SakuraTears的博客

越努力越幸运

排序算法（七） - 双轴快速排序

发表于 分类于 阅读次数： Valine：
本文字数： 5.6k 阅读时长 ≈ 5 分钟

前言

上篇文章我们介绍了TimSort排序算法，排序算法（六）- TimSort，今天我们再来看一种排序算法，双轴快速排序（DualPivotQuicksort），这个排序算法也是非常有意思的，它也是目前Java对于基本数据类型数组排序使用的内置排序算法。

正文

双轴快速排序（DualPivotQuicksort）

简介及原理

双轴快速排序（DualPivotQuicksort）是Vladimir Yaroslavskiy在2009年开发出来的一种排序算法，是快速排序的一种变体，与快排不同的是，它有两个基准值（快排有一个）。

相比快速排序，双轴快速排序有着更高的效率，我们来看下。

我们先来回顾下快速排序，快排的主要原理如下：

对于待排序数组，选择一个基数(pivot)，然后把比它小的那些数放在它的左边，把比它大的那些数放在它的右边，然后再对这个数左右两部分数递归的执行快排过程，直到子数组只剩一个数为止。

如下图所示。

upload successful

而双轴快速排序会把待排序数组分为3份，有两个基准点，我们先来看下双轴快排的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// sort A[left..right]
dual_pivot_quicksort(A,left,right) 
    if right−left ≥ 1
        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
        // p to final position
        A[left] := A[ℓ]; A[ℓ] := p 
        // q to final position
        A[right] := A[g]; A[g] := q 
        dual_pivot_quicksort(A, left , ℓ−1)
        dual_pivot_quicksort(A, ℓ+1,g −1)
        dual_pivot_quicksort(A,g +1,right)
    end if

它的原理图如下：

upload successful

双轴快速排序的工作原理：

对于待排序数组，取最小索引上的值和最大索引上的值为基准，根据这两个基准，可以把数组分成小于最小基准的一部分、大于最小基准小于最大基准的一部分、大于最大基准的一部分，共三部分；再对这三部分进行双轴快速排序。

代码实现

我们根据伪代码，可以写出双轴快排的具体代码，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class DualPivotQuickSort {

    public static void dualPivotQuickSort(int[] a, int left, int right) {
        //根据两个基准将数据分成三部分
        if (right - left >= 1) {
            int pivot1 = Math.min(a[left], a[right]);
            int pivot2 = Math.max(a[left], a[right]);
            int start = left + 1, end = right - 1, tempIndex = start;
            while (tempIndex <= end) {
                if (a[tempIndex] < pivot1) {
                    swap(a, tempIndex, start);
                    start++;
                } else if (a[tempIndex] >= pivot2) {
                    while (a[end] > pivot2 && tempIndex < end) {
                        end--;
                    }
                    swap(a, tempIndex, end);
                    end--;
                    if (a[tempIndex] < pivot1) {
                        swap(a, tempIndex, start);
                        start++;
                    }
                }
                tempIndex++;
            }
            start--;
            end++;
            //分完堆后两个基准的位置还不对，需要将这两个基准移动到正确位置
            a[left] = a[start];
            a[start] = pivot1;
            a[right] = a[end];
            a[end] = pivot2;
            //对分成的三部分继续进行双轴快排
            dualPivotQuickSort(a, left, start - 1);
            dualPivotQuickSort(a, start + 1, end - 1);
            dualPivotQuickSort(a, end + 1, right);
        }
    }
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = new int[100000000];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(100000000);
        }
        System.out.println("DualPivotQuicksort排序开始：");
        long start = System.currentTimeMillis();
        dualPivotQuickSort(a, 0, a.length - 1);
        System.out.println("DualPivotQuicksort耗时：" + (System.currentTimeMillis() - start) + "ms");
        System.out.println("DualPivotQuicksort排序完成！");
        System.out.println("数组是否有序：" + isOrdered(a));
    }
}

我们继续使用1亿数据量对其进行测试，可得到如下结果：

upload successful

可以看到双轴快排排序1亿数据耗时在9s左右，我们在排序算法（五）-双调排序中测过1亿数据情况下普通快速排序耗时大概在12s左右。

我们也可以测试大量数据，实际上，双轴快排效率是要优于普通快排的。

动图演示

下面视频演示了在一定数据量下的排序过程。

upload successful

其他注意事项

我们来分析下双轴快排的复杂度情况。

我们知道，对于递归，其时间复杂度公式如下：

T[n] = aT[n/b] + f(n)

我们对于普通快速排序，最好情况下，很容易得到其时间复杂度公式：

T[n] = 2T[n/2] + n

其中 T[n/2]为平分后的子数组的时间复杂度，n 是划分两部分数组所需要的时间。这个公式表示快排每次正好可以把序列分成两个相等的子序列。其中T[0] = T[1] = 1。

迭代求公式有可以得到时间复杂度如下：

upload successful

对于双轴快速排序，我们在最优情况下可以得到其时间复杂度公式：

T[n] = 3T[n/3]+n

