简介堆排序（HeapSort）是一种利用堆的数据结构设计的排序算法，属于选择排序。堆是一棵完全二叉树，具有以下性质：每个节点的值都大于或等于其左右子节点的值，称为大顶堆；或者每个节点的值都小于或等于其左右子节点的值，称为小顶堆。堆排序的思想是：将一个无序的序列调整成堆，可以找到序列中的最大值（或最小值），然后将找到的元素与结束元素交换，这样有序的序列元素就会加一，无序序列的元素减一，对新的无序序列重复操作，从而实现排序。算法实现步骤构造初始堆。将给定的无序序列构造成大顶堆（一般升序使用大顶堆，降序使用小顶堆）；将顶部元素与最后一个元素交换以使最后一个元素最大。然后继续调整堆，然后交换堆顶元素和堆尾元素，得到第二大元素；重新调整结构，使其满足堆定义，然后继续交换栈顶元素和当前端元素；如此反复交换、重建、交换，直到整个序列排序完毕。Python代码实现#heap_sort代码实现defbuild(arr:List[int],root,end):whileTrue:child=2*root+1#左孩子节点的位置ifchild>end:#如果是左孩子node超过最后一个节点，则终止循环breakif(child+1<=end)and(arr[child+1]>arr[child]):#如果右子节点在最后一个节点之前，则右子节点大于左子节点如果节点大，将我们的子节点指针移到右子节点child+=1ifarr[child]>arr[root]:#如果最大子节点大于根节点,交换两者的顺序并移动根节点指针,移动到这个子节点arr[child],arr[root]=arr[root],arr[child]root=childelse:breakdefheap_sort(arr:List[int]):n=len(arr)first_root=n//2-1#确认最深和最后一个根节点的位置forrootinrange(first_root,-1,-1):#从后面遍历所有根节点在前面，构建一个堆并进行调整build(arr,root,n-1)forendinrange(n-1,0,-1):#调整完成后，将堆顶根节点的位置与堆中最后一个元素交换，即现在是数组中最大的元素，然后调整堆的大小，将最大的元素放在堆的顶部。重复以上操作arr[0],arr[end]=arr[end],arr[0]build(arr,0,end-1)#testdataif__name__=='__main__':importrandomrandom.seed(54)arr=[random.randint(0,100)for_inrange(10)]print("原始数据：",arr)heap_sort(arr)print("堆排序结果：",arr)#输出原始数据：[17,56,71,38,61,62,48,28,57,42]堆排序结果：[17,28,38,42,48,56,57,61,62,71]动画演示算法分析时间复杂度每次重构时，随着堆容量的减少，层数会减少，函数的时间复杂度会发生变化。重建堆总共需要n-1次循环，每次循环的比较次数为$\log_2i$，则总和为：$$T=\log_2n+\log_2(n-1)+\cdots+\log_23+\log_22=\log_2\left(n!\right)\\\因为\left(\dfrac{n}{2}\right)^{\dfrac{n}{2}}\len!\len^n\\\因此\dfrac{n}{2}\log_2\left(\dfrac{n}{2}\right)\le\log_2\left(n!\right)\len\log_2n$$所以堆排序的时间复杂度是$O(nlog_2n)$。空间复杂度空间复杂度是临时变量在交换元素时占用的内存空间，所以堆排序的空间复杂度是$O(1)$Stability堆排序在交换数据的时候比较父节点和子节点所以，即使有两个具有相等值的兄弟节点，它们的相对顺序可能会在排序过程中发生变化。因此，堆排序是不稳定的。综合评价时间复杂度（平均）时间复杂度（最好）时间复杂度（最差）空间复杂度排序方法稳定性$O(nlog_2n)$$O(nlog_2n)$$O(nlog_2n)$$O(1)$in-placeisunstable联系我们个人博客网站：http://www.bling2.cn/Github地址：https://github.com/lb971216008/Use-Python-to-Achieve知乎专栏：https://zhuanlan.zhihu.com/Use-Python-to-Achieve小专栏：https://xiaozhuanlan.com/Use-Python-to-Achieve博客园：https://www.cnblogs.com/Use-Python-to-Achieve
