1.1 原理

  快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。

  设要排序的数组是，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

  快速排序最重要的操作就是分区（Partition），我们用下图来描述该过程。
  先说明图中变量的意义：
  v：指的是关键数据；
  l：指数组的第一个元素的索引；
  j：指小于关键数据 v 的数组的最后一个元素的索引；
  i：指当前遍历的元素 e 的索引；

image.png

image.png

1.2 代码

public class QuickSort {
    // 用于记录 partition 操作的次数
    private static int count = 0;

    public static void main(String[] args) {
        int[] array = {3, 9, 1, 4, 2, 7, 8, 6, 5};
        int length = array.length;
        sort(array, 0, length - 1);
    }

    private static void sort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(array, left, right);
        sort(array, left, p - 1);
        sort(array, p + 1, right);
    }

    /**
     * 对 array[left, right] 部分进行分区 (partition) 操作
     *
     * @param array
     * @param left  数组的起始索引
     * @param right 数组的结束索引
     * @return 返回值为 p, 使得 array[left, p - 1] < array[p] < array[p + 1, right]
     */
    private static int partition(int[] array, int left, int right) {
        count++;
        int v = array[left];
        int j = left;
        // array[left + 1, j] < v, 初始状态时 j = left, 那么 array[left + 1, left] 是不存在的，保证了边界有效性
        // array[j + 1, i) > v, 右侧取开区间, 初始状态时 i = left + 1, 那么 array[left + 1, left + 1) 是不存在的，也保证了边界有效性
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < v) {
                swap(array, j + 1, i);
                j++;
            }
        }
        swap(array, left, j);
        System.out.println("第 " + count + " 次分区的结果: " + Arrays.toString(array));
        return j;
    }

    private static void swap(int[] array, int a, int b) {
        if (a == b) {
            return;
        }
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

    第 1 次分区的结果: [2, 1, 3, 4, 9, 7, 8, 6, 5]
    第 2 次分区的结果: [1, 2, 3, 4, 9, 7, 8, 6, 5]
    第 3 次分区的结果: [1, 2, 3, 4, 9, 7, 8, 6, 5]
    第 4 次分区的结果: [1, 2, 3, 4, 5, 7, 8, 6, 9]
    第 5 次分区的结果: [1, 2, 3, 4, 5, 7, 8, 6, 9]
    第 6 次分区的结果: [1, 2, 3, 4, 5, 6, 7, 8, 9]

1.3 时间复杂度

• 最坏情况划分：当划分产生的两个子问题分别包含了个元素和个元素，那么复杂度为。也就是说，在这种情况下，快速排序算法的运行时间并不比插入排序更好。此外，当输入数组已经完全有序时，快速排序的时间复杂度仍然为。
• 最好情况划分：当划分产生的两个子问题的规模都不大于，那么复杂度为。
• 通常我们认为快速排序的平均复杂度为。

========================== 优化 ==========================

一、随机化快速排序

  上面已经提到了普通快速排序法的最差时间复杂度是在有序或近乎有序的素组中发生，为什么会这样？因为有序会导致每次partition递归操作都没有比关键数据小的子数组。那么，它整个的递归树的高度是(假设数组有个元素)，可以得出公式：

image.png

  既然已经知道了原因，对于有序或近乎有序数组来说，就不能取第一个元素（因为它最小）作为关键数据了，而是采用随机的方式在数组中选取一个元素作为关键数据，这时快速排序的期望时间复杂度为，因为它退化成的可能性是随着的值越大就变得越小。从概率学角度来分析，第一次 partition 取到最小元素的概率为，第二次取到最小元素的概率为，... 依次类推，每次都取到最小元素的概率是，当足够大的时候概率几乎为。

    private static int randomPartition(int[] array, int left, int right) {
        count++;
        int random = (int) (Math.random() * (right - left) + left);
        swap(array, left, random);
        int v = array[left];
        int j = left;
        // array[left + 1, j] < v, 初始状态时 j = left, 那么 array[left + 1, left] 是不存在的，保证了边界有效性
        // array[j + 1, i) > v, 右侧取开区间, 初始状态时 i = left + 1, 那么 array[left + 1, left + 1) 是不存在的，也保证了边界有效性
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < v) {
                swap(array, j + 1, i);
                j++;
            }
        }
        swap(array, left, j);
        System.out.println("第 " + count + " 次分区的结果: " + Arrays.toString(array));
        return j;
    }
    第 1 次分区的结果: [1, 2, 9, 4, 3, 7, 8, 6, 5]
    第 2 次分区的结果: [1, 2, 3, 4, 9, 7, 8, 6, 5]
    第 3 次分区的结果: [1, 2, 3, 4, 5, 6, 8, 9, 7]
    第 4 次分区的结果: [1, 2, 3, 4, 5, 6, 7, 8, 9]