1. 基本原理
堆排序就是利用堆的特性进行一个无序序列的排序工作。
堆的特点
堆分为最大堆和最小堆，其实就是完全二叉树。
最大堆要求节点的元素都要不小于其孩子
最小堆要求节点元素都不大于其左右孩子。
两者对左右孩子的大小关系不做任何要求，其实很好理解。
有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。
其实我们的堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩
余的元素重新调整为最大堆，依次类推，最终得到排序的序列。
基本思想
将初始待排序关键字序列(a1,a2,⋯,an)构建成大顶堆，此堆为初始的无序区
将堆顶元素a[1]与最后一个元素a[n]交换，此时得到新的无序区(a1,a2,⋯,an−1)和新的有序区(an)
由于交换后新的堆顶a[1]可能违反堆的性质，因此需要对当前无序区(a1,a2,⋯,an−1)调整为新堆，然后再次将a[1]与无序区最后一个元素交换，得到新的无序区(a1,a2,⋯,an−2)新的有序区(an−1,an−2)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
一个例子
这里有一个无序的序列，[16,7,3,20,17,8]
首先构造一个二叉树：
然后依据构造的二叉树，从下至上调整，得到一个初始化的最大堆。
再讲堆顶的数和堆底的数互换。
但是，此时的堆可能不符合要求，需要再从新调整：
再重复，将堆顶和堆底互换（当然了，在之前，堆的大小要减1）
又一次进行调整：
重复，将堆顶和堆底互换（当然了，在之前，堆的大小又要减1）
再调整：
再换：
再调整：
再换：
到这，一个堆排序就完成了，最终得到一个最小堆。
2. Python 实现
程序
#定义一个对单一节点的父节点以及其孩子大小交换的函数def initialMaxHeap(a,startIndex,endIndex):leftChildIndex=2*startIndex+1 #父节点为i，左边孩子的位置为2*i+1#判断左边孩子是否有右边的孩子if leftChildIndex+1<=endIndex and a[leftChildIndex+1]>a[leftChildIndex]:leftChildIndex+=1 if a[leftChildIndex]>a[startIndex]:#左右孩子值大于父节点的值的时候，交换,使得这个二叉树的最大值位于父节点上temp=a[startIndex]a[startIndex]=a[leftChildIndex]def myHeapSort(a):#a是要排序的序列listLength=a.__len__()while True:if listLength==1:break;finalNodeHavingChild=(listLength)//2-1 #寻找最下一层的父节点#从下到上调整堆for i in range(finalNodeHavingChild,-1,-1):#print(a[i])initialMaxHeap(a,i,listLength-1)#将堆顶的数换到堆底temp=a[0]a[0]=a[listLength-1]a[listLength-1]=temp#这个调整之后，可能不满足最大堆的定义，需要再从上到下再调整一次#从上到下调整堆for j in range(0,finalNodeHavingChild+1):#print(a[j])initialMaxHeap(a,j,listLength-1)#将堆的数量减少listLength-=1return a def generatingRandomNumber(sampleNumber,lower,upper):#sampleNumber :是生成的随机序列的长度#lower和upper分别是生成随机序列的下限与上限#最后，函数会返回一个随机的无序的序列a。import randoma=[]aSize=a.__len__()while 1:aSize=a.__len__()if aSize>=sampleNumber:breakelse:temp=int(random.randint(lower,upper))a.append(temp)return aif __name__=="__main__":a=generatingRandomNumber(20,1,100)print()print('the sequence before sorting is:\n')print(a)print()print('the sequence after sorting is:\n')print(myHeapSort(a))
结果为：
结果正确！！！
排序动态图
3. 时间复杂度分析
在构建堆(初始化大顶堆)的过程中，完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和必要的互换，对于每个非终端结点来说，其实最多进行两次比较和一次互换操作，因此整个构建堆的时间复杂度为: O(n)。大概需进行 n2∗2=n 次比较和 n2 次交换。
在正式排序时，n 个结点的完全二叉树的深度为
如果觉得《排序算法三：堆排序基本原理以及Python实现》对你有帮助，请点赞、收藏，并留下你的观点哦！
