洛谷 P1177 【模板】快速排序【13种排序模版】

P1177 【模板】快速排序

题目描述

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

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

输入输出格式

输入格式：

输入文件sort.in的第1行为一个正整数N，第2行包含N个空格隔开的正整数a[i]，为你需要进行排序的数，数据保证了A[i]不超过1000000000。

输出格式：

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

输入输出样例

输入样例#1：

5
4 2 4 5 1

输出样例#1：

1 2 4 4 5

说明

对于20%的数据，有N≤1000；

对于100%的数据，有N≤100000。

题目链接：https://www.luogu.org/problem/show?pid=1177

下面给出几种排序方法：

1.松式基排

所谓普通基排，就是以65536为底，用位运算，把一个数拆成两部分，要循环两遍

松式基排，就是以256为底，用位运算把一个数拆成四部分，要循环四遍

为什么松式基排在WC的时候会更快呢，因为这样的话cnt数组刚好能装进L1高速缓存

下面给出如下代码：

 #include <cstring>
 #include <cstdio>
 #include <algorithm>
 using namespace std;
 const int MAXN = ;
 const int BIT = ;
 const int U = ;
 int n, a[MAXN];
 inline int getd( int x, int d ) {
     return (x>>(d*BIT))&(U-);
 }
 int cnt[U], b[MAXN];
 void radix_sort() {
     int *x = a, *y = b;
     for( int d = ; d < ; ++d ) {
         for( int i = ; i < U; ++i ) cnt[i] = ;
         for( int i = ; i < n; ++i ) ++cnt[getd(x[i],d)];
         for( int i = ; i < U; ++i ) cnt[i] += cnt[i-];
         for( int i = n-; i >= ; --i ) y[--cnt[getd(x[i],d)]] = x[i];
         swap(x,y);
     }
     for( int i = ; i < n; ++i ) printf( "%d ", x[i] );
 }
 int main() {
     scanf( "%d", &n );
     for( int i = ; i < n; ++i ) scanf( "%d", a+i );
     radix_sort();
     return ;
 }

2.归并排序

时间复杂度：O(nlogn)

注意：

1.其他排序算法的空间复杂度是O(1)，而归并排序的空间复杂度很大，为O(n)。

2.下面的end是“末尾索引＋1”，即数列末尾要留一个空位。

下面给出如下代码：

 #include<iostream>
 using namespace std;
 int a[];
 int temp[];
 void merge_sort(int *a,int start,int end)
 {
     if(start+>=end)                                         //回渊
     return;
     //int temp[start-end+5];
     int mid=start+(end-start)/;                        //划分阶段
     int i=start,j=mid,count=start;
     merge_sort(a,start,mid);
     merge_sort(a,mid,end);
     while(i<mid||j<end)                                    //合并解
     {
         if(j>=end||(i<mid&&a[i]<=a[j]))
         {
             temp[count++]=a[i++];
         }
         else
         temp[count++]=a[j++];
     }
     //int x=0;
     for(int v=start;v<end;v++)
     {
         a[v]=temp[v];
     }
 }
 int main()
 {
     int n;
     cin>>n;
     for(int i=;i<n;i++)
     {
         cin>>a[i];
     }
     merge_sort(a,,n);
     for(int i=;i<n;i++)
     {
         cout<<a[i]<<' ';
     }
     return ;
 }

3.快速排序(优化读入读出)

下面给出如下代码：

 #include <cstdio>
 #include <iostream>
 using namespace std;
 int a[];
 int read_int() //读入优化
 {
     int x,f=; //f表示符号,x表示数值
     char ch;
     while (ch=getchar(),ch<||ch>) //如果ch不是数字
         if (ch=='-') f=-f; //如果是符号就改变符号
     x=ch-; //首位数字
     while (ch=getchar(),ch>=&&ch<=) //接下来的每位数字
         x=x*+ch-; //将数字添加进x内
     return x*f; //返回数值
 }
 void write_int(int x)
 {
     if (x==) //判断0的情况
         {
         putchar('');
         return;
     }
     int num=;
     char c[]; //然而我刚开始打的是10,然后发现输出10位数乱码了
     while (x) //x!=0
         c[++num]=x%+,x/=; //保存每一位
     while (num) //如果未输出完
         putchar(c[num--]); //输出
 }
 int sort(int l,int r) //快排，不用多说了吧
 {
     int i,j,x;
     x=a[(l+r)>>]; //基准
     i=l;
     j=r;
     do
     {
         while (a[i]<x) ++i;
         while (a[j]>x) --j; //跳过排序完毕的元素
         if (i<=j)
         {
             a[]=a[i];
             a[i]=a[j];
             a[j]=a[];
             ++i;
             --j; //交换
         }
     }
     while (i<=j);
     if (l<j) sort(l,j);
     if (i<r) sort(i,r); //排序左右子序列
 }
 int main()
 {
     int n,i;
     n=read_int();
     for (i=;i<=n;i++)
         a[i]=read_int(); //快读的正确打开方式
     sort(,n);
     for (i=;i<n;i++)
     {
         write_int(a[i]);
         putchar(' '); //输出的正确打开方式
     }
     write_int(a[n]);
     putchar('\n'); //强迫症...
     return ;
 }

