改进的堆排序算法：
以小堆为例，堆排序的简化过程如下
1、初始化n个节点的二叉树为小堆
2、把堆顶元素移除，将堆的最后一个元素A移到堆顶，从上至下将A下沉，直至二叉树为小堆。
重复2，直至堆为空。
这是我们用到的堆排序算法，以习为常。但这个算法的效率还可以优化吗？且看第2步，堆的最后一个元素相对于根元素的两个子节点，有很大的概率比他们大，从概率的角度来看这种比较是不划算的，为什么要选这么一个较大元素进行下沉呢。于是，第2步可以做如下改进
{
a 移除堆顶元素，将一个空元素填到堆顶（可以将这个空元素理解为一个无限大的元素），
b 比较空元素其两个子节点L和R，若L较小，则将L的值替换空元素，将L赋值为空。
... 重复b直至空元素下沉到堆的底部。
c 若空白元素是最后一个元素，则删除空白元素。
否则将空白元素与最后一个元素互换，然后删除空白元素，再将最后一个元素进行上浮（与其父元素比较，若父元素比其大，则元素互换并继续上浮）。
c 若空白元素是最后一个元素，则删除空白元素。
否则将空白元素与最后一个元素互换，然后删除空白元素，再将最后一个元素进行上浮（与其父元素比较，若父元素比其大，则元素互换并继续上浮）。
}
这样做的好处是，只需要比较两个子节点的值（一个比另一个大的概率为50%，这种比较相对来说比较划算），最后元素只需要在最后一步做上浮的操作（因为最后一个元素本身较大，上浮时只需进行较少次数的比较）。
快速排序时间复杂度能做到
吗？
吗？
快速排序我们会随机选取一个元素作为支点，将小于支点的元素移至支点的左端，将大于支点的元素移至右端。我们希望左右两边的元素个数趋于平衡。是否真的能达到这种平衡我们不妨从概率的角度来看一下。
将选取的支点元素计为A0，第k个与A0比较的元素计为Ak.则有
P(A0>A1)=1/2.
P((A0>A1)&&(A0>A2))=1/3.(任意的三个元素中，随机选取一个元素为最大元素的概率是1/3)
P((A0>A2)|(A0>A1)) = P((A0>A1)&&(A0>A2))/P(A0>A1)=2/3 (贝叶斯公式:P(B|C)=P(BC)/P(C),也即若A0>A1,则A0>A2的概率为2/3)
也就是说，如果第一个与支点元素比较的元素小于支点元素，那么第二个与支点元素比较的元素小于支点元素的概率是2/3, 更进一步可以证明，如果前面M个与支点比较的元素都小于支点元素，那么第M+1个元素也小于支点元素的概率为(M+1)/(M+2).
所以快速排序每次分割，元素更倾向于向支点的某一边聚集，并不能做到近似的均匀分割，所以快排的平均时间复杂度达不到
.
参考文档：http://users.aims.ac.za/~mackay/sorting/sorting.html
.参考文档：http://users.aims.ac.za/~mackay/sorting/sorting.html