其中 T[n/3]为平分后的子数组的时间复杂度，n 是划分两部分数组所需要的时间。这个公式表示快排每次正好可以把序列分成三个相等的子序列。其中T[0] = T[1] = 1。

迭代求公式有可以得到时间复杂度如下：

upload successful

可以看到双轴快速排序的时间复杂度也是O(n * log n)级别的。

双轴快速排序的时间复杂度：

时间复杂度（最好）：O(n * log n)
时间复杂度（平均）：O(n * log n)
时间复杂度（最差）：O(n^2)

对于空间复杂度，每次递归需要一定栈空间保存结果，其栈空间复杂度公式：

S[n] = 3S[n/3] + n

其中 T[n/3]为平分后的子数组的空间复杂度，n 是保存此层递归结果所需要的空间。这个公式表示快排每次正好可以把序列分成三个相等的子序列。其中T[0] = T[1] = 1。

根据这个公式可以得到双轴快排的栈空间复杂度是O(n * log n)级别的，但是双轴快排却不消耗堆空间，其堆空间复杂度为O(1)。

双轴快速排序的空间复杂度：

就地排序算法的空间复杂度为O(1)，如果考虑到递归调用占用系统资源，它的空间复杂度为O(n * log n)

双轴快速排序也是一种不稳定排序算法。

双轴快速排序为什么比普通快排要快

关于双轴快速排序有一篇论文 Why Is Dual-Pivot Quicksort Fast?，有兴趣的可以看一下。

论文中详细介绍了为什么相比普通快排，双轴快速排序要快。

论文中提到双轴快速排序的元素比较次数是要比普通快排要多的。

它们的比较次数比值大致如下：

DualPivotQuickSort vs QuickSort    =>    1.7043nlnn  vs  1.5697nlnn

一般排序算法中元素比较次数越多其耗费的时间越高，可是双轴快排却和普通快排呈现了两种不同的结果，这样理论与实验是相矛盾的。

论文作者提到在我们在排序时不仅要考虑元素比较次数，还应该考虑 CPU的速度，内存的速度，CPU和内存速度是否匹配 等的影响。

作者提出了“内存墙”问题：

据统计在过去的25年里面，CPU的速度平均每年增长46%, 而内存的带宽每年只增长37%，那么经过25年的这种不均衡发展，它们之间的差距已经蛮大了。假如这种不均衡持续持续发展，有一天CPU速度再增长也不会让程序变得更快，因为CPU始终在等待内存传输数据，这就是传说中内存墙(Memory Wall)。

同时给出了另一种比较排序算法优劣的方法：扫描元素个数算法。

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

为什么只算一次呢？因为在CPU高速缓存下，再次访问数组同一下标下的元素要比访问一个新的下标元素的时间少很多。（缓存级别vs内存级别）

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

在这种新算法下，作者计算的两种排序算法的扫描元素个数之比为：

DualPivotQuickSort vs QuickSort    =>    1.4035nlnn  vs  1.5697nlnn

也就是普通快排要比双轴快排多扫描了12%的元素，也相当于节约了大概12%的时间，在实际实验过程中来看，节约了10%左右的时间。

具体的计算过程可参考论文中的一些计算公式。

Java中的DualPivotQuicksort

在看这个问题之前，我们先来构造一个完全倒序的数组，比如1亿数据量，来测试DualPivotQuicksort。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
        int[] a = new int[100000000];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = 100000000 - i;
        }
        System.out.println("DualPivotQuicksort排序开始：");
        long start = System.currentTimeMillis();
        dualPivotQuickSort(a, 0, a.length - 1);
        System.out.println("DualPivotQuicksort耗时：" + (System.currentTimeMillis() - start) + "ms");
        System.out.println("DualPivotQuicksort排序完成！");
        System.out.println("数组是否有序：" + isOrdered(a));
    }

我们运行这个测试类，后面会等待很久然后出现栈溢出异常，原因很简单，这种情况下，双轴快排退化成冒泡排序（与普通快排类似），时间复杂度为O(n^2)。

这是我们无法忍受的。

作为一款优秀的排序算法，不仅要求其能适应最好情况和一般情况，更重要的是要其在最差情况下效率也要高效。更不用说如果作为一种语言的源代码的基础包里的部分了。

因此Java里的排序算法是有大量优化的。

我们在Java源代码中可以找到类 DualPivotQuicksort.java，它是Arrays.sort底层代码实现的一部分（另一部分是TimSort）,主要对于基本数据类型进行排序（不需要考虑稳定性）。

我们看到它是一种混合排序算法，而不单单是双轴快排。

其内部使用了插入排序、归并排序、双轴快速排序、单轴（普通）快速排序、计数排序等排序算法。

关于这个排序的分析我将在下篇文章介绍下。

总结

关于双轴排序算法的内容就聊到这儿，本文介绍了双轴快排的实现原理及一些特点。

在下篇文章里我会介绍下Java源代码里的DualPivotQuicksort，这个类由Vladimir Yaroslavskiy、Jon Bentley、Josh Bloch编写，是一个高效的排序算法。

源码

文中涉及到的程序代码详见我的 Github。

参考资料




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

您的支持就是我创作的动力！

欢迎关注我的其它发布渠道