4.利用stl实现堆排序，不是优先队列，比优先队列快上不少，而且容易记

下面给出如下代码：

 #include <cstdio>
 #include <algorithm>
 #include <queue>//头文件
 using namespace std;
 const int maxx =  + ;
 int Heap[maxx];
 int main()
 {
     int n,num = ,x;
     scanf("%d",&n);
     for(int i=;i<=n;i++)
         scanf("%d",&x),Heap[++num]=x,push_heap(Heap+,Heap+num+,greater<int>());
     for(int i=;i<=n;i++)
             printf("%d ",Heap[]),pop_heap(Heap+,Heap+num+,greater<int>()),num--;//这几步是关键
     return ;
 }//代码比手搓堆短很多，而且时间差不多

5.朴素的堆排模板类

下面给出如下代码：

 #include <bits/stdc++.h>
 using namespace std;
 template<typename T> //定义一个交换模板
 void change(T& a,T& b)
 {
     T t;
     t=a;a=b;b=t;
 }
 template<typename T> //定义一个模板类
 class Heap{
     T data[]; //存储数据

     void ify(int i); //维护堆
         Heap(int); //构造函数
         ~Heap(); //析构函数
         void build(); //建堆
         void heapsort(); //堆排序
         istream& scan(istream&); //读入
         ostream& print(ostream&); //输出
 };
 template<typename T>
 Heap<T>::Heap(int n_):n(n_)
 {
 }
 template<typename T>
 Heap<T>::~Heap()
 {
 }
 template<typename T>
 void Heap<T>::ify(int i)
 {
     int l=i<<;
     int r=(i<<)+;
     int m;
     if (l<=size&&data[l]>data[i]) m=l;
     else m=i;
     if (r<=size&&data[r]>data[m]) m=r;
     if (m!=i)
     {
         change(data[m],data[i]); //找到最大数后交换并维护子树
         ify(m);
     }
 }
 template<typename T>
 void Heap<T>::build()
 {
     int i;
     size=n;
     for (i=n/;i>;i--) //对每个非叶子节点维护一次
         ify(i);
 }
 template<typename T>
 void Heap<T>::heapsort()
 {
     build();
     for (int i=n;i>;i--)
     {
         change(data[],data[i]); //将最大数扔到最后
         --size;
         ify(); //维护
     }
 }
 template<typename T>
 istream& Heap<T>::scan(istream& is) //读入
 {
     for (int i=;i<=n;i++)
         is>>data[i];
     return is;
 }
 template<typename T>
 ostream& Heap<T>::print(ostream& os) //输出
 {
     for (int i=;i<n;i++)
         os<<data[i]<<' ';
     os<<data[n];
     return os;
 }
 template<typename T>
 istream& operator>>(istream& is,Heap<T>& a) //重载运算符
 {
     return a.scan(is);
 }
 template<typename T>
 ostream& operator<<(ostream& os,Heap<T>& a) //同上
 {
     return a.print(os);
 }
 int main()
 {
     int n;
     cin>>n;
     Heap<int> a(n);
     cin>>a;
     a.heapsort();
     cout<<a<<endl;
 }

6.优先队列priority_queue

下面给出如下代码：

 #include<cstdio>
 #include<algorithm>
 #include<queue>
 using namespace std;
 int main(){
     priority_queue<int,vector<int>,greater<int> > q;
     int n,x;
     scanf("%d",&n);
     for(int i=;i<=n;i++){
         scanf("%d",&x);
         q.push(x);
     }
     for(int i=;i<=n;i++){
         x=q.top();
         printf("%d ",x);
         q.pop();
     }
     return ;
 }

