快排的改良版——内省式排序

快速排序是一种很快的算法,它平均的时间复杂度为O(nlgn), 最坏时间复杂度为O(n^2)。但是快排有很多改良版,其中一种就是内省式的快排,在STL中的快快排使用的就是这种算法。

  • 为什么需要这种算法

因为快排在面对小数组(比如大小为10的数组)且基本有序的情况下,它的表现还没插入排序要好。因为数组的基本有序,使得插入排序不用很多次的执行元素的移动,并且可以避免递归。 在SGI STL中的函数sort使用的排序算法其实就是内省式的排序算法。内省的排序算法是基于快排实现的。假设待排序的数组大小为n,去一个k值,使得k为满足2^k <= n的最大值。k为最大的递归层次、 为什么要设置最大递归层次呢? 因为快排的递归层次过深的时候,很可能会退化成O(n^2)。内省式排序使用k来控制快排的递归深度,当快排的递归深度到达k的时候选择使用heap排序。

  • 为什么不一开始就使用heap排序

heap排序在平均时间复杂度是O(nlgn),最坏情况也是O(nlgn),看起来要比快排要快。但是实际上,快排是要比heap排序要快,第一个原因是:heap排序虽然和快排在平均情况下的时间复杂度是O(nlgn),但是heap排序的时间常数要比快排的时间常数要大。第二个原因是:据统计,快排的最坏情况在是很少发生的。第三个原因是:快排能够比较好的吻合程序的空间局部性原理,因为它操作的基本都是相邻的元素(虚拟存储器的设计理论基础中就有程序的时间局部性和空间局部性),能够减少内存缺页中断的发生次数。

  • 为什么要使用heap排序呢

因为在递归层次太深的时候,就意味着发生最坏情况的概率大大的提升了,这时候因为heap排序的最坏情况下的时间复杂度是O(nlgn)比快排的O(n^2)要好,因此使用heap排序能更好优化排序效率。