python实现【堆排序】(HeapSort)

算法原理及介绍

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法****。堆实质是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序**。

算法过程描述

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；

2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；

3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

算法排序图解如下

python实现代码

def heapify(arr, n, i):
    # 构建大顶堆
    largest = i
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 2*i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 交换
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    # 构建大顶堆
    for i in range(n, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        # 一个个交换元素
        arr[i], arr[0] = arr[0], arr[i]  # 交换
        heapify(arr, i, 0)
    return arr

如果喜欢作者，欢迎点赞、收藏及关注，谢谢！
点击下面相应的链接即可查看各个算法的详细介绍及python实现方法：

1. 冒泡排序(BubbleSort)
2. 选择排序(SelectionSort)
3. 插入排序(InsertSort)
4. 归并排序(MergeSort)
5. 快速排序(QuickSort)
6. 堆排序(Heap Sort)
7. 计数排序(Count Sort)
8. 桶排序(Bucket Sort)
9. 基数排序(Radix Sort)
10. 希尔排序(Shell Sort)