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

复健ing…

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是： 1．先从数列中取出一个数作为基准数。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。 ——菜鸟教程

题目描述

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

5
4 2 4 5 1

样例输出 #1

1 2 4 4 5

提示

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

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

代码

//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;
}