排序算法入门（二）：快速排序 —— 分区、基准与 O(n log n) 的平均性能

import java.util.Arrays;

public class QuickSort {

    public static void sort(int[] a) {
        if (a == null || a.length < 2) {
            return;
        }
        quickSort(a, 0, a.length - 1);
    }

    private static void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;                        // 区间里只剩 0 或 1 个元素，天然有序
        }
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);           // 基准已经归位，递归时必须把它排除在外，
        quickSort(a, p + 1, hi);           // 否则每次分区都切出 n-1 个元素，区间不收敛
    }

    /** Lomuto 分区：把 a[hi] 当基准，返回基准归位后的下标 */
    private static int partition(int[] a, int lo, int hi) {
        int pivot = a[hi];
        int i = lo;                        // i 是"小于基准区"的下一个空位
        for (int j = lo; j < hi; j++) {
            if (a[j] < pivot) {            // 严格小于：等于基准的元素留在右半区，
                swap(a, i, j);             // 它们本来也不用挪，交换次数因此少一半
                i++;
            }
        }
        swap(a, i, hi);                    // 基准换到小于区和大于区之间，这里就是它的最终位置
        return i;
    }

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

    public static void main(String[] args) {
        int[] a = {5, 1, 4, 2, 8, 3};
        sort(a);
        System.out.println(Arrays.toString(a));   // [1, 2, 3, 4, 5, 8]
    }
}

    /** Hoare 分区：以区间中间元素为基准，返回左右两半的分界点 */
    private static int hoarePartition(int[] a, int lo, int hi) {
        int pivot = a[lo + ((hi - lo) >>> 1)];   // 先把基准的值取出来，后面的交换动不了它
        int i = lo - 1;
        int j = hi + 1;
        while (true) {
            do { i++; } while (a[i] < pivot);    // 停在第一个不小于基准的元素上
            do { j--; } while (a[j] > pivot);    // 停在第一个不大于基准的元素上
            if (i >= j) {
                return j;                        // 指针交叉，本轮分区结束
            }
            swap(a, i, j);
        }
    }

    /** 配套递归：分界点 j 不是基准的位置，所以右半边从 j+1 开始 */
    private static void hoareSort(int[] a, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = hoarePartition(a, lo, hi);
        hoareSort(a, lo, j);       // 写成 (lo, j-1) 会漏元素，甚至让区间不再缩小而死循环
        hoareSort(a, j + 1, hi);
    }

    // 用到 ThreadLocalRandom，需要 import java.util.concurrent.ThreadLocalRandom;

    /** 三数取中：把 lo、mid、hi 三个位置排好序，再取中间那个当基准 */
    private static void medianOfThreeToEnd(int[] a, int lo, int hi) {
        int mid = lo + ((hi - lo) >>> 1);   // 不用 (lo + hi) / 2，避免大下标相加溢出
        if (a[lo] > a[mid]) swap(a, lo, mid);
        if (a[lo] > a[hi])  swap(a, lo, hi);
        if (a[mid] > a[hi]) swap(a, mid, hi);
        swap(a, mid, hi);                   // 三次交换后 a[mid] 是中位数，换到右端给 Lomuto 用
    }

    /** 随机基准：让最坏情况的输入无法被提前构造出来 */
    private static void randomPivotToEnd(int[] a, int lo, int hi) {
        if (hi - lo < 2) {
            return;                         // 两三个元素的区间上，随机数生成比比较本身还贵
        }
        int r = lo + ThreadLocalRandom.current().nextInt(hi - lo + 1);
        swap(a, r, hi);
    }

    /** 先递归较短的一边，较长的一边用循环摊平：栈深度锁死在 O(log n) */
    private static void quickSortBounded(int[] a, int lo, int hi) {
        while (lo < hi) {
            int p = partition(a, lo, hi);
            if (p - lo < hi - p) {    // 左半更短：左半真正递归，右半留到下一轮循环
                quickSortBounded(a, lo, p - 1);
                lo = p + 1;
            } else {                  // 右半更短，反过来处理
                quickSortBounded(a, p + 1, hi);
                hi = p - 1;
            }
        }
    }