排序算法之：快速排序（Quick Sort）的分区优化与尾递归消除

题目描述

快速排序是一种基于“分治”策略的高效排序算法，其核心步骤是“分区”（Partition）。标准快速排序在最坏情况下（如数组已排序）时间复杂度会退化到 O(n²)，并且递归深度可能达到 O(n)，有栈溢出风险。本题目要求深入理解快速排序的经典实现，并在此基础上，优化分区过程以处理数组中存在大量重复元素的情况，同时通过尾递归消除来优化递归深度，确保最坏情况下的栈空间复杂度为 O(log n)。

解题过程

1. 快速排序基础与经典分区算法

快速排序的思路是：

1. 分区：从数组中选择一个元素作为“基准”（pivot）。将所有小于基准的元素移到基准左边，大于基准的移到右边。分区结束后，基准就位于其最终排序后的正确位置。
2. 递归：递归地对基准左右两边的子数组进行同样的操作。

经典实现：Lomuto 分区方案
Lomuto 分区简单直观，通常选取最右侧元素作为基准：

1. 初始化一个指针 i，指向“小于基准的区域”的末尾（初始为 low-1）。
2. 遍历数组从 low 到 high-1 的元素（j 为当前遍历指针）。
3. 如果当前元素 arr[j] <= 基准，则 i 右移一位，并交换 arr[i] 和 arr[j]。
4. 遍历结束后，将基准（arr[high]）与 arr[i+1] 交换，此时基准位于索引 i+1 处，并返回此索引。

int partition_Lomuto(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

问题：当数组包含大量等于基准的元素时，Lomuto分区会将这些元素全部放到一侧，导致分区不平衡，递归树倾斜，效率降低。

2. 分区优化：三路分区（Dutch National Flag Problem）

为了高效处理重复元素，我们引入三路分区。它将数组划分为三个部分：

• < pivot 区域：arr[low ... lt-1]
• == pivot 区域：arr[lt ... gt]
• > pivot 区域：arr[gt+1 ... high]

算法步骤（以 arr[low] 为基准）：

1. 初始化三个指针：lt = low（小于区域的右界），gt = high（大于区域的左界），i = low + 1（当前检查元素）。
2. 当 i <= gt 时循环：
   a. 如果 arr[i] < pivot，交换 arr[i] 和 arr[lt]，然后 lt++, i++。
   b. 如果 arr[i] > pivot，交换 arr[i] 和 arr[gt]，然后 gt--。（注意：i 不增加，因为交换过来的 arr[gt] 还未检查）
   c. 如果 arr[i] == pivot，i++。
3. 循环结束后，lt 指向第一个等于基准的元素，gt 指向最后一个等于基准的元素。递归时，只需要对 < pivot 区域 (low, lt-1) 和 > pivot 区域 (gt+1, high) 进行排序，中间相等区域已就位。

pair<int, int> partition_ThreeWay(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int lt = low;     // 最终指向“等于区域”的左边界
    int gt = high;    // 最终指向“等于区域”的右边界
    int i = low + 1;
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[lt], arr[i]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            swap(arr[i], arr[gt]);
            gt--;
        } else { // arr[i] == pivot
            i++;
        }
    }
    return {lt, gt}; // 返回等于区域的左右边界
}

3. 递归优化：尾递归消除

标准递归形式是对分区后的左右两个子数组都进行递归调用。这可能导致递归深度在最坏情况下（如每次分区都极不平衡）达到 O(n)。

尾递归消除思想：
递归调用发生在函数末尾。我们可以手动管理“待处理”的子数组区间，而不是依靠递归栈。具体做法是，每次分区后，我们只对较小的那个子数组进行递归调用，而对较大的子数组，通过更新循环变量，在下一次循环中处理。这确保了递归栈的深度永远不会超过 O(log n)。

优化后的快速排序主函数：

void quickSort_Optimized(vector<int>& arr, int low, int high) {
    while (low < high) { // 使用循环代替一部分递归
        // 1. 进行三路分区
        pair<int, int> bounds = partition_ThreeWay(arr, low, high);
        int left_end = bounds.first - 1;  // 小于区域的右边界
        int right_start = bounds.second + 1; // 大于区域的左边界

        // 2. 尾递归消除：先递归排序较小的子数组
        if ((left_end - low) < (high - right_start)) {
            // 左子数组更小，先排它
            quickSort_Optimized(arr, low, left_end);
            // 更新 low，在下一轮循环中排右子数组
            low = right_start;
        } else {
            // 右子数组更小（或相等），先排它
            quickSort_Optimized(arr, right_start, high);
            // 更新 high，在下一轮循环中排左子数组
            high = left_end;
        }
        // 注意：等于区域 (bounds.first 到 bounds.second) 已有序，无需处理
    }
}

原理：我们总是保证递归调用发生在较小的子数组上。由于每次递归调用处理的数组大小至少减半（因为我们总是先处理较小的那部分，而较小部分的长度不超过原数组的一半），所以递归的最大深度被限制在 O(log n)。对于另一部分较大的子数组，我们通过修改 low 或 high 参数，在函数返回后由外层的 while 循环继续处理，这模拟了递归但并未增加栈深度。

总结

通过结合三路分区和尾递归消除，我们对经典快速排序进行了重要优化：

1. 三路分区：有效处理了含有大量重复元素的数组，避免了因重复元素导致的分区不平衡，在重复元素多的情况下性能显著优于经典分区。
2. 尾递归消除：将最坏情况下的递归栈深度从 O(n) 降低到 O(log n)，避免了在大数据量或极端输入下栈溢出的风险，同时保持了算法的平均 O(n log n) 时间复杂度。

这个优化版本是工程实践中常用且高效的快速排序实现之一。