洛谷笔记 - P1177 【模板】快速排序

发表于 更新于 本文字数： 588 阅读时长 ≈ 2 分钟

复健 ing…

快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法 (Divide-and-ConquerMethod)。

该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
—— 菜鸟教程

题目描述

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

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

输入格式

第 11 行为一个正整数 NN，第 22 行包含 NN 个空格隔开的正整数 aia_i，为你需要进行排序的数，数据保证了 AiA_i 不超过 10910^9。

输出格式

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

样例 #1

样例输入 #1

1
2
5
4 2 4 5 1

样例输出 #1

1
1 2 4 4 5

提示

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//P1177 【模板】快速排序
//https://www.luogu.com.cn/problem/P1177

//https://www.luogu.com.cn/record/83564299 RE*4 不幸地把数组大小看错了
//https://www.luogu.com.cn/record/83564342 AC

#include<iostream>
using namespace std;
int n,a[100001];
void swap(int x,int y){
    int tmp=a[x];
    a[x]=a[y];
    a[y]=tmp;
}
void quicksort(int h,int e){
    int j=a[(e+h)/2],x=h,y=e; //中位数、头、尾
    while(x<=y){
        while(a[x]<j) x++;
        while(a[y]>j) y--;
        if(x<=y){ //左右正常顺序排好后找不符合左右大小规律的数互换位置
            swap(x,y);
            x++;y--; //继续正常查找排序过程
        }
    }
    //此处循环结束后，左右部分分割
    if(h<y) //左半部分排序
        quicksort(h,y);
    if(x<e) //右半部分排序
        quicksort(x,e);
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    quicksort(1,n);
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
    return 0;
}