深刻理解快速排序

「理解快速排序」的关键在于理解它「分区」的过程。

下面以数组 [4, 1,?5,?3,?6,?2,?7,?8] 为例分析分区的过程。

假设数字 3 被随机选中称为中间值，该数字被交换到数组的尾部。接下来初始化两个指针，指针 P1?初始化至下标为 -1 的位置，指针 P2?初始化至下标为 0 的位置，如「图a」所示。「始终」将指针 P1?指向已经发现的「最后一个」小于 3 的数字。此时尚未发现任何一个小于 3 的数字，因此将指针 P1 指向一个无效的位置。将指针 P2 从下标为 0 的位置开始向右扫描数组中的每个数字。当指针 P2?指向第 1 个小于 3 的数字 1 时，指针 P1?向右移动一格，然后交换两个指针指向的数字，此时数组（即两个指针）的状态如「图b」所示。继续右移指针 P2?直到遇到下一个小于 3 的数字 2，指针 P1?再次向右移动一格，然后交换两个指针指向的数字，此时数组（即两个指针）的状态如「图c」所示。继续右移指针 P2?直到指向数字 3 也没有遇到新的小于 3 的数字，此时整个数组都已经扫描完毕。再次将指针 P1?向右移动一格，然后交换指针 P1?和 P2?指向的数字，于是所有小于 3 的数字都位于 3 的左边，所有大于 3 的数字都位于数组的右边，如「图d」所示。

附上 Java 代码：

public class MyQuicksort {
    /**
     * quicksort - 快排
     */
    private void quicksort(int[] nums, int start, int end) {
        if (end > start) {
            // pivot 为分区完成的下标值（分区 - 目标值左边的数字都小于它，目标值右边的数字都大于它）
            int pivot = partition(nums, start, end);
            // 分治思想，继续分别分区左右边的数组
            quicksort(nums, start, pivot - 1);
            quicksort(nums, pivot + 1, end);
        }
    }

    /**
     * partition - 分区
     * 选取一个随机下标，并把小于和大于的数值分区
     * 分区 - 目标值左边的数字都小于目标值，目标值右边的数字都大于目标值
     */
    private int partition(int[] nums, int start, int end) {
        // 随机一个下标并放置到数组末尾（随机的时间复杂度较平均）
        int random = new Random().nextInt(end - start + 1) + start;
        swap(nums, random, end);

        // small 为 p1 指针的下标。
        // * p1 指针始终指向已经发现的最后一个小于目标值的数字
        int small = start - 1;
        // i 为 p2 指针下标，遍历找到小于目标的数字后，p1 指针前移并交换。使小于目标值的都分区在左边
        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                small++;
                swap(nums, small, i);
            }
        }

        // p2 指针遍历完成后，所有小于目标值的数组都在 p1 指针及其左边，此时 p1 指针右移并与目标值交换达成目的
        small++;
        swap(nums, start, end);

        return small;
    }

    /**
     * 交换两个下标的值
     */
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}