7.用一个红黑树来实现

下面给出如下代码：

 #include <cstdlib>
 #include <iostream>
 #include <set>
 #include <string>
 using namespace std;
 int main(int argc, char *argv[])
 {
     multiset<int>sort;//新建一个红黑树
     int n;
     scanf("%d",&n);
     for(int i=;i<=n;i++)
     {
             int a;
             cin>>a;
             sort.insert(a);//将数据插入红黑树
             }
     set<int>::iterator it;
     for(it=sort.begin();it!=sort.end();it++)
     cout << *it<<' ';//遍历输出红黑树，即排序结果
     cout<< endl;
     return ;
 }

8.排序二叉树

有一种很好的办法是用排序二叉树。。。建好树后中序遍历输出。。。就好了。

不过二叉排序树有退化成链的可能，所以可以用splay或是treap甚至AVL以及红黑树来排序。。。

伸展树(splay)的写法：

 #include<iostream>
 #include<algorithm>
 #include<cstdio>
 #include<cstdlib>
 #include<cstring>
 #define xh(a,b,c)for(int a=(b);a<=(c);a++)
 #define dxh(a,b,c)for(int a=(b);a>=(c);a--)
 #define hy(a)memset(a,0,sizeof(a))
 using namespace std;
 void qin(int &x){//快速读入
     int base=,num;
     char c=getchar();
     while(!(c=='-'||c>=''&&c<=''||c==EOF))c=getchar();
     if(c==EOF)exit();
     if(c=='-')base=-,c=getchar();
     num=c-'';
     c=getchar();
     while(c>=''&&c<=''){
         num*=;
         num+=c-'';
         c=getchar();
     }
     x=num*base;
 }
 char integ[];
 void qout(int x){//快速输出
     if(x<)putchar('-'),x=-x;
     int len=;
     do{
         integ[len++]=x%+'';
         x/=;
     }while(x);
     while(len--){
         putchar(integ[len]);
     }
 }
 struct jd{//静态splay
     int x;
     int l,r,h;
 };
 const int N=;
 jd bst[N];
 int root,n;//root表示根节点的编号
 void lj(int u,int d,int fx){
     if(fx==)bst[u].r=d;
     else bst[u].l=d;
     bst[d].h=u;
 }
 void zig(int x){//左旋
     int b1=bst[x].l,b2=bst[x].r,h=bst[x].h,b3=bst[h].r;
     root=x;
     bst[x].h=;
     lj(x,h,);
     lj(x,b1,-);
     lj(h,b2,-);
     lj(h,b3,);
 }
 void zag(int x){//右旋
     int b1=bst[x].l,b2=bst[x].r,h=bst[x].h,b3=bst[h].l;
     root=x;
     bst[x].h=;
     lj(x,h,-);
     lj(x,b2,);
     lj(h,b3,-);
     lj(h,b1,);
 }
 void zigzig(int x){//略。。。反正是向上调
     int b1=bst[x].l,
         b2=bst[x].r,
         h=bst[x].h,
         b3=bst[h].r,
         hh=bst[h].h,
         b4=bst[hh].r,
         hhh=bst[hh].h;
         if(hhh==){
             root=x;
             bst[x].h=;
         }else if(bst[hhh].l==hh)lj(hhh,x,-);
         else lj(hhh,x,);
     lj(x,h,);
     lj(h,hh,);
     lj(x,b1,-);
     lj(h,b2,-);
     lj(hh,b3,-);
     lj(hh,b4,);
 }
 void zagzag(int x){//略。。。反正是向上调*2
     int h=bst[x].h,
         hh=bst[h].h,
         hhh=bst[hh].h,
         b1=bst[hh].l,
         b2=bst[h].l,
         b3=bst[x].l,
         b4=bst[x].r;
         if(hhh==){
             root=x;
             bst[x].h=;
         }else if(bst[hhh].l==hh)lj(hhh,x,-);
     else lj(hhh,x,);
     lj(x,h,-);
     lj(h,hh,-);
     lj(x,b4,);
     lj(h,b3,);
     lj(hh,b1,-);
     lj(hh,b2,);
 }
 void zigzag(int x){//略。。。反正是向上调*3
     int b1=bst[x].l,
         b2=bst[x].r,
         h=bst[x].h,
         b3=bst[h].r,
         hh=bst[h].h,
         b4=bst[hh].l,
         hhh=bst[hh].h;
     if(hhh==){
             root=x;
             bst[x].h=;
         }else if(bst[hhh].l==hh)lj(hhh,x,-);
     else lj(hhh,x,);
     lj(x,h,);
     lj(x,hh,-);
     lj(hh,b1,);
     lj(h,b2,-);
     lj(h,b3,);
     lj(hh,b4,-);
 }
 void zagzig(int x){////略。。。反正是向上调
     int b1=bst[x].l,
         b2=bst[x].r,
         h=bst[x].h,
         b3=bst[h].l,
         hh=bst[h].h,
         b4=bst[hh].r,
         hhh=bst[hh].h;
         if(hhh==){
             root=x;
             bst[x].h=;
         }else if(bst[hhh].l==hh)lj(hhh,x,-);
     else lj(hhh,x,);
     lj(x,h,-);
     lj(x,hh,);
     lj(h,b1,);
     lj(hh,b2,-);
     lj(h,b3,-);
     lj(hh,b4,);
 }
 void splay(int x){//伸展操作（把x节点调到根节点）
     while(bst[x].h){
         if(bst[bst[x].h].h==){
             if(bst[bst[x].h].l==x)zig(x);
             else zag(x);
         }
         else{
             int h=bst[x].h,hh=bst[h].h;
             if(bst[h].l==x){
                 if(bst[hh].l==h)zigzig(x);
                 else zigzag(x);
             }
             else{
                 if(bst[hh].l==h)zagzig(x);
                 else zagzag(x);
             }
         }
     }
 }
 void ins(int r,int i){//插入
     if(bst[i].x<bst[r].x){
         if(bst[r].l==){
             lj(r,i,-);
             splay(i);//每当插入一个数后都要把这个数调到根节点
         }
         else ins(bst[r].l,i);
     }
     else{
         if(bst[r].r==){
             lj(r,i,);
             splay(i);;//每当插入一个数后都要把这个数调到根节点
         }
         else ins(bst[r].r,i);
     }
 }
 void bl(int x){//中序遍历
     if(x==)return;
     bl(bst[x].l);
     qout(bst[x].x);
     putchar(' ');
     bl(bst[x].r);
 }
 int main(){
     qin(n);
     qin(bst[].x);
     root=;
     xh(i,,n){
         qin(bst[i].x);
         ins(root,i);
     }
     bl(root);
     putchar('\n');
     return ;
 }

