⚡ 快速排序 (Quick Sort)

归档: #Algorithm #Sorting #Advanced

核心心法: "分而治之" —— 选个老大划清界限，左边都是小弟，右边都是大哥。

🧠 核心思想 (前序遍历)

快排的本质是二叉树的前序遍历。

1. 选基准 (Pivot)：随机挑一个数。
2. 切分 (Partition)：把比基准小的扔左边，比基准大的扔右边。
3. 递归 (Recursion)：对左右两边重复上述过程，直到只剩一个元素。

🎨 图解演示

点击“开始排序”体验分治过程

45

0

12

1

89

2

34

3

76

4

23

5

56

6

4

7

90

8

67

9

15

10

88

11

33

12

72

13

50

14

95

15

20

16

8

17

62

18

40

19

基准

小于基准

大于基准

已排序

💻 代码实现 (C++ 随机化版)

 1. 指针交换法 
// 也叫 "左右指针法"
// 核心思路：左右互找，找到不符合规则的就交换
class Solution {
public:
    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        
        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }

    int partition(vector<int>& nums, int left, int right) {
	    
	    // 🎲 随机选一个位置，跟最左边交换 
	    int randIdx = left + rand() % (right - left + 1); 
	    swap(nums[left], nums[randIdx]);
	    
        int pivot = nums[left]; // 选最左为基准
        int i = left + 1;
        int j = right;

        while (true) {
            // i 向右找比 pivot 大的
            while (i <= j && nums[i] <= pivot) i++;
            // j 向左找比 pivot 小的
            while (i <= j && nums[j] > pivot) j--;

            if (i >= j) break;
            
            // 找到了就交换
            swap(nums[i], nums[j]);
        }
        
        // 最后把基准换到分界点
        swap(nums[left], nums[j]);
        return j;
    }
};

2.挖坑法
// 核心思路：不用 swap，而是把数直接填入“坑”里
// 也就是：右边的数填左边的坑，左边的数填右边的坑
class Solution {
public:
    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        
        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[left]; // 把最左边的数拿出来，left 位置变成了"坑"
        
        while (left < right) {
            // 1. 右指针向左找比 pivot 小的数
            while (left < right && nums[right] >= pivot) right--;
            
            // 找到了！填到左边的"坑"里，现在 right 变成了新"坑"
            nums[left] = nums[right];
            
            // 2. 左指针向右找比 pivot 大的数
            while (left < right && nums[left] <= pivot) left++;
            
            // 找到了！填到右边的"坑"里，现在 left 变成了新"坑"
            nums[right] = nums[left];
        }
        
        // 循环结束时 left == right，这里是最后的坑，把 pivot 填进去
        nums[left] = pivot;
        return left;
    }
};

💡 核心对比

方法	操作特点	适用场景
指针交换法	swap 交换 (3次赋值)	推荐。逻辑直观，左右两边对着跑，也是 STL 的主流实现思路。
挖坑法	直接覆盖 (1次赋值)	经典。少了一点赋值开销，理解起来像填空游戏，不容易死循环。
随机化	先随机换头	防坑。解决 [1,2,3,4,5] 这种有序数组导致的 问题。

📊 复杂度分析

维度	数值	说明
时间 (平均)		每次切分都减半
时间 (最差)		每次都选到最大/最小值 (随机化可避免)
空间		递归栈的深度
稳定性	❌ 不稳定	远距离交换破坏顺序

💡 适用场景

• 通用排序：C++ std::sort、Java Arrays.sort (基本类型) 的底层核心。

• 数组排序首选：在内存足够的情况下，它是最快的通用排序。