新的快速排序算法: 《Dual-Pivot QuickSort》阅读笔记

相信大家在大学的《算法与数据结构》里面都学过快速排序(QuickSort), 知道这种排序的性能很好，JDK里面直到JDK6用的都是这种经典快排的算法。但是到了JDK7的时候JDK内置的排序算法已经由经典快排变成了Dual-Pivot排序算法。那么Dual-Pivot到底是何方圣神，能比我们学过的经典快排还要快呢？我们一起来看看。

经典快排

在学习新的快排之前，我们首先来复习一下经典快排，它的核心思想是:

接受一个数组，挑一个数(pivot)，然后把比它小的那一摊数放在它的左边，把比它大的那一摊数放在它的右边，然后再对这个数左右两摊数递归的执行快排过程，直到子数组只剩一个数为止。[2]

伪代码大概是这样的:

void quicksort(int array[], int left, int right)
{
    //Do nothing if left <= right
    //p <- Get a number from array
    //Put elements <= p to the left side
    //Put elements >= p to the right side
    //Put p in the middle slot which index is pivot
    //Recursive quicksort the left parts and right parts
}

元素比较的次数

经典快排为什么快？ 所谓快其实专业的说法是“时间复杂度”。对于排序算法来说主要看的是排序所需要的元素比较的次数。

我们在《算法与数据结构》里面都是这么学的。

对于快排来说，假设输入数组里面数字的个数为n，那么平均要进行的元素之间比较的次数是: O(nlogn)。相比冒泡排序的O(n2)来说比较的次数要少，那么当然就快了。

Dual-Pivot快排是个什么鬼？

它是俄罗斯人Vladimir Yaroslavskiy在2009年开发出来的。要知道经典快排在1990年代稳定下来就再也没有大改过了，几乎所有的语言里面的排序用的都是同样的经典快排的算法。20年之后当这个俄罗斯人提出新的Dual-Pivot快排的时候，很多人的第一想法是不信的，因为经典快排都被研究烂了，大家不相信在这个算法上面还会有什么可以改进的地方。

那么Dual-Pivot快排到底是怎么样的一个排序算法呢？其实从它的名字里面可以看出一些端倪：在经典快排里面有一个pivot的概念，它是用来分隔大数和小数的 -- 这个pivot把一个数组分成两份。那么所谓的Dual-Pivot其实就是用两个Pivot, 把整个数组分成三份。伪代码大概是这样的:

dual_pivot_quicksort(A,left,right) // sort A[left..right]
    if right−left ≥ 1
        // Take outermost elements as pivots (replace by sampling)
        p := min {A[left],A[right]}
        q := max{A[left],A[right]}
        ℓ := left +1; g := right −1; k := ℓ
        while k ≤ g
            if A[k] < p
                 Swap A[k] and A[ℓ]; ℓ := ℓ+1
            else if A[k] ≥ q
                while A[g] > q and k < g
                    g := g −1
                end while
                Swap A[k] and A[g]; g := g −1
                if A[k] < p
                    Swap A[k] and A[ℓ]; ℓ := ℓ+1
                end if
            end if
            k := k +1
        end while
        ℓ := ℓ−1; g := g +1
        A[left] := A[ℓ]; A[ℓ] := p // p to final position
        A[right] := A[g]; A[g] := q // q to final position
        dual_pivot_quicksort(A, left , ℓ−1)
        dual_pivot_quicksort(A, ℓ+1,g −1)
        dual_pivot_quicksort(A,g +1,right)
    end if

看起来主要的区别就是经典快排递归的时候把输入数组分两段，而Dual-Pivot则分三段，就这么简单，那为什么这就快了呢？
其实如果按照元素比较次数来比较的话，Dual-Pivot快排元素比较次数其实比经典快排要多:

1.5697nlnn VS 1.7043nlnn

理论跟实际情况不符合的时候，如果实际情况没有错，那么就是理论错了。

CPU与内存

要理解上面的问题，先介绍点背景知识。我们平常很少考虑过CPU的速度，内存的速度，CPU和内存速度是否匹配的问题。

其实它们是不匹配的。

距统计在过去的25年里面，CPU的速度平均每年增长46%, 而内存的带宽每年只增长37%，那么经过25年的这种不均衡发展，它们之间的差距已经蛮大了。

假如这种不均衡持续持续发展，有一天CPU速度再增长也不会让程序变得更快，因为CPU始终在等待内存传输数据，这就是传说中内存墙(Memory Wall)。

有点像木桶理论：木桶的容量是由最短的那块板决定的，所以你CPU再快，如果内存带宽不够，那也没用。

25年前Dual-Pivot快排可能真的比经典快排要慢，但是25年之后虽然算法还是以前的那个算法，但是计算机已经不是以前的计算机了。在现在的计算机里面Dual-Pivot算法更快！

扫描元素个数

那么既然光比较元素比较次数这种计算排序算法复杂度的方法已经无法客观的反映算法优劣了，那么应该如何来评价一个算法呢？作者提出了一个叫做扫描元素个数的算法。

在这种新的算法里面，我们把对于数组里面一个元素的访问: array[i] 称为一次扫描。但是对于同一个下标，并且对应的值也不变得话，即使访问多次我们也只算一次。而且我们不管这个访问到底是读还是写。

其实这个所谓的扫描元素个数反应的是CPU与内存之间的数据流量的大小。

因为内存比较慢，统计CPU与内存之间的数据流量的大小也就把这个比较慢的内存的因素考虑进去了，因此也就比元素比较次数更能体现算法在当下计算机里面的性能指标。

在这种新的算法下面经典快排和Dual-Pivot快排的扫描元素个数分别为:

1.5697nlnn VS 1.4035nlnn

也就是说经典快排确实进行了更多的元素扫描动作，因此也就比较慢。在这种新的算法下面，Dual-Pivot快排比经典快排t节省了12%的元素扫描，从实验来看节省了10%的时间。

结论

• 由于CPU与内存的发展失衡，我们在分析算法复杂性的时候已经不能简单地用元素比较次数来比较了，因为这种比较的方法只考虑了CPU的因素，没有考虑内存的因素。
• 对于那种对输入数据进行顺序扫描的排序算法，扫描元素的个数这种新的算法把内存的流量的因素考虑进去，比较适应新时代。
• 世界在不断的变化，你当年在学堂里面学的东西可能已经过时了。

参考资料

1. Why Is Dual-Pivot Quicksort Fast?
2. 一个Quicksort究竟可以写到多么短

最后

以上就是坚强冬瓜为你收集整理的新的快速排序算法: 《Dual-Pivot QuickSort》阅读笔记的全部内容，希望文章能够帮你解决新的快速排序算法: 《Dual-Pivot QuickSort》阅读笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。