快速排序实现代码及其优化

快速排序

快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。

快速排序可以和归并排序类比着看，加深印象：

快速排序

两个子数组如果有序，整个数组也有序了；

递归调用位置在处理数组之后；

切分（partition）的位置取决于数组的内容

归并排序

将数组分为两个子数组排序；

递归调用位置在处理数组之间；

数组被等分成两半

快速排序的思路

选择一个切分元素，根据这个切分元素将数组切分成两半，左边小于等于该元素，右边大于等于该元素，并范围切分点坐标。

根据切分点坐标，划分左右子数组，并递归在子数组中进行排序。

代码实现

《算法4》书中的实现方式（双指针）：

    public void quickSort(int[] a) {
        quickSort0(a, 0, a.length - 1);
    }

    private void quickSort0(int[] a, int lo, int hi) {
        if (lo >= hi)
            return;

        int index = partition0(a, lo, hi);

        quickSort0(a, lo, index - 1);
        quickSort0(a, index + 1, hi);
    }

    private int partition0(int[] a, int lo, int hi) {
        // 选择基准点
        int v = a[lo];
        int i = lo;
        int j = hi + 1;
        while (true) {
            while (a[++i] <= v)
                if (i == hi)
                    break;
            while (a[--j] >= v)
                if (j == lo)
                    break;
            // 当两个指针相遇的时候，j指向的是左子数组的最右侧（是小于基准点的）
            if (i >= j)
                break;
            // swap 是自己写的一个方法，实现起来很简单。限于篇幅，这里就省略一下。
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }

挖坑填数法：

    private void sort(int[] nums, int l, int h) {
        if (l >= h) {
            return;
        }
        // 先进行partition，得到下标
//        int rIndex = random.nextInt(r - l) + l + 1;
        int lo = l, hi = h, key = nums[l];
        while (lo < hi) {
            while (lo < hi && nums[hi] >= key) {
                --hi;
            }
            nums[lo] = nums[hi];
            while (lo < hi && nums[lo] <= key) {
                ++lo;
            }
            nums[hi] = nums[lo];
        }
        nums[lo] = key;
        sort(nums, l, lo - 1);
        sort(nums, lo + 1, h);
    }

快速排序的特点

空间复杂度：O(n)

时间复杂度：O(nlogn)

稳定性：不稳定。

优点：不需要外部空间（只需要很小的递归栈），时间复杂度是 O(nlogn)。快速排序的内循环非常短小，理论和实际上速度都非常快。

缺点：比较脆弱。很多种情况会导致性能只有平方级别。因此需要对快速排序进行优化。

快速排序的优化

递归到小数组时，切换到插入排序

对于小数组，快速排序比插入排序慢

因为递归，在小数组中，快速排序的 sort 方法也会调用自己

    // 快速排序的优化
    // 1. 在小数组的时候，使用插入排序
    public static void sort11(int[] a) {
        sort1(a, 0, a.length - 1);
    }

    private static int M = 5;

    private static void sort1(int[] a, int lo, int hi) {
        // 如果是小数组，则使用插入排序
        if (lo + M >= hi) {
            InsertionSort.sort(a, lo, hi);
            return;
        }
        // parition 函数的实现这里就不赘述了
        int index = partition(a, lo, hi);
        sort1(a, lo, index - 1);
        sort1(a, index + 1, hi);
    }

三取样切分，对数组取样三份，然后选取中位数。

对于倒序的数组，此方法可以极大提高效率

    private static int partition2(int[] a, int lo, int hi) {
        // 这里的基准点 v 暂时先不赋值
        int i = lo, j = hi + 1, v;
        v = mediumPos(a, lo, hi);
        ...
    }

// 三取样，并且将中位数交换到 lo 位置
    private static int mediumPos(int[] a, int lo, int hi) {
        int mid = (lo + hi) / 2;

        if (a[mid] > a[hi])
            swap(a, mid, hi);
        if (a[lo] > a[hi])
            swap(a, lo, hi);
        // 经过上面两步，a[hi] 是最大值
        if (a[mid] > a[lo])
            swap(a, mid, lo);
        // 经过上面一步，a[lo] 就是中位数
        return a[lo];
    }

将数组简单化为三部分，分别是小于、等于、大于切分元素的数组元素

该方式对于数组中有大量重复元素的时候，非常高效

    private static void sort3(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int lt = lo, curr = lo+1, gt = hi, v = a[lo];
        while (curr <= gt) {
            if (a[curr] < v) {
                swap(a, lt++, curr++);
            } else if (a[curr] > v) {
                swap(a, curr, gt--);
            } else {
                curr++;
            }
        }
        // 此时坐标 lt 的左边都是小于当前基准点的
        // 此时坐标 gt 的右边都是大于当前基准点的
        // 剩下的 [lt, gt] 则是刚好等于基准点的数据
        sort3(a, lo, lt - 1);
        sort3(a, gt + 1, hi);
    }

快速排序的应用 - 快速选择

数组中只有三种类型的数据（或三种范围的数据），则可以使用三个指针进行 三路快排。

Sort Colors

        public void sortColors(int[] nums) {
            // l 坐标的左边都是0， r 坐标的右边都是2，curr是移动的指针（当前操作）
            int l = 0, r = nums.length - 1, curr = 0;
            while (curr <= r) {
                if (nums[curr] == 0) {
                    swap(nums, curr++, l++);
                } else if (nums[curr] == 2) {
                    swap(nums, curr, r--);
                } else {
                    curr++;
                }
            }

        }

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