public class QuickSort {

    public static void sort(Comparable[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    /**
     * 递归对 arr[left...right] 排序
     *
     * @param arr   数组
     * @param left  左边界
     * @param right 右边界
     */
    private static void sort(Comparable[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(arr, left, right);  // 【< segment，segment，> segment】
        sort(arr, left, p - 1);               // 处理【< segment】部分
        sort(arr, p + 1, right);              // 处理【> segment】部分
    }

    /**
     * 对 arr[left...right] 进行 partition
     *
     * @param arr   数组
     * @param left  左边界
     * @param right 右边界
     */
    private static int partition(Comparable[] arr, int left, int right) {
        // 选基准：此处每次选择最左边的元素
        Comparable base = arr[left];

        // arr[left+1...segment] < base ；arr[segment+1...i) > base
        int segment = left;   // j 是小于基值和大于基值的分界点
        for (int i = left + 1; i <= right; i++) { // arr ==> 【segment，< segment，> segment】
            // 对于比基准值小的值，放在segment所在的位置，segment索引递增
            if (arr[i].compareTo(base) < 0) {
                segment++;
                Comparable temp = arr[i];
                arr[i] = arr[segment];
                arr[segment] = temp;
            }
        }
        // 结束之后，将 base 放到 segment 位置
        // 【segment，< segment，> segment】 ==> 【< segment，segment，> segment】
        Comparable temp = arr[segment];
        arr[segment] = arr[left];
        arr[left] = temp;

        // 返回基准值所在的索引
        return segment;
    }
}