堆排序

堆排序————通过在将数据读入的过程中建小堆，再每次取出root，并重构该堆，最后就得到从小到大的序列。

 

堆排序基于堆结构，堆结构整棵树是平衡的，而且他的数组实现方式对空间的利用率也很高。平均情况下他要比快速排序慢一个常数因子，但是他很适合由于数据集太大而放不进内存的排序情况（仍是原地排序）——非原地排序只学过归并排序。归并排序也适用于数据太大而放不入内存的情况。

 

建堆要用O(n)的时间，并且n次取得最大元素要用O(logn)的时间——将root与最后一个元素交换位置将新的root下降到合适位置需要O(logn)的时间，再删除旧根。因此整个时间代价是O(nlogn)。

堆排序更适合于外排序，其最佳，平均，最差的时间代价都是O(nlogn)。