快速排序

定义

>[!tip] 快速排序（Quick Sort）基本思想： 采用经典的分治策略，选择数组中某个元素作为基准数，通过一趟排序将数组分为独立的两个子数组，一个子数组中所有元素值都比基准数小，另一个子数组中所有元素值都比基准数大。然后再按照同样的方式递归的对两个子数组分别进行快速排序，以达到整个数组有序。

快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程如下图所示。

流程

哨兵划分（分治）

1. 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
2. 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
3. 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。 [

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 ≤ 基准数 ≤ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。

快速排序的分治策略 哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。

def partition(self, nums: list[int], left: int, right: int) -> int:
    """哨兵划分"""
    # 以 nums[left] 为基准数
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1  # 从右向左找首个小于基准数的元素
        while i < j and nums[i] <= nums[left]:
            i += 1  # 从左向右找首个大于基准数的元素
        # 元素交换
        nums[i], nums[j] = nums[j], nums[i]
    # 将基准数交换至两子数组的分界线
    nums[i], nums[left] = nums[left], nums[i]
    return i  # 返回基准数的索引

递归

快速排序的整体流程如图所示。

1. 首先，对原数组执行一次“哨兵划分”，得到未排序的左子数组和右子数组。
2. 然后，对左子数组和右子数组分别递归执行“哨兵划分”。
3. 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

/* 快速排序 */
quickSort(nums, left, right) {
    // 子数组长度为 1 时终止递归
    if (left >= right) return;
    // 哨兵划分
    const pivot = this.partition(nums, left, right);
    // 递归左子数组、右子数组
    this.quickSort(nums, left, pivot - 1);
    this.quickSort(nums, pivot + 1, right);
}

算法特性

• 时间复杂度为 O(nlog⁡n)、非自适应排序：在平均情况下，哨兵划分的递归层数为 log⁡n ，每层中的总循环数为 n ，总体使用 O(nlog⁡n) 时间。在最差情况下，每轮哨兵划分操作都将长度为 n 的数组划分为长度为 0 和 n−1 的两个子数组，此时递归层数达到 n ，每层中的循环数为 n ，总体使用 O($n^2$) 时间。
• 空间复杂度为 O(n)、原地排序：在输入数组完全倒序的情况下，达到最差递归深度 n ，使用 O(n) 栈帧空间。排序操作是在原数组上进行的，未借助额外数组。
• 非稳定排序：在哨兵划分的最后一步，基准数可能会被交换至相等元素的右侧。

快速排序为什么快

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。

• 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 O$(n^2$) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 O($nlogn$) 的时间复杂度下运行。
• 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
• 复杂度的常数系数小：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

基准数优化

快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为 n−1、右子数组长度为 0 。如此递归下去，每轮哨兵划分后都有一个子数组的长度为 0 ，分治策略失效，快速排序退化为“冒泡排序”的近似形式。

为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。

需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至$O(n^2)$ 的概率大大降低。

示例代码如下：

/* 选取三个候选元素的中位数 */
medianThree(nums, left, mid, right) {
    let l = nums[left],
        m = nums[mid],
        r = nums[right];
    // m 在 l 和 r 之间
    if ((l <= m && m <= r) || (r <= m && m <= l)) return mid;
    // l 在 m 和 r 之间
    if ((m <= l && l <= r) || (r <= l && l <= m)) return left;
    return right;
}

/* 哨兵划分（三数取中值） */
partition(nums, left, right) {
    // 选取三个候选元素的中位数
    let med = this.medianThree(
        nums,
        left,
        Math.floor((left + right) / 2),
        right
    );
    // 将中位数交换至数组最左端
    this.swap(nums, left, med);
    // 以 nums[left] 为基准数
    let i = left,
        j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
        this.swap(nums, i, j); // 交换这两个元素
    }
    this.swap(nums, i, left); // 将基准数交换至两子数组的分界线
    return i; // 返回基准数的索引
}

尾递归优化

