排序：快速排序

1 思路

假设对数组data进行排序，如果能够对data以元素v分割成左右两部分，

• 对于左边所有元素都比v小，
• 对于右边所有元素都比v要大。

那么只要我们不断的递归对左右两个子数组进行相同的过程，最终数组就都会有序。

快速排序

2 实现

因此，首先需要考虑的是，如何对一个数组进行分割？
如果我们要分割数组data[l, r]中的元素，首先需要选定一个标定点：这里我们选择最左边(l)的元素：
那么我们可以使用变量i循环遍历data[l+1, r]的区间，如果遇到比v小的，那么我们就放到j+1的位置，同时j要自增1，以表示<v的部分进行了扩容。如下图所示，操作i和j的目的是不断的缩小未处理部分，同时给<v和>=v的部分扩容。需要注意的是，需要考虑=v的元素，我们将其放在了右边部分。

partition过程

当整个未处理部分未空时，此时，我们只需要交换v和j处的元素，即完成了分割，分割方法实现如下：

// 将data[l, r]划分为三部分data[l, j-1]、data[j]、data[p+1, r]，其中，data[l, j-1]所有元素都比data[j]小，data[j+1, r]所有元素都比data[j]要大
private static <E extends Comparable<E>> int partition(E[] data, int l, int r) {
    E v = data[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (data[i].compareTo(v) < 0) {
            j++;
            Utils.swap(data, i, j);
        }
    }
    Utils.swap(data, l, j);
    return j;
}

已经有了分割方法，接下来实现递归，思路如下：

• 对数组以v进行分割
• 对<v的子数组进行排序
• 对>=v的子数组进行排序
• 递归之

实现代码如下：

public static <E extends Comparable<E>> void sort(E[] data) {
    if (data == null || data.length <= 1) {
        return;
    }

    sort(data, 0, data.length - 1);
}

// 宏观语义：该函数的功能用于对数组data的区间[l, r]进行排序
private static <E extends Comparable<E>> void sort(E[] data, int l, int r) {
    // 最简单的情况
    if (l >= r) {
        return;
    }

    // 先解决更小的问题
    int p = partition(data, l, r);
    sort(data, l, p - 1);
    sort(data, p + 1, r);
}

3 有序数组的退化

有序数组会使快排退化为O(n^2)的复杂度，这是因为，当数组有序的时候，每次partition后，左半区间将为空，而右半区间将为除v外的所有元素，这就违背了一分为二的分治思想，树的层次将由O(logn)变为了O(n)层。
解决的办法是，随机选择数组中的一个元素作为v，然后和第0个元素交换位置。

// 将data[l, r]划分为三部分data[l, j-1]、data[j]、data[p+1, r]，其中，data[l, j-1]所有元素都比data[j]小，data[j+1, r]所有元素都比data[j]要大
private static <E extends Comparable<E>> int partition(E[] data, int l, int r, Random random) {
    int p = random.nextInt(r - l + 1) + l;
    Utils.swap(data, l, p);
    
    E v = data[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (data[i].compareTo(v) < 0) {
            j++;
            Utils.swap(data, i, j);
        }
    }
    Utils.swap(data, l, j);
    return j;
}

4 双路快排

上面的算法还是有问题，当所有元素都相等时，还是会出现退化为O(n^2)复杂度的问题。这是因为，我们总是把等于v的元素都放到右边，因此还是会出现左半区间将为空，而右半区间将为除v外的所有元素这种情况。解决方法是把=v的元素分散在左右两半空间，具体思想如图示：

双路排序

做一些解释：

• 我们需要遍历的是未处理部分的区间，并将该区间的元素分散到左右两个区间中，该区间用[i, j]表示。
• 向后遍历i，一旦data[i]>=v的元素停止遍历
• 向前遍历j，一旦data[j]<=v的元素停止遍历
• i的起始值为l+1，此时未处理部分为除第l个元素的所有元素；终止值>j，此时表示没有未处理部分了。
• j的初始值为r；终止值为<i，此时表示没有未处理部分了。
• 如果，i和j处的元素需要交换，交换i和j处的元素。

private static <E extends Comparable<E>> int partition2(E[] data, int l, int r, Random random) {
    int p = random.nextInt(r - l + 1) + l;
    Utils.swap(data, l, p);
    int i = l + 1;
    int j = r;
    while (true) {
        while (i <= j && data[i].compareTo(data[l]) < 0) {
            i++;
        }
        while (j >= i && data[j].compareTo(data[l]) > 0) {
            j--;
        }
        if (i >= j) {
            break;
        }
        Utils.swap(data, i, j);
        i++;
        j--;
    }
    Utils.swap(data, l, j);
    return j;
}

5 复杂度分析

对于双路算法来说，其实还是存在某种情况，每次随机取得的值刚好可以使算法退化到O(n^2)，但这样的概率非常小，可以忽略不记；对于算法复杂度分析，有下面三条原则：

• 如果能找到一组数据能使算法100%恶化，此时是普通算法，看最差情况，例如单路排序。
• 如果没有一组数据能使算法100%恶化，此时是随机算法，看期望，例如双路排序。
• 如果算法中间会有多次调用，可以尝试均摊分析，例如数组的扩容

6 三路快排

如果一个数组中存在大量相同的元素，其实在遍历的时候就可以辨别出来，那么在partition过程中，就可以把那部分数据都放在中间，再一次递归就可以少递归很多元素，其大致思想如下图：

三路快排

做如下解释：

• 将数组分为五个部分，v, <v的部分，=v的部分，未处理部分，>v的部分
• 循环遍历未索引部分，由i来表示，如果i处的元素<v，则和lt后面的元素进行交换，扩容<v的部分，i后挪
• 如果i的元素>v，则和gt前面的元素进行交换，此时，由于交换到i处的元素还未被考察，因此i不变，gt需要向前挪
• i的终止条件是>=gt还要大，则表示没有可考察的元素了，未处理部分未空

private static <E extends Comparable<E>> void sort3ways(E[] data, int l, int r, Random random) {
    // 最简单的情况
    if (l >= r) {
        return;
    }

    int lt = l, gt = r + 1, i = l;
    // 维持循环不变量：data[l+1, lt] < v, data[lt+1, i-1]=v, data[gt, r]>v
    while (i < gt) {
        if (data[i].compareTo(data[l]) < 0) {
            lt++;
            Utils.swap(data, lt, i);
            i++;
        } else if (data[i].compareTo(data[l]) > 0) {
            gt--;
            Utils.swap(data, gt, i);
        } else {
            i++;
        }
    }
    Utils.swap(data, l, lt);
    //此时，data[l, lt-1] < v, data[lt, i-1]=v, data[gt, r]>v
    sort3ways(data, l, lt - 1, random);
    sort3ways(data, gt, r, random);
}