9.可并堆

 #include<bits/stdc++.h>
 using namespace std;
 #define fr(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
 struct tree{
     tree *l,*r,*f;
     int v,sl,sr;
     tree(){
         l=r=f=NULL;
         v=sl=sr=;
     }
 }*root,*k,*d;
 tree* merge(tree *x,tree *y){//合并
     if(x==NULL)return y;
     if(y==NULL)return x;
     if(x->v>y->v)
         swap(x,y);
     x->r=merge(x->r,y);
     x->sr++;
     if((x->sl)<(x->sr)){
         swap(x->l,x->r);
         swap(x->sl,x->sr);
     }
     return x;
 }
 void insert(int x){//插入
     k=new tree;
     k->v=x;
     if(root==NULL)root=k;
     else root=merge(root,k);
 }
 int top(){//顶端元素
     if(root!=NULL)return root->v;
     return -;
 }
 void pop(){//弹出
     if(root!=NULL)root=merge(root->l,root->r);//合并左右子数
 }
 int main(){
     root=NULL;
     int n;
     scanf("%d",&n);
     fr(i,,n){
         int a;
         scanf("%d",&a);
         insert(a);
     }
     fr(i,,n){
         printf("%d ",top());
         pop();
     }
     return ;
 }

10.希尔排序

 #include <cstdio>
 using namespace std;
 int i,j,k,n,m,x,y,t,d,a[];
 void ShellInsert(int* pDataArray, int d, int iDataNum){
     for (int i = d; i < iDataNum; i += ){
         int j = i - d;
         int temp = pDataArray[i];
         while (j >=  && pDataArray[j] > temp){pDataArray[j+d] = pDataArray[j];j -= d;}
         if (j != i - d)pDataArray[j+d] = temp;
     }
 }
 void ShellSort(int* pDataArray, int iDataNum){
     int d = iDataNum / ;
     while(d >= ){ShellInsert(pDataArray, d, iDataNum);d = d / ;}
 }
 int main(){
     scanf("%d",&n);if (n==) return ;
     for (i=;i<n;i++) scanf("%d",&a[i]);
     ShellSort(a,n);
     for (i=;i<n;i++) printf("%d ",a[i]);
     return ;
 }