在某些输入下，快速排序可能占用空间较多。 以完全有序的输入数组为例，设递归中的子数组长度为 m ，每轮哨兵划分操作都将产生长度为 0 的左子数组和长度为 m−1 的右子数组，这意味着每一层递归调用减少的问题规模非常小（只减少一个元素），递归树的高度会达到 n−1 ，此时需要占用 O(n) 大小的栈帧空间。

为了防止栈帧空间的累积，我们可以在每轮哨兵排序完成后，比较两个子数组的长度，仅对较短的子数组进行递归。由于较短子数组的长度不会超过 n/2 ，因此这种方法能确保递归深度不超过 log⁡n ，从而将最差空间复杂度优化至 $O(logn)$ 。代码如下所示：

/* 快速排序（尾递归优化） */
quickSort(nums, left, right) {
    // 子数组长度为 1 时终止
    while (left < right) {
        // 哨兵划分操作
        let pivot = this.partition(nums, left, right);
        // 对两个子数组中较短的那个执行快速排序
        if (pivot - left < right - pivot) {
            this.quickSort(nums, left, pivot - 1); // 递归排序左子数组
            left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
        } else {
            this.quickSort(nums, pivot + 1, right); // 递归排序右子数组
            right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}

完整快排

踩坑

>[!error] 踩坑注意 在快速排序的 partition 方法中，内部循环中移动指针 i 和 j 的顺序对算法的正确性和效率有重要影响。 应当满足j先移动，i再移动

两种循环顺序的对比

第一种顺序

while (i < j && nums[i] <= nums[left]) {
    i++;   // 从左向右找首个大于基准数的元素
}
while (i < j && nums[j] >= nums[left]) {
    j--;  // 从右向左找首个小于基准数的元素
}

• 步骤：
  1. 首先，从左向右移动指针 i，找到第一个大于基准值 nums[left] 的元素。
  2. 然后，从右向左移动指针 j，找到第一个小于基准值 nums[left] 的元素。
  3. 如果 i < j，交换 nums[i] 和 nums[j]。

第二种顺序

while (i < j && nums[j] >= nums[left]) {
    j--;  // 从右向左找首个小于基准数的元素
}
while (i < j && nums[i] <= nums[left]) {
    i++;  // 从左向右找首个大于基准数的元素
}

• 步骤：
  1. 首先，从右向左移动指针 j，找到第一个小于基准值 nums[left] 的元素。
  2. 然后，从左向右移动指针 i，找到第一个大于基准值 nums[left] 的元素。
  3. 如果 i < j，交换 nums[i] 和 nums[j]。

影响分析

1. 指针移动顺序的影响：

   • 第一种顺序（i 先移动）：
     • 可能会导致指针 i 和 j 在某些情况下越过彼此，从而引发错误的交换或无限循环。
     • 例如，当数组中存在多个等于基准值的元素时，指针 i 可能会移动得过远，导致 j 不足够及时移动，最终可能导致基准值未正确放置。
   • 第二种顺序（j 先移动）：
     • 遵循标准的 Hoare 分区算法，这种顺序更能确保在指针交汇前完成所有必要的交换。
     • 先移动 j 可以确保先找到右侧需要移动的元素，再移动 i，减少错位交换的可能性。

2. 标准 Hoare 分区算法的顺序：

   • 在经典的 Hoare 分区算法中，通常是先移动 j，然后移动 i。这是因为 j 先移动可以更快地找到需要交换的右侧元素，确保分区的正确性。
   • 这种顺序在实践中被证明更为稳定，尤其是在处理包含大量重复元素的数组时。

为什么顺序不同会导致问题？

• 一致性和标准化：

  • 标准的 Hoare 分区算法是先移动 j，然后移动 i。这种顺序确保了在找到需要交换的元素时，指针 j 已经定位到右侧需要交换的较小元素，而指针 i 定位到左侧需要交换的较大元素，从而保证交换后的数组部分更加有序。

• 避免错误交换：

  • 如果先移动 i，可能会导致指针 i 过度移动，导致 j 无法及时找到需要交换的较小元素，或者在某些情况下导致 i 和 j 交叉，影响分区的正确性。

• 递归深度和效率：

  • 正确的分区顺序有助于更均匀地划分数组，减少递归深度，提升排序效率，避免栈溢出等问题。

推荐的分区实现

为了确保快速排序算法的正确性和效率，建议采用标准的 Hoare 分区顺序，即先移动 j，然后移动 i。以下是修正后的 partition 方法示例：

/* 标准 Hoare 分区算法 */
static int partition(int[] nums, int left, int right) {
    // 1. 确定基准数
    int baseIndex = medianThree(nums, left, (right + left) / 2, right);  // 选取三个候选元素的中位数
    swap(nums, left, baseIndex); // 将中位数交换至数组最左端
    int pivot = nums[left]; // 基准值

    int i = left - 1;
    int j = right + 1;

    while (true) {
        // 从右向左找到第一个小于等于 pivot 的元素
        do {
            j--;
        } while (nums[j] > pivot);

        // 从左向右找到第一个大于等于 pivot 的元素
        do {
            i++;
        } while (nums[i] < pivot);

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

        swap(nums, i, j);
    }
}

完整的修正代码示例

结合上述建议，以下是修正后的完整快速排序代码：

import java.util.Arrays;

public class JavaLearning {

    /* 元素交换 */
    static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /* 选取三个候选元素的中位数 */
    static int medianThree(int[] nums, int left, int middle, int right) {
        int l = nums[left];
        int m = nums[middle];
        int r = nums[right];

        if((l <= m && m <= r) || (r <= m && m <= l)) {
            return middle;
        }
        if((m <= l && l <= r) || (r <= l && l <= m)) {
            return left;
        }
        return right;
    }

    /* 标准 Hoare 分区算法 */
    static int partition(int[] nums, int left, int right) {
        // 1. 确定基准数
        int baseIndex = medianThree(nums, left, (right + left) / 2, right);  // 选取三个候选元素的中位数
        swap(nums, left, baseIndex); // 将中位数交换至数组最左端
        int pivot = nums[left]; // 基准值

        int i = left - 1;
        int j = right + 1;

        while (true) {
            // 从右向左找到第一个小于等于 pivot 的元素
            do {
                j--;
            } while (nums[j] > pivot);

            // 从左向右找到第一个大于等于 pivot 的元素
            do {
                i++;
            } while (nums[i] < pivot);

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

            swap(nums, i, j);
        }
    }

    /* 快速排序（使用标准 Hoare 分区） */
    static void quickSort(int[] nums, int left, int right) {
        while (left < right) {
            // 哨兵划分操作
            int pivot = partition(nums, left, right);

            // 递归排序较小的子数组，迭代排序较大的子数组
            if (pivot - left < right - pivot) {
                quickSort(nums, left, pivot);
                left = pivot + 1;
            } else {
                quickSort(nums, pivot + 1, right);
                right = pivot;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {11, 2, 33, 4, 55, 6, 77, 8, 99, 10};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}

测试结果

使用修正后的代码，运行结果应为：

[2, 4, 6, 8, 10, 11, 33, 55, 77, 99]

总结

• 循环顺序的重要性：在快速排序的 partition 方法中，先移动 j 再移动 i 的顺序更符合标准的 Hoare 分区算法，有助于确保算法的正确性和稳定性。
• 标准化实现：遵循经典算法的实现顺序和逻辑，可以减少错误，提高代码的可维护性和可靠性。
• 调试与验证：在实现分区逻辑时，建议通过具体的例子进行手动跟踪，确保每一步都符合预期，从而避免潜在的逻辑错误。

如果在修正后仍然遇到问题，建议进一步检查其他部分的实现逻辑，或者使用调试工具逐步跟踪算法的执行过程，以确保每一步都按预期进行。