环境

Python 3.5.2

原理

  • 将列表构造成最大堆或最小堆
  • 将堆的根节点,即最大值或最小值与堆的末尾对调
  • 将末尾元素(即之前得到的堆的根节点)移除后,重构堆,如此循环

源码

def heap_sort(l):
    def max_heapify(root_index, end_index):
        """函数用于构造最大堆"""
        # 减一是因为堆的下标从1开始
        max_child_index = root_index*2-1

        # 在该二叉树有两个子节点的情况下,将两个子节点比较大小
        if max_child_index + 1 < end_index:
            if l[max_child_index+1] > l[max_child_index]:
                max_child_index += 1

        # 将最大的子节点与根节点做比较
        if l[max_child_index] > l[root_index-1]:
            l[max_child_index], l[root_index-1] = l[root_index-1], l[max_child_index]


    # 循环构造最大堆,而后将最大堆的根节点与末节点调换
    for end_index in range(len(l), 1, -1):
        # 每次要构造的最大堆大小与末节点有关
        max_root_index = end_index//2

        # 构造一个最大堆
        for root_index in range(max_root_index, 0, -1):
            max_heapify(root_index, end_index)

        # 将最大堆的根节点与末节点调换
        l[0], l[end_index-1] = l[end_index-1], l[0]


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    heap_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(nlogn)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定

环境

Python 3.5.2

原理

  • 将递归分解列表,直至最小(即每个列表仅有一个元素)
  • 将列表分解最小之后,递归合并两个列表,即挨个比较两个列表中最前面的元素,谁较小就将谁加入新的列表,而后该列表的下标后移一位,继续比较,直至其中一个列表为空,而后将另一个列表中剩余的元素加入新列表
  • 不断合并,直至完全排序完成

源码

def merge_sort(l):
    # 对列表进行二分分解
    n = len(l)
    if n <= 1:
        return l
    mid_posi = n//2
    # print(1)
    l_list = merge_sort(l[:mid_posi])
    # print(2)
    r_list = merge_sort(l[mid_posi:])
    # print(3)

    # 对列表进行合并
    sorted_list = []
    l_posi = 0
    r_posi = 0
    # print('l_list: %s' % l_list)
    # print('r_list: %s' % r_list)

    while l_posi < len(l_list) and r_posi < len(l_list):
        if l_list[l_posi] <= r_list[r_posi]:
            sorted_list.append(l_list[l_posi])
            l_posi += 1
        else:
            sorted_list.append(r_list[r_posi])
            r_posi += 1

    # 将列表剩余部分合并
    sorted_list += l_list[l_posi:]
    sorted_list += r_list[r_posi:]
    # print('sorted_list: %s' % sorted_list)

    return sorted_list


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    sorted_list = merge_sort(l)
    print(sorted_list)

时间复杂度

  • 最优时间复杂度:O(nlogn)
  • 最坏时间复杂度:O(nlogn)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):稳定

环境

Python 3.5.2

原理

  • 为插入排序的优化
  • 对要排序的列表根据一定间隔(初始间隔一般设为列表长度的一半)进行分组
  • 对各列表之间相同位置(下标)的元素进行插入排序
  • 间隔减半,再次分组并对各列表之间相同位置(下标)的元素进行插入排序
  • 如此循环,最终间隔为1,即为正常的插入排序

源码

def shell_sort(l):
    n = len(l)
    # 初始间隔
    gap = n//2

    while gap > 0:
        for i in range(gap, n):
            for j in range(i, gap-1, -gap):
                if l[j] < l[j-gap]:
                    l[j], l[j-gap] = l[j-gap], l[j]
                else:
                    break
        gap //= 2


if __name__ == '__main__':
    l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
    print(l)
    shell_sort(l)
    print(l)

时间复杂度

  • 最优时间复杂度(初始间隔为列表长度一半时):O(nlogn)
  • 最坏时间复杂度:O(n2)
  • 稳定性(多个元素等值的情况下是否会破坏原有顺序):不稳定