双路快速排序

双路快速排序是快排的优化版。

双路快排的思想是，在待排序数组 [l, r] 的头和尾分别设置一个指针 i = l + 1 和 j = r，使得 arr[l+1...i) <= v；arr(j...r] >= v。这样可以使算法在待排序数组的左右两边同时推进。

问题：

为什么是 arr[l+1...i) <= v 而不是 arr[l...i) <= v？因为 l 被拿去用来做标定点 v 了。
为什么标定点两边都有等于 v 的元素？具体原因请看代码注释。

public class QuickSort2Ways {
    public void sort(Comparable[] arr) {
        int n = arr.length;

        quickSort2Ways(arr, 0, n - 1);
    }

    // 递归调用 quickSort2Ways，对 arr[l...r] 的范围进行排序
    private void quickSort2Ways(Comparable[] arr, int l, int r) {
        if (r <= l) return;

        int p = partition(arr, l, r);

        quickSort2Ways(arr, l, p - 1);
        quickSort2Ways(arr, p + 1, r);
    }

    // 返回 p，使得 arr[l...p-1] <= arr[p]，arr[p+1...r] >= arr[p]
    private int partition(Comparable[] arr, int l, int r) {
        // 考虑一个近乎有序的数组，如果只是简单的选择第一个元素作为标定点，那么分出的左右子数组长度就会严重不对等
        // 极端情况，对于一个有序的数组，排序二叉树就会退化成链表，时间复杂度由 logn 退化为 n^n
        // 优化措施就是，随机在 arr[l...r] 的范围中选择一个数值作为标定点
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);

        Comparable v = arr[l];

        // arr[l+1...i) <= v; arr(j...r] >= v，注意开区间
        int i = l + 1, j = r;

        while (true) {
            // 为什么标定点两边都有等于 v 的元素？为什么 arr[i].compareTo(v) < 0，而不是 <= 0
            // 因为如果对于一个**具有非常多相同元素**的待排序数组来说，如果进行 <= 0 比较，这会导致标定点 p 的左右部分严重失衡
            // 这样做可以让 arr[i].compareTo(v) == 0 的元素**随机**的分布在标定点 p 的左右部分，不至于失衡
            // 比如：待排序数组 [0,1,1,1,1,1,1]，选中 p = 1
            // 那么第一个 while 循环完成后，[l + 1 ... i) 已经包含整个数组了，严重失衡。
            while (i <= r && arr[i].compareTo(v) < 0) i++;

            while (j >= l + 1 && arr[j].compareTo(v) > 0) j--;

            if (i > j) break;

            swap(arr, i, j);

            i++;
            j--;
        }

        // 这里要交换 l 和 j 的值，而不是 i 的值
        // 因为，i 存在越界的可能。同理下面返回的也是 j 的值
        // 比如： 待排序数组：[1, 2, 3, 4]。选中 p = 4，那么进行完第一个 while 循环后，i = 4，越界了。
        swap(arr, l, j);

        return j;
    }

    private void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

public class QuickSort2Ways {
    public void sort(Comparable[] arr) {
        int n = arr.length;

        quickSort2Ways(arr, 0, n - 1);
    }

    // 递归调用 quickSort2Ways，对 arr[l...r] 的范围进行排序
    private void quickSort2Ways(Comparable[] arr, int l, int r) {
        if (r <= l) return;

        int p = partition(arr, l, r);

        quickSort2Ways(arr, l, p - 1);
        quickSort2Ways(arr, p + 1, r);
    }

    private int partition(Comparable[] arr, int l, int r) {
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);

        Comparable v = arr[l];

        int i = l + 1, j = r;

        while (true) {
            while (i <= r && arr[i].compareTo(v) < 0) i++;
            while (j >= l + 1 && arr[j].compareTo(v) > 0) j--;

            if (i > j) break;

            swap(arr, i, j);

            i++;
            j--;
        }

        swap(arr, l, j);

        return j;
    }

    private void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

另外，使用快速排序还可以解决「数组中的第 K 个最大元素」问题。

第 K 个最大元素，在升序排序的数组中对应的位置是 [len - K]，假设数组长度为 len。

partition 方法的返回值就是：partition 方法中的标定点 p 在当前排序好的数组中的位置。