8、堆排序
（1）堆的界说：设有n个元素的序列{K1，K2，…，Kn}，当且仅当满意下述关系之一时，称之为堆。
(i) Ki≤K2 i 且Ki≤K2 i +1；
(ii) Ki≥K2 i 且Ki≥K2 i +1 。
此中(i)称为小顶堆，(ii)称为大顶堆。
（2）堆排序的根本头脑为：先将序列创建堆，然后输出堆顶元素，再将剩下的序列创建堆，然后再输出堆顶元素，依此类推，直到全部元素均输出为止，此时元素输出的序列就是一个有序序列。
（3）堆排序的算法步调如下(以大顶堆为例)：
(i)初始时将次序表R[1..n]中元素创建为一个大顶堆，堆顶位于R[1]，待序区为R[1..n]。
(ii)循环实验步调3～步调4，共n-1次。
(iii)假设为第i 运行，则待序区为R[1..n-i+1]，将堆顶元素R[1]与待序区尾元素R[n-i+1]互换，此时顶点元素被输出，新的待序区为R[1..n-i ]。
(iv)待序区对应的堆已经被粉碎，将之重新调解为大顶堆。
（4）堆排序时间复杂度为：O(nlog2n)，是不稳固的排序。
