Swift实现堆排序算法的代码示例
算法思想
堆排序利用了最大堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。
1.用最大堆排序的基本思想
（1）先将初始文件R[1..n]建成一个最大堆，此堆为初始的无序区
（2）再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
（3）由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
2.最大堆排序算法的基本操作：
（1）建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2)其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。
（2）调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。
（3）堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)[2]
注意
（1）只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
（2）用小根堆排序与利用最大堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
Swift示例
（1）基于最大堆实现升序排序
funcinitHeap(inouta:[Int]){
forvari=(a.count-1)/2;i>=0;--i{
adjustMaxHeap(&a,len:a.count,parentNodeIndex:i)
}
}
funcadjustMaxHeap(inouta:[Int],len:Int,parentNodeIndex:Int){
//如果len<=0，说明已经无序区已经缩小到0
guardlen>1else{
return
}
//父结点的左、右孩子的索引
letleftChildIndex=2*parentNodeIndex+1
//如果连左孩子都没有，一定没有右孩子，说明已经不用再往下了
guardleftChildIndex<lenelse{
return
}
letrightChildIndex=2*parentNodeIndex+2
//用于记录需要与父结点交换的孩子的索引
vartargetIndex=-1
//若没有右孩子，但有左孩子，只能选择左孩子
ifrightChildIndex>len{
targetIndex=leftChildIndex
}else{
//左、右孩子都有，则需要找出最大的一个
targetIndex=a[leftChildIndex]>a[rightChildIndex]?leftChildIndex:rightChildIndex
}
//只有孩子比父结点还要大，再需要交换
ifa[targetIndex]>a[parentNodeIndex]{
lettemp=a[targetIndex]
a[targetIndex]=a[parentNodeIndex]
a[parentNodeIndex]=temp
//由于交换后，可能会破坏掉新的子树堆的性质，因此需要调整以a[targetIndex]为父结点的子树，使之满足堆的性质
adjustMaxHeap(&a,len:len,parentNodeIndex:targetIndex)
}
}
funcmaxHeapSort(inouta:[Int]){
guarda.count>1else{
return
}
initHeap(&a)
forvari=a.count-1;i>0;--i{
//每一趟都将堆顶交换到指定范围内的最后一个位置
ifa[0]>a[i]{
lettemp=a[0]
a[0]=a[i]
a[i]=temp
}
print(a)
print(i-1)
//有序区长度+1，而无序区长度-1，继续缩小无序区，所以i-1
//堆顶永远是在0号位置，所以父结点调整从堆顶开始就可以了
adjustMaxHeap(&a,len:i-1,parentNodeIndex:0)
print(a)
}
}
（2）基于最小堆降序排序
funcinitHeap(inouta:[Int]){
forvari=(a.count-1)/2;i>=0;--i{
adjustMinHeap(&a,len:a.count,parentNodeIndex:i)
}
}
funcadjustMinHeap(inouta:[Int],len:Int,parentNodeIndex:Int){
//如果len<=0，说明已经无序区已经缩小到0
guardlen>1else{
return
}
//父结点的左、右孩子的索引
letleftChildIndex=2*parentNodeIndex+1
//如果连左孩子都没有，一定没有右孩子，说明已经不用再往下了
guardleftChildIndex<lenelse{
return
}
letrightChildIndex=2*parentNodeIndex+2
//用于记录需要与父结点交换的孩子的索引
vartargetIndex=-1
//若没有右孩子，但有左孩子，只能选择左孩子
ifrightChildIndex>len{
targetIndex=leftChildIndex
}else{
//左、右孩子都有，则需要找出最大的一个
targetIndex=a[leftChildIndex]<a[rightChildIndex]?leftChildIndex:rightChildIndex
}
//只有孩子比父结点还要大，再需要交换
ifa[targetIndex]<a[parentNodeIndex]{
lettemp=a[targetIndex]
a[targetIndex]=a[parentNodeIndex]
a[parentNodeIndex]=temp
//由于交换后，可能会破坏掉新的子树堆的性质，因此需要调整以a[targetIndex]为父结点的子树，使之满足堆的性质
adjustMinHeap(&a,len:len,parentNodeIndex:targetIndex)
}
}
funcminHeapSort(inouta:[Int]){
guarda.count>1else{
return
}
initHeap(&a)
forvari=a.count-1;i>0;--i{
//每一趟都将堆顶交换到指定范围内的最后一个位置
ifa[0]<a[i]{
lettemp=a[0]
a[0]=a[i]
a[i]=temp
}else{
return//可以直接退出了，因为已经全部有序了
}
//有序区长度+1，而无序区长度-1，继续缩小无序区，所以i-1
//堆顶永远是在0号位置，所以父结点调整从堆顶开始就可以了
adjustMinHeap(&a,len:i-1,parentNodeIndex:0)
}
}
测试：
vararr=[5,3,8,6,4] //vararr=[89,-7,999,-89,7,0,-888,7,-7] maxHeapSort(&arr) print(arr) //打印日志如下： [4,6,5,3,8] 3 [6,4,5,3,8] [3,4,5,6,8] 2 [5,4,3,6,8] [3,4,5,6,8] 1 [3,4,5,6,8] [3,4,5,6,8] 0 [3,4,5,6,8] [3,4,5,6,8]