j++; if(rc > list.key[j]) break; list.key[s] = list.key[j]; s = j; } list.key[s] = rc; } void HeapSort(SqList &list) { KeyType temp; for(int i = list.Length/2; i>0; i--) HeapAdjust(list,i,list.Length); for(i = list.Length; i>1; --i){ temp = list.key[1]; list.key[1] = list.key[i]; list.key[i] = temp; HeapAdjust(list,1,i-1); } //将 list 建成大根堆，从表后往前调整 //每次将大根堆的第一个元素(即值最大) //取出来放在末尾位置上(撇开已经排好的序列) //重新调整 list 为大根堆 } 【算法分析】 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调 用 Heapify 实现的。 堆排序的最坏时间复杂度为 O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为 O(1)， 它是不稳定的排序方法。