快排算法

快速排序的思路

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p + 1, hi)

快速排序的partition方式

一种是Lomuto partition scheme，另外一种是Hoare partition scheme。

Lomuto partition

This scheme is attributed to Nico Lomuto and popularized by Bentley in his book

lomuto的partition实现方式

i指示最前面的大于pivot的元素位置，j从前往后滑动来调整元素位置。每次j碰到小于pivot的元素，则swap i位置的元素和j位置的元素，再i指向下一个大于pivot的元素。
最后，记得swap i位置的元素和最末尾的元素。

private int lomutoPartition(int nums[], int lo, int hi) {
        int pivot = nums[hi];
        int i = lo;
        for (int j = lo; j < hi; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }

        swap(nums, i, hi); // replace the guard element
        return i;
    }

Hoare partition scheme

The original partition scheme described by C.A.R. Hoare uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion.

Hoare’s scheme is more efficient than Lomuto’s partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.

hoare的partition实现方式

i从前往后找到大于pivot的元素，j从后往前找到小于pivot的元素，然后两者swap.

private int hoarePartition(int nums[], int lo, int hi) {
        int pivot = nums[lo];
        int i = lo, j = hi;
        while (true) {
            while (nums[i] < pivot) {
                i++;
            }

            while (nums[j] >= pivot) {
                j--;
            }

            if (i >= j) {
                return j;
            }

            swap(nums, i, j);
        }
    }