从树形选择排序中我们知道，为了构成完全二叉树，需要额外很大的辅助空间，为了弥补，威洛姆斯在1964年提出了堆排序。堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占一个存储空间。 堆顶一如下：n 个元素的序列{K1,K2,...,Kn} 当且仅当满足如下关系时，称之为堆。 Ki=K2i && Ki=K(2i+1) 或者 Kisq[j]) ){ j++; } /*有孩子比根大，破环了堆*/ if(sq[j]rc){ sq[low]=sq[j]; /*让low指向其中孩子的根，使其继续向下调整*/ low=j; } /*根本身根就是最大的，未破环堆*/ else{ break; } } sq[low]=rc; } /* * 对sq+1,sq+2,sq+3,...,sq+length 进行堆排序 */ void HeapSort(int *sq,int length){ //从最后一个非叶子节点进行从下往上调整，建立大根堆 for(int i=length/2;i0;i--){ HeapAdjust(sq,i,length); } /* * 取大根堆第一个元素后(得到最大元素)和最后一个元素交换 * 此时最大的数就移至最后，重新调整前面的序列为大根堆 */ int tmp; for(int i=length;i0;i--){ /* sq[1]sq[length] */ tmp=sq[1]; sq[1]=sq[i]; sq[i]=tmp; HeapAdjust(sq,1,i-1); } } 堆排序在最坏情况下，其时间复杂度也为 O（NlogN）。相对于快速排序来说，这是堆排序的最大优点，此外堆排序仅需一个记录大小的供交换的辅助空间。

*博客内容为网友个人发布，仅代表博主个人观点，如有侵权请联系工作人员删除。