11.用动态插入堆排序

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 using namespace std;
 typedef long long ll;
 ll heap[];
 #define lson(x) x<<1
 #define rson(x) x<<1|1
 #define fa(x) x>>1
 ll N;
 struct Heap{
     int size;
     Heap(){
         size=;
     }
     void pushDown(int i){ //从顶部向下推至合适位置
         int l,r,k;
         while(lson(i)<=size){
             l=lson(i);r=rson(i);k=i;
             if(heap[k]>heap[l]){
                 k=l;
             }
             if(r<=size && heap[k]>heap[r]){
                 k=r;
             }
             if(k!=i){
                 swap(heap[i],heap[k]);
                 i=k;
             }else break;
         }
     }
     void pushUp(int i){ // 从底部推至合适位置
         while(fa(i)>=){
             if(heap[fa(i)]>heap[i]){
                 swap(heap[fa(i)],heap[i]);
                 i=fa(i);
             }else break;
         }
     }
     void pop(){ //删除堆顶元素
         heap[]=heap[size--];
         pushDown();
     }
     ll top(){
         return heap[];
     }
     void insert(int x){ //插入一个新元素到堆底
         heap[++size]=x;
         pushUp(size);
     }
 }H;
 inline ll read(){
     ll a=;
     char ch=getchar();
     bool flag = false;
     while(ch>'' || ch<'' || ch=='-'){
         if(ch=='-') flag=true;
         ch=getchar();
     }
     while(ch>='' && ch<=''){
         a=a*+ch-'';
         ch=getchar();
     }
     if(flag) a=-a;
     return a;
 }
 int main(){
     N=read();ll v;
     for(int i=;i<=N;++i){
         v=read();H.insert(v);
     }
     while(H.size){
         printf("%lld ",H.top());
         H.pop();
     }
     return ;
 }

12.基数排序(O(n))

 #include<iostream>
 #include<cstdio>
 #include<cstdlib>
 #include<cstring>
 #include<string>
 #define Z 1000000+10
 #define K 10+10//位数设为20 ， 11 也可以
 #define FORZ(a,b,c) for(a=b;a<=c;a++)
 #define FORJ(a,b,c) for(a=b;a>=c;a--)
 #define M0(a) memset(a,0,sizeof(a))
 using namespace std;
 int a[Z];
 int b[Z];
 int cnt[K];
 int getmax(const int n)
 {
   int i,p=,sum=;
   FORZ(i,,n)
   {
       while(a[i]>=sum)
       {
         sum*=;
       p++;
     }
   }
   return p;
 }
 void JS_sort(const int n)
 {
   int i,j,k,l,o,p,u;
   int wei=getmax(n);
   int ord=;
   FORZ(k,,wei)
   {
       M0(cnt);
       FORZ(i,,n)
     {
       u=a[i]/ord%;
       cnt[u]++;
     }
     FORZ(i,,)
     {
       cnt[i]+=cnt[i-];
     }
     //滚包裹
     FORJ(i,n,)
     {
       u=a[i]/ord%;
       b[cnt[u]]=a[i];
       cnt[u]--;
     }
     FORZ(i,,n)
     {
       a[i]=b[i];
     }
     ord*=;
   }
 }
 int main()
 {
   int n,i,j,k,l,u,o,p;
   scanf("%d",&n);
   FORZ(i,,n)scanf("%d",&a[i]);
   JS_sort(n);
   FORZ(i,,n)printf("%d ",a[i]);
 }

13.最不值得一提的sort(不建议，毕竟这是一道模版题)

 #include <bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 ll a[];
 int main()
 {
     int n;
     cin>>n;
     for(int i=;i<=n;i++)
         cin>>a[i];
     sort(a+,a++n);
     for(int i=;i<n;i++)
         cout<<a[i]<<" ";
     cout<<a[n]<<endl;
     return ;
 }