当前位置：首页 > article >正文

快速排序不啦不啦

article 2025/3/31 17:15:51

一、快速排序基本思想

想象你有一堆杂乱的书需要按编号排列。快速排序的做法是：
1️⃣ 随便选一本书作为"基准书"
2️⃣ 把比它小的放左边，比它大的放右边
3️⃣ 对左右两堆书重复这个过程

二、代码逐行解析

1. 随机数生成

int getRand(int min, int max) {
    return (rand() % (max - min + 1)) + min;
}

作用：生成[min,max]范围内的随机数
类比：闭着眼睛从书堆里随机摸一本书

2. 核心排序逻辑

void quick_sort(int arr[], int low, int high) {
    if(low >= high) return; // 终止条件：只剩一本书时不需要整理

    // 🎯 随机选基准书
    int t_id = getRand(low, high);
    int tmp = arr[t_id];
    
    // 📌 初始化两个"整理员"
    int i = low-1;  // 左整理员（从最左边开始往右走）
    int j = high+1; // 右整理员（从最右边开始往左走）

    while(i < j) {
        // 👉 右整理员找小书
        while(arr[--j] > tmp); // 一直往左走，直到找到比基准小的书
        
        // 👈 左整理员找大书
        while(arr[++i] < tmp); // 一直往右走，直到找到比基准大的书

        if(i < j) swap(arr[i], arr[j]); // 交换两本放错位置的书
    }

    // ✂️ 分割成左右两堆继续整理
    quick_sort(arr, low, j);    // 整理左边小书堆
    quick_sort(arr, j+1, high); // 整理右边大书堆
}

三、动态演示

假设要排序数组 [3,1,4,2,5]，随机选中3作为基准：

步骤1️⃣：整理员开始工作

初始状态：i=-1, j=5
[3,1,4,2,5]
 ↑       ↑

右整理员j找到2（比3小） → j=3
左整理员i找到4（比3大） → i=2
交换后：[3,1,2,4,5]

继续循环：
右整理员j移动到1 → j=1
左整理员i移动到4 → i=3
此时i>j，循环结束

步骤2️⃣：分割区间

分割点j=1 → 左区间[0,1]，右区间[2,4]
继续递归处理左右区间

四、关键点解释

为什么要随机选基准？

如果总是选第一个元素，遇到已排序数组时效率会退化成O(n²)。随机选择能避免最坏情况。

i和j的移动顺序

--j 先移动再判断：避免死循环
++i 先移动再判断：保证每次循环都有进展

循环终止条件

当i和j相遇或交叉时（i >= j），说明分区完成

五、存在的问题

当所有元素相同时（如全2），每次只能确定一个元素的位置，时间复杂度退化为O(n²)。解决方法：

+ 使用三路快排，将数组分为 <、=、> 三部分
+ 遇到重复元素时直接跳过中间区域

六、性能对比

情况	平均时间复杂度	最坏时间复杂度
普通快排	O(nlogn)	O(n²)
三路快排	O(nlogn)	O(nlogn)

逐步解释：

普通的快速排序在最坏情况下（例如所有元素完全相同）仍然会出现 O(n²) 的时间复杂度。以下是详细分析：

一、问题根源

当数组中所有元素相同时，代码的分区逻辑会失效：

每次分区只能确定一个元素的位置
假设数组为 [2,2,2,2,2]：
- 随机选择基准后，i 和 j 会在首尾相遇
- 分区后左区间为整个数组，右区间为空
- 每次递归只能排除一个元素（基准本身）

递归深度变为 O(n)
导致总操作次数为：

n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 → O(n²)

二、代码验证

以全为 2 的数组 [2,2,2,2,2] 为例：

第一次分区
- i 从 low-1=-1 开始右移，直到 i=4（越界）
- j 从 high+1=5 开始左移，直到 j=0
- 分区后：左区间 [0,0]，右区间 [1,4]
递归右区间 [1,4]
重复上述过程，每次只能排除一个元素。

三、解决方法

使用 三路快速排序 优化重复元素处理：

将数组分为三部分
- < pivot、= pivot、> pivot
跳过重复元素区域
递归时只需处理 < 和 > 的部分。

四、三路快排核心代码

void quick_sort(int arr[], int low, int high) {
    if (low >= high) return;

    // 随机选择基准并交换到low位置
    int t_id = getRand(low, high);
    swap(arr[low], arr[t_id]);
    int pivot = arr[low];

    // 三路分割初始化
    int lt = low;      // 最后一个小于pivot的位置 (less than)
    int gt = high;     // 第一个大于pivot的位置 (greater than)
    int i = low + 1;   // 当前遍历指针

    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[i], arr[lt]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            swap(arr[i], arr[gt]);
            gt--;
        } else {
            i++;
        }
    }

    // 递归处理左右区域
    quick_sort(arr, low, lt - 1);  // 处理 < 部分
    quick_sort(arr, gt + 1, high); // 处理 > 部分
}