前言

上篇文章我们讲到了双轴快速排序，今天我们来看下快排的另一种 - 三路快速排序（ThirdWayQuickSort），也称三向切分的快速排序。

正文

简介及原理

三路快速排序（ThirdWayQuickSort）是如何出现的呢？

我们知道，对于待排序数组，其数据是随机的，如果数组中有大量相同元素，无论普通快排还是双轴快排，由于快速排序的判定问题，会导致这些重复数移到一边从而大幅增加算法的运算时间。

为了优化这种数据情况，进而出现了三路快速排序。

三路快速排序也是采用一个轴值pivot，那具体是哪三路呢？

三路指的就是每分割（Partition）一次，三路排序会把数据分为小于pivot、等于pivot和大于pivot的三部分。

三路排序的大致原理如下：

对于待排序数组，选取第一个元素为中轴pivot；
每次分割处理将小于pivot的数据放到左边，等于pivot的数据放在中间，大于pivot的数据放在右边；
对小于pivot和大于pivot的部分重复分割过程。

我们以一个数组为例，来看下它的原理,如下图。

其算法描述如下：

对于待排序数组a，最左索引为left，最右索引为right；
排序过程中，以a[left]最为pivot，用i、j、k将数组分割为4部分，其中i表示pivot元素的起始index，所有小于pivot的元素下标都应该小于i；k表示待扫描的元素索引从i+1开始，到j结束；j表示待扫描元素的最后索引；
开始时i=left，k=left+1,j=right,此时小于pivot的元素为0个，大于pivot的元素为0个，待扫描的元素为j-k+1个；
从k开始扫描，当该元素比pivot小时，交换a[i]和a[k]，同时i++，k++，这样就能把该元素放到pivot的左边了；
当该元素等于pivot时，略过即可，即k++；
当该元素大于pivot时，需要把它放到右边，先看下a[j]和pivot的大小。
(1) 如果a[j] > pivot，显然它已经在右边了，我们只需j--即可；
(2) 如果a[j] = pivot，这时候我们需要交换a[k]和a[j]的位置，同时k++,j--即可；
(3) 如果a[j] < pivot，这时候我们除了交换a[k]和a[j]位置后，继续交换a[i]和a[k]的位置，将这个小元素移到左边，同时i++,j--,k++;
最后数据会被分为大于pivot、小于pivot、等于pivot的三部分，我们对大于pivot和小于pivot的部分再进行上述逻辑，直到传入的数据长度为1，说明数据全部有序了。

动图演示

代码实现

public class ThirdWayQuickSort {
    public static void quickSort3Way(int[] a, int left, int right) {
        //递归终止条件，少于等于一个元素的数组已有序
        if (left >= right) {
            return;
        }
        int i, j, k, pivot;
        //首元素作为中轴
        pivot = a[left];
        i = left;
        k = left + 1;
        j = right;

        outer:
        while (k <= j) {
            if (a[k] < pivot) {
                swap(a, i, k);
                i++;
                k++;
            } else if (a[k] == pivot) {
                k++;
            } else {// 遇到A[k]>pivot的情况，j从右向左扫描
                //A[j]>pivot的情况,j继续向左扫描
                while (a[j] > pivot) {
                    j--;
                    if (j < k) {
                        break outer;
                    }
                }
                //A[j]==pivot的情况
                if (a[j] == pivot) {
                    swap(a, k, j);
                    k++;
                    j--;
                } else {//A[j]<pivot的情况
                    swap(a, i, j);
                    swap(a, j, k);
                    i++;
                    k++;
                    j--;
                }
            }
        }
        //A[i, j] 等于 pivot 且位置固定，不需要参与排序
        // 对小于pivot的部分进行递归
        quickSort3Way(a, left, i - 1);
        // 对大于pivot的部分进行递归
        quickSort3Way(a, j + 1, right);
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    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(100000);
        }
        System.out.println("ThirdWayQuickSort排序开始：");
        long start = System.currentTimeMillis();
        quickSort3Way(a,0,a.length-1);
        System.out.println("ThirdWayQuickSort耗时："+(System.currentTimeMillis()-start)+"ms");
        System.out.println("ThirdWayQuickSort排序完成！");
        System.out.println("数组是否有序："+isOrdered(a));
    }
}

其他注意事项

三路快排的时间复杂度与快速排序相当：

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

三路快排的空间复杂度为O(n * log n) （递归消耗栈空间，是一种就地排序算法，如果从堆空间角度空间复杂度为O(1)）

三路快排也是一种不稳定排序算法。

相比普通快排和双轴快排，我们可以看到三路快排对于有重复数据的数组处理较佳，可以减少元素交换次数。

测试相关

我们来实际测试下，相关代码如下：

我们准备1亿数据，但是数据集范围为[0,10000)，这时候相同元素产生的就会比较多，我们分别测试下三路快排、双轴快排和普通快排。

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(10000);
    }
    int[] b = a.clone();
    int[] c = a.clone();

    System.out.println("ThirdWayQuickSort排序开始：");
    long start = System.currentTimeMillis();
    quickSort3Way(a,0,a.length-1);
    System.out.println("ThirdWayQuickSort耗时："+(System.currentTimeMillis()-start)+"ms");
    System.out.println("ThirdWayQuickSort排序完成！");
    System.out.println("数组是否有序："+isOrdered(a));

    System.out.println("DualPivotQuickSort排序开始：");
    long start1 = System.currentTimeMillis();
    DualPivotQuickSort.dualPivotQuickSort(b,0,b.length-1);
    System.out.println("DualPivotQuickSort耗时："+(System.currentTimeMillis()-start1)+"ms");
    System.out.println("DualPivotQuickSort排序完成！");
    System.out.println("数组是否有序："+isOrdered(b));

    System.out.println("QuickSort排序开始：");
    long start2 = System.currentTimeMillis();
    QuickSort.quickSort(c,0,c.length-1,true);
    System.out.println("QuickSort耗时："+(System.currentTimeMillis()-start2)+"ms");
    System.out.println("QuickSort排序完成！");
    System.out.println("数组是否有序："+isOrdered(c));
}

多次测试结果大致如下：

我们可以看到，当数据集重复元素较多时，三路快排确实有着比较优的排序效率。

我们将数据集范围改为[0,100)，效果更加明显。

1
2
3

for (int i = 0; i < a.length; i++) {
    a[i] = r.nextInt(100);
}

我们增大数据集范围，改为[0,100000000)，再来测试一下。

1
2
3

for (int i = 0; i < a.length; i++) {
    a[i] = r.nextInt(100000000);
}

可以看到三路快排效率比不上双轴快排了，因为这种情况下，重复元素较少，三路快排基本退化为普通快排。

总结

通过对三路快排（ThirdWayQuickSort）的介绍，我们大致了解了它的一些原理和排序过程，快速排序主要就有普通快排、三路快排和双轴快排三种。

在数据集元素重复较多的情况下，三路快排有着显著的优势，因此它和双轴快排一起，作为了Java对基本数据类型排序方法实现的一部分。

源码地址

本篇文章提到的所有代码均可见于我的GitHub。

SakuraTears的博客

排序算法（八） - 三路快速排序

前言

正文