原地实现快速排序

概念回顾

快速排序是一种基于分治思想的排序算法，其核心在于选择一个基准值（pivot），将数组划分为两部分，使得左侧元素均小于基准值，右侧元素均大于基准值，然后递归地对两部分继续排序。

“原地”快速排序特指在划分过程中不借助额外数组（如“小于区间数组”“大于区间数组”），而是在原数组上通过交换完成元素重排。严格意义上，它的空间复杂度仅来自递归调用栈，为 $O(\log n)$ （平均情况）。

原地快排的核心思想

关键在于原地分区。即在一个区间 [l, r] 内，通过指针移动与元素交换，使数组满足：

[l, pivot_index - 1] < pivot
[pivot_index + 1, r] > pivot

而无需开辟额外存储空间。

实现原地分区的主流方法有两类：

Hoare Partition（双指针逼近）
Lomuto Partition（单指针扫描）

工程中更常用 Hoare 版本，因为交换次数更少、性能更稳定。

实现思路（Hoare Partition）

选取区间起点作为基准值 pivot = nums[l]，然后定义两个指针：

i：从左向右移动
j：从右向左移动

执行过程：

从右侧开始，找到第一个 < pivot 的元素
从左侧开始，找到第一个 > pivot 的元素
交换这两个元素
重复上述过程，直到 i >= j
最后将 pivot 放到正确位置（通常与 j 交换）

该过程保证：

左边全部 ≤ pivot
右边全部 ≥ pivot

C++实现

#include <vector>
using namespace std;

class QuickSort {
public:
    void sort(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
    }

private:
    void quickSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;

        int pivot = nums[l];
        int i = l, j = r;

        while (i < j) {
            // 从右往左找小于 pivot 的
            while (i < j && nums[j] >= pivot) j--;
            // 从左往右找大于 pivot 的
            while (i < j && nums[i] <= pivot) i++;
            if (i < j) swap(nums[i], nums[j]);
        }

        // 将 pivot 放到正确位置
        swap(nums[l], nums[i]);

        quickSort(nums, l, i - 1);
        quickSort(nums, i + 1, r);
    }
};

JavaScript实现

function quickSort(nums, l = 0, r = nums.length - 1) {
    if (l >= r) return;

    let pivot = nums[l];
    let i = l, j = r;

    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        while (i < j && nums[i] <= pivot) i++;
        if (i < j) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }

    [nums[l], nums[i]] = [nums[i], nums[l]];

    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}

算法分析

时间复杂度取决于分区是否均衡：

平均情况：每次划分接近对半 $→$ 时间复杂度为 $O(n \log n)$
最坏情况：数组已有序且每次选到极值 $→$ 时间复杂度退化为 $O(n^2)$

空间复杂度：

不使用额外数组，属于原地排序
递归调用栈深度：
- 平均： $O(\log n)$
- 最坏： $O(n)$

工程细节与优化点

在实际实现中，单纯的原地快排仍存在性能波动，需要注意以下问题：

首先是基准选择。如果始终选择区间端点（如 nums[l]），在接近有序数组时会退化。通常采用“随机选择”或“三数取中”降低最坏情况概率。

其次是小区间优化。当子数组规模较小时（如 ≤ 16），改用插入排序可以减少递归开销并提升缓存命中率。

最后是尾递归优化。通过手动改写递归结构，使递归深度控制在 $O(\log n)$ ，避免栈溢出。

整体而言，原地快排的本质优势在于空间效率高 + 常数因子小，因此在工程实践中仍是高性能排序的核心实现方式之一。