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

【以无克有】排序之随机快速排序

article 2025/2/19 16:08:45

分治就是：抽刀断水水更流，举杯消愁愁更愁

文章目录

快速排序原理(最常见的双端扫描思路)
- 原理讲解
- 代码实现
- - 分区(Partition)部分：
  - 递归排序部分：
复杂度简要分析
例题
- 随机快速排序模板
- 快排应用之第k小数(不去重)
参考资料及推荐
总结

快速排序原理(最常见的双端扫描思路)

原理讲解

分治策略：拆解问题的艺术
快速排序的核心是分治法，即“分而治之”。想象你要给全班同学按身高排序，如果直接比较所有人会很麻烦。于是你选出一个“基准同学”，让比他矮的站左边，高的站右边。这样一来，大问题就拆成了两个小问题——只需分别给左右两边的队伍排序即可。
关键操作：基准选择与分区:
- 选基准（Pivot）
  这个基准相当于划分队伍的“标尺”，选数组第一个或最后一个元素或位于中间的元素（《算法导论》基础版本的做法）。比如选最后一个同学的身高作为基准，但实际应用中通常采用随机选择数组中的某元素的优化策略。
- 分区（Partition）
  这是快速排序的精华步骤。你需要通过两指针像“夹击”一样调整数组：左指针从起点向右扫描，寻找比基准大的元素。右指针从终点向左扫描，寻找比基准小的元素。当两指针找到不满足条件的元素时，交换它们的位置，直到两指针相遇。此时，基准的正确位置就确定了——左边全比它小，右边全比它大。
递归处理：化整为零
分区完成后，对左右两个子数组重复上述过程，直到每个子数组只剩一个或零个元素（递归终止条件）。就像把大队伍不断分成小队，直到每个小队已经自然有序，无需再分。

代码实现

分区(Partition)部分：

这里笔者提供两个思路，一个是leetcode上的模板，另一个是让deepseek评判出来的较优写法

//力扣版
int partition(int* arr, int l, int r) {
    // 随机选择枢轴：避免最坏情况时间复杂度
    int pivot = arr[l + rand() % (r - l + 1)];
    // 初始化指针i和j为区间外，后续通过do-while先移动再判断
    int i = l - 1, j = r + 1; //注意并非l与r
    while (i < j) { // 循环直到指针相遇或交叉
        do i++; while (arr[i] < pivot); // 从左找第一个≥pivot的元素
        do j--; while (arr[j] > pivot); // 从右找第一个≤pivot的元素
        if (i < j) swap(arr[i], arr[j]); // 交换并继续循环
    }
    return j; // 返回分界点j，后续递归区间为[l, j]和[j+1, r]
}

//deepseek版
int partition(int* arr, int l, int r) {
    // 随机选择枢轴（与力扣版相同）
    int pivot = arr[l + rand() % (r - l + 1)];
    // 初始化指针i和j为区间端点（而非区间外）
    int i = l, j = r;
    while (i <= j) { // 循环条件允许i和j相等
        while (arr[i] < pivot) i++; // 从左找第一个≥pivot的元素
        while (arr[j] > pivot) j--; // 从右找第一个≤pivot的元素
        if (i <= j) { // 允许i和j相等时交换
            swap(arr[i], arr[j]);
            i++; // 交换后移动指针，避免重复比较
            j--;
        }
    }
    return j; // 返回分界点j，后续递归区间为[l, j]和[j+1, r]
}

递归排序部分：

//用递归树的思路来理解：
//1.根节点对应初始数组，通过partition将数组分为左（≤基准值）、右（≥基准值）两段，基准值定位到最终位置j。
//2.子树生成：递归处理左区间[l,j]和右区间[j+1,r]，形成左右子树分支。
//3.叶子节点：当区间长度≤1（l≥r）时终止递归，确保底层无子节点。
void quick_sort(int* arr,int l,int r)
{
    if(l >= r) return;
    int j = partition(arr,l,r);
    quick_sort(arr,l,j);
    quick_sort(arr,j+1,r);
}

复杂度简要分析

快速排序的整体时间复杂度由递归深度和每次分区的成本共同决定：
最好情况：
每次分区都能将数组均匀划分为两部分（例如基准元素选择为中位数），此时递归深度为 O(log n) ，每层分区总操作次数为 O(n) 。总时间复杂度为 O(n log n) 。例子：对随机无序数组进行排序，且每次分区基准选择合理即选择到了中位数。
最坏情况：
每次分区极度不平衡（例如数组已完全有序且基准固定选择首元素），此时由于选择的不合理每次只减少一个元素，所以每层分区总操作次数增加到了 O(n) ，递归深度退化为 O(n) ，总时间复杂度为 O(n²) 。例子：对已升序排列的数组使用快速排序，且基准始终选择第一个元素。
平均情况：
假设分区大致平衡（例如通过随机化或三数取中法优化基准选择），递归深度仍为 O(log n) ，总时间复杂度保持 O(n log n)。

例题

随机快速排序模板

例题：P1177 【模板】排序

#include <bits/stdc++.h>
using namespace std;

void quick_sort(int *arr, int l, int r)
{
    if (l >= r) return;
    int base = arr[l + rand() % (r-l+1)], i = l, j = r; // 因为java源码的实现中有pivot变量使用很多人喜欢用pivot表示base，pivot支点感觉并不比base基准表述得更形象
    while (i <= j)
    {
        while (arr[i] < base) i++;
        while (arr[j] > base) j--;
        if (i <= j)
        {
            swap(arr[i], arr[j]);
            i++;j--; // 防止两个相同值死循环
        }
    }
    quick_sort(arr, l, j);
    quick_sort(arr, i, r);
}

int main()
{
    int m;
    cin >> m;
    int *xp = (int *)malloc(m * sizeof(int));
    for (int i = 0; i < m; ++i)
    {
        cin >> xp[i];
    }
    quick_sort(xp, 0, m - 1);
    for (int i = 0; i < m; ++i)
    {
        cout << xp[i] << " ";
    }
}

快排应用之第k小数(不去重)

例题：P1923 【深基9.例4】求第 k 小的数

#include <bits/stdc++.h>
using namespace std;

int partition(int* arr,int l,int r)
{
    int pivot = arr[l + rand()%(r-l+1)],i=l-1,j=r+1;
    while(i < j)
    {
        do i++;while(arr[i] < pivot);
        do j--;while(arr[j] > pivot);
        if(i < j) swap(arr[i],arr[j]);
    }
    return j;
}

int quick_select(int* arr,int l,int r,int k)
{
    if(l >= r) return arr[l];
    int j = partition(arr,l,r);
    int left_len = j - l + 1;
    if(k < left_len) return quick_select(arr,l,j,k);
    else return quick_select(arr,j+1,r,k-left_len);
}   


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin >> n >> k;
    int* arr = (int*)malloc(n*sizeof(int));
    for(int i=0;i<n;++i) cin >> arr[i];
    cout << quick_select(arr,0,n-1,k)  << endl;
    free(arr);

    return 0;
}