信息奥赛｜快速排序

信息奥赛 C++ 排序 快速排序
信息奥赛知识点
发布日期:   2023-10-18
文章字数:   2.9k
阅读时长:   12 分
阅读次数:  

信息奥赛｜快速排序

知识点概览 🚀

  • 快速排序の简单介绍
  • 快速排序の编程框架
  • 快速排序の代码模版

知识点详解 🎥

简单介绍 ☘️

快速排序 是分治算法的应用之一，其时间复杂度可以到达 $O(nlogn)$

关于快速排序的具体思想，网上已经有许多优秀的博客，这里不再赘述，有需要的读者可以查看下面几篇推文：

快速排序详解：http://t.csdn.cn/v8Zul

摊主将在本文中阐述一些快速排序的学习心得与注意事项，供日后复习使用。

编程框架 🧑🏻‍💻

首先来看一下 快速排序的编程框架：

quicksort(int l,int r){
  if(l>=r) return;  //返回条件
  
  //快速排序每一趟流程
  1.选定当前序列的基准数(pivot)
  2.哨兵出动，交换序列值，直到找到基准点(两哨兵交汇处)
  3.将基准数归位至基准点(pivot_position)
    
  //二分，递归调用
  quicksort(l,pivot_position);
  quicksort(pivot_position+1,r);
}

对比 归并排序的编程框架：

mergesort(int l,int r){
  if(l>=r) return;  //返回条件
  
 	//二分，递归调用，先把两个子序列分别排好
  int mid = (l+r)/2;
  mergesort(l,mid);
  mergesort(mid+1,r);
  
  //将两个有序的子序列合并
  1.设定哨兵p1,p2，两个子序列元素不断比较，放入临时数组t中
  2.检查哨兵p1是否到末尾，将剩余元素依次放入t中
  3.检查哨兵p2是否到末尾，将剩余元素依次放入t中
  4.将临时数组t中的元素全部放入原序列中
}

可以看到，两者的共同点是 都有递归调用的过程，不同点是 递归调用的位置不同。快速排序 是先完成一趟排序，然后将序列二分；归并排序 则是先将序列二分，再将排序后的两个子序列合并。

虽然两者的编程框架看起来有些相似，但 实际的编程难度，快速排序会更难一些。

快速排序的难度提升，并不是指思想上的难度，而是快速排序在编程时，需要考虑的编程细节，如「等号条件」等较为繁琐。在快速排序的编程过程中，很容易出现「漏掉一个等号，排序就失败」的情况。

代码模版 🧑🏻‍💻

模版 1

该模版容易理解，但是非常容易超时。❌

void qsort(int a[], int l, int r) {
    if (l >= r) return;
    int pivot = a[l];  //基准数
    int i = l;  //选定左哨兵
    int j = r;  //选定右哨兵

    while (i < j) {
        while (a[j] >= pivot && i < j) j--;
        while (a[i] <= pivot && i < j) i++;
        if (i != j) swap(a[i], a[j]);  //交换当前不相同的哨兵值
    }
    swap(a[i], a[l]);  //循环结束后，哨兵值 i = j，为基准数a[l]最后的位置

    qsort(a, l, i - 1);
    qsort(a, i + 1, r);
}

模版 2（AcWing 版）

该模版相对不容易理解，但是不会超时。✅

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);  //经过实测，该模版中的j不能替换为i
}

边界值思考 🧐

结合快速排序的 C++ 源代码，思考下面的问题：

  1. 返回条件：if(l > r) return; 和 if(l >= r) return; 对程序造成的影响。
  2. 左哨兵的选择：p1 = a[l] 🆚 p1 = a[l+1] 对程序造成的影响。
  3. 在第一层 while 循环中，while(p1<p2) 🆚 while(p1<=p2) 对程序造成的影响。
  4. 在第二层 while 循环中，while (a[p2] >= pivot && p2 > p1) 🆚 while (a[p2] > pivot && p2 > p1) 对程序造成的影响。
  5. 在第二层 while 循环中，while (a[p2] >= pivot && p2 > p1) 🆚 while (a[p2] >= pivot && p2 >= p1) 对程序造成的影响。

C++ 源代码（基于模版1）

#include<bits/stdc++.h>
using namespace std;
int a[10005];
int n;

void quicksort(int l, int r);
void print();

int main() {
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    cout<<"before quick sort:";
    print();

    quicksort(1, n);

    cout<<"after quick sort: ";
    print();

    return 0;
}

void print() {
    for (int i = 1; i <= n; ++i) {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

void quicksort(int l, int r) {
    if (l > r) return;    //思考此处的条件，是否需要添加等号，如果不加，会有什么影响
    int tmp;
    int pivot = a[l]; //设定基准数
    int p1 = l;    //左哨兵初始位置在哪里，是l还是l+1
    int p2 = r;

    while (p1 < p2) {   //思考此处条件，是否需要添加 =，如果不添加，会有什么后果
        while (a[p2] >= pivot && p2 > p1) p2--;    //思考此处条件，两者是否需要添加等号
        while (a[p1] <= pivot && p2 > p1) p1++;

        if (p1 != p2) {
            tmp = a[p2];
            a[p2] = a[p1];
            a[p1] = tmp;
        }
    }
    a[l] = a[p1];
    a[p1] = pivot;

    quicksort(l, p1 - 1);
    quicksort(p1 + 1, r);
}

分析：

  1. 返回条件：if(l > r) return; 和 if(l >= r) return; 对程序 没有影响。
  2. 左哨兵必须选择 p1 = a[l] ✅ ，不能选择 p1=a[l+1] ❌ 。比如序列 6 7 10 9，如果左哨兵选择 7 ，那么两个哨兵在 7 相遇，7 和 6 换了位置，这是不对的。而左哨兵选择 6 ，两个哨兵会在 6 相遇，6 和自己换了位置（等于没换），才是正确的。
  3. 在第一层 while 循环中，while(p1<p2) ✅ while(p1<=p2) ❌ 。当两个哨兵相遇时，后者可能陷入死循环。
  4. 在第二层 while 循环中，while (a[p2] >= pivot && p2 > p1) ✅ while (a[p2] > pivot && p2 > p1) ❌ 。比如序列 6 2 1 7 5 6，如果不添加等号，右哨兵就会停留在最后一个 6 上，左哨兵一直停留在第一个 6 上，程序陷入死循环。
  5. 在第二层 while 循环中，while (a[p2] >= pivot && p2 > p1) ✅ while (a[p2] >= pivot && p2 >= p1) ❌ 。比如序列 6 7 8 9，添加等号后，右哨兵在回到第 1 个 6 的位置时，仍会执行 p1--，导致下标越界。

C++ 源代码（基于模版2）

Acwing 的 模版2 ，没有那么多等号条件要考虑，较为推荐。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int n;
int a[N];


//快速排序
void qsort(int l,int r){
    //返回条件
    if(l >= r) return ;
    
    //选定基准数，定义双指针
    int temp = a[ (l + r) >> 1 ];
    int i = l - 1, j = r + 1;
    
    //基本流程
    while( i < j ){
        do i++; while(a[i] < temp);
        do j--; while(a[j] > temp);
        if(i < j) swap(a[i],a[j]);
    }
    
    //递归
    qsort(l,j);
    qsort(j+1,r);
}

int main(){
    //读入数据
    cin>>n;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    
    //快速排序
    qsort(1,n);
    
    
    //输出结果
    for ( int i = 1; i <= n; i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    
    return 0;
}

🧑🏻‍💻 快速排序OI案例

OI 案例1

【题目描述】

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

【输入】

第 $1$ 行为一个正整数 $N$，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数，数据保证了 $A_i$ 不超过 $10^9$。

【输出】

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

【输入样例】
5
4 2 4 5 1
【输出样例】
1 2 4 4 5
【数据范围】

对于 $20%$ 的数据，有 $N\leq 10^3$；

对于 $100%$ 的数据，有 $N\leq 10^5$。

【原题链接】
【题目解析】

本题如果直接提交 模版1 程序，会有 3 个超时点 ❌

因此需要优化。

image-20221002111905046


先来看一些不需要对代码算法做改进的优化。

  • 优化方案1：将 输入输出流 改为 scanf/printf，实测该方法 失败，仍有 3 个超时点。❌

  • 优化方案2：添加优化语句，实测该方法 失败，仍有 3 个超时点（关于该优化的 相关技术博客）❌

int main(){
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
  ...
}
  • 优化方案3：手动开启O2优化，实测该方法 失败，编译错误。（洛谷不支持手动开启 O2优化）❌
#pragma GCC optimize(2)

image-20221002155829361

  • 优化方法4：在洛谷 OJ 上，勾选 开启O2优化，实测该方法生效，通过所有测试点。✅

image-20221002160201555

image-20221002160544907


再来看一些 基于快速排序本身算法思想的优化：

首先分析 快速排序的时间复杂度：

简单来说，快速排序是一种基于二分思想的算法，时间复杂度为 $O( nlogn )$

但是，当需要排序的数组，本身就有序，或者趋近于有序时，快速排序的时间复杂度会退化成 $O(n^2)$

具体数学推导可以看下面这一篇 技术博客的分析：

快速排序时间复杂度分析（最坏情况，最佳情况，平均情况）


基于以上对时间复杂度的分析，最终优化方案 如下：

  • 优化方案1：使用 random_shuffle(a+1,a+n+1) 将原数组打乱，该方案 部分奏效，但是仍有 1 个超时点。（PS：调用 1 次和调用 n 次 该代码进行打乱，最后 1 个超时点均存在）❌

image-20221002164504743

  • 优化方案2：使用 sort(a+1,a+n+1) ，直接 AC（不得不说，STL 真香）✅
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)	cin >> a[i];

    sort(a+1,a+n+1);  //STL大法真香
  
    for (int i = 1; i <= n; ++i)	cout << a[i] << " ";
    cout << endl;
    return 0;
}

image-20221002165815983

  • 优化方案3：在传统快速排序中，我们的基准点总是选择左边界，这使得像 6 5 4 3 2 1 这类数据，在递归时，quicksort(p1+1,r) 失效，程序并没有「二分」，速度大大降低。

所以我们 修改基准点的选择，改为 tmp = a[(l + r) / 2] （即 模版2），成功 AC ✅

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int n;
int a[N];


//快速排序
void qsort(int l, int r) {
    //返回条件
    if (l >= r) return;

    //选定基准数，定义双指针
    int temp = a[(l + r) >> 1];
    int i = l - 1, j = r + 1;

    //基本流程
    while (i < j) {
        do i++; while (a[i] < temp);
        do j--; while (a[j] > temp);
        if (i < j) swap(a[i], a[j]);
    }

    //递归
    qsort(l, j);
    qsort(j + 1, r);
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    //读入数据
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    //快速排序
    qsort(1, n);

    //输出结果
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

image-20221202094324541

刷题题单 🧑🏻‍💻

刷题题单与相应题解请见博客：信息奥赛题单｜快速排序🔗 / （备用）信息奥赛题单｜归并排序🔗

如链接失效，可以在文章末尾选择上一篇博客 或 在搜索界面搜索关键词「快速排序」即可。

参考资料 📚

文章作者: Rickyの水果摊
文章链接: https://ricky2333.github.io/2023/10/18/xin-xi-ao-sai-kuai-su-pai-xu/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Rickyの水果摊 !
信息奥赛 C++ 排序 快速排序
赏
  目录