堆排序算法 #

1. 堆排序算法原理
2. 堆排序算法的实现

收获 #

学完本节内容，可以初步理解并掌握堆排序算法。

堆排序算法原理 #

堆排序的原理如下：

1. 将待排序列表中的数据按从上到下、从左到右的顺序构造成一棵完全二叉树。初始的数组和对应的二叉树如下图所示。
   
   
2. 将完全二叉树中每个节点(叶节点除外)的值与其子节点(子节点有一个或两个)中较大的值进行比较，如果节点的值小于子节点的值，则交换他们的位置。如下图所示。
   
3. 将节点与子节点进行交换后，重复步骤2，直到不需要交换或子节点是叶节点时停止。比较完所有的非叶节点后，即可构建出堆结构。
4. 将数据构造成堆结构后，将堆顶与堆尾交换，然后将堆尾从堆中取出来，添加到已排序序列中，完成一轮堆排序，堆中的数据个数减1。如下图所示。
   
5. 重复步骤2,3,4，直到堆中的数据全部被取出，列表排序完成。

堆排序算法的实现 #

python实现代码如下：

def heap_sort(a):
    first = len(a) // 2 - 1
    for start in range(first, -1, -1):
        # 从下到上，从右到左对每个非叶节点进行调整，循环构建成大顶堆
        big_heap(a, start, len(a) - 1)
    for end in range(len(a) - 1, 0, -1):
        # 交换堆顶和堆尾的数据
        a[0], a[end] = a[end], a[0]
        # 重新调整完全二叉树，构造成大顶堆
        big_heap(a, 0, end - 1)
    return a


def big_heap(a, start, end):
    root = start
    # 左孩子的索引
    child = root * 2 + 1
    while child <= end:
        # 节点有右子节点，并且右子节点的值大于左子节点，则将child变为右子节点的索引
        if child + 1 <= end and a[child] < a[child + 1]:
            child += 1
        if a[root] < a[child]:
            # 交换节点与子节点中较大者的值
            a[root], a[child] = a[child], a[root]
            # 交换值后，如果存在孙节点，则将root设置为子节点，继续与孙节点进行比较
            root = child
            child = root * 2 + 1
        else:
            break


if __name__ == '__main__':
    a=[10,17,50,7,30,15,5,38,21]
    print(heap_sort(a))

小结 #

理解并掌握堆排序算法的原理
掌握堆排序的代码实现

习题 #

1. 习题1：画出堆排序算法的流程图
2. 习题2：使用堆排序算法，对列表[10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]进行升序排列