利用快速排序算法将读入的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高速缓存
下面给出如下代码:
1 #include <cstring>
2 #include <cstdio>
3 #include <algorithm>
4 using namespace std;
5 const int MAXN = 100010;
6 const int BIT = 16;
7 const int U = 65536;
8 int n, a[MAXN];
9 inline int getd( int x, int d ) {
10 return (x>>(d*BIT))&(U-1);
11 }
12 int cnt[U], b[MAXN];
13 void radix_sort() {
14 int *x = a, *y = b;
15 for( int d = 0; d < 2; ++d ) {
16 for( int i = 0; i < U; ++i ) cnt[i] = 0;
17 for( int i = 0; i < n; ++i ) ++cnt[getd(x[i],d)];
18 for( int i = 1; i < U; ++i ) cnt[i] += cnt[i-1];
19 for( int i = n-1; i >= 0; --i ) y[--cnt[getd(x[i],d)]] = x[i];
20 swap(x,y);
21 }
22 for( int i = 0; i < n; ++i ) printf( "%d ", x[i] );
23 }
24 int main() {
25 scanf( "%d", &n );
26 for( int i = 0; i < n; ++i ) scanf( "%d", a+i );
27 radix_sort();
28 return 0;
29 }
2.归并排序
时间复杂度:O(nlogn)
注意:
1.其他排序算法的空间复杂度是O(1),而归并排序的空间复杂度很大,为O(n)。
2.下面的end是“末尾索引+1”,即数列末尾要留一个空位。
下面给出如下代码:
1 #include<iostream>
2 using namespace std;
3 int a[100010];
4 int temp[100010];
5 void merge_sort(int *a,int start,int end)
6 {
7 if(start+1>=end) //回渊
8 return;
9 //int temp[start-end+5];
10 int mid=start+(end-start)/2; //划分阶段
11 int i=start,j=mid,count=start;
12 merge_sort(a,start,mid);
13 merge_sort(a,mid,end);
14 while(i<mid||j<end) //合并解
15 {
16 if(j>=end||(i<mid&&a[i]<=a[j]))
17 {
18 temp[count++]=a[i++];
19 }
20 else
21 temp[count++]=a[j++];
22 }
23 //int x=0;
24 for(int v=start;v<end;v++)
25 {
26 a[v]=temp[v];
27 }
28 }
29 int main()
30 {
31 int n;
32 cin>>n;
33 for(int i=0;i<n;i++)
34 {
35 cin>>a[i];
36 }
37 merge_sort(a,0,n);
38 for(int i=0;i<n;i++)
39 {
40 cout<<a[i]<<' ';
41 }
42 return 0;
43 }
3.快速排序(优化读入读出)
下面给出如下代码:
1 #include <cstdio>
2 #include <iostream>
3 using namespace std;
4 int a[100000];
5 int read_int() //读入优化
6 {
7 int x,f=1; //f表示符号,x表示数值
8 char ch;
9 while (ch=getchar(),ch<48||ch>57) //如果ch不是数字
10 if (ch=='-') f=-f; //如果是符号就改变符号
11 x=ch-48; //首位数字
12 while (ch=getchar(),ch>=48&&ch<=57) //接下来的每位数字
13 x=x*10+ch-48; //将数字添加进x内
14 return x*f; //返回数值
15 }
16 void write_int(int x)
17 {
18 if (x==0) //判断0的情况
19 {
20 putchar('0');
21 return;
22 }
23 int num=0;
24 char c[11]; //然而我刚开始打的是10,然后发现输出10位数乱码了
25 while (x) //x!=0
26 c[++num]=x%10+48,x/=10; //保存每一位
27 while (num) //如果未输出完
28 putchar(c[num--]); //输出
29 }
30 int sort(int l,int r) //快排,不用多说了吧
31 {
32 int i,j,x;
33 x=a[(l+r)>>1]; //基准
34 i=l;
35 j=r;
36 do
37 {
38 while (a[i]<x) ++i;
39 while (a[j]>x) --j; //跳过排序完毕的元素
40 if (i<=j)
41 {
42 a[0]=a[i];
43 a[i]=a[j];
44 a[j]=a[0];
45 ++i;
46 --j; //交换
47 }
48 }
49 while (i<=j);
50 if (l<j) sort(l,j);
51 if (i<r) sort(i,r); //排序左右子序列
52 }
53 int main()
54 {
55 int n,i;
56 n=read_int();
57 for (i=1;i<=n;i++)
58 a[i]=read_int(); //快读的正确打开方式
59 sort(1,n);
60 for (i=1;i<n;i++)
61 {
62 write_int(a[i]);
63 putchar(' '); //输出的正确打开方式
64 }
65 write_int(a[n]);
66 putchar('\n'); //强迫症...
67 return 233;
68 }
4.利用stl实现堆排序,不是优先队列,比优先队列快上不少,而且容易记
下面给出如下代码:
1 #include <cstdio>
2 #include <algorithm>
3 #include <queue>//头文件
4 using namespace std;
5 const int maxx = 100000 + 10;
6 int Heap[maxx];
7 int main()
8 {
9 int n,num = 0,x;
10 scanf("%d",&n);
11 for(int i=1;i<=n;i++)
12 scanf("%d",&x),Heap[++num]=x,push_heap(Heap+1,Heap+num+1,greater<int>());
13 for(int i=1;i<=n;i++)
14 printf("%d ",Heap[1]),pop_heap(Heap+1,Heap+num+1,greater<int>()),num--;//这几步是关键
15 return 0;
16 }//代码比手搓堆短很多,而且时间差不多
5.朴素的堆排模板类
下面给出如下代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 template<typename T> //定义一个交换模板
4 void change(T& a,T& b)
5 {
6 T t;
7 t=a;a=b;b=t;
8 }
9 template<typename T> //定义一个模板类
10 class Heap{
11 T data[100001]; //存储数据
12
13 void ify(int i); //维护堆
14 Heap(int); //构造函数
15 ~Heap(); //析构函数
16 void build(); //建堆
17 void heapsort(); //堆排序
18 istream& scan(istream&); //读入
19 ostream& print(ostream&); //输出
20 };
21 template<typename T>
22 Heap<T>::Heap(int n_):n(n_)
23 {
24 }
25 template<typename T>
26 Heap<T>::~Heap()
27 {
28 }
29 template<typename T>
30 void Heap<T>::ify(int i)
31 {
32 int l=i<<1;
33 int r=(i<<1)+1;
34 int m;
35 if (l<=size&&data[l]>data[i]) m=l;
36 else m=i;
37 if (r<=size&&data[r]>data[m]) m=r;
38 if (m!=i)
39 {
40 change(data[m],data[i]); //找到最大数后交换并维护子树
41 ify(m);
42 }
43 }
44 template<typename T>
45 void Heap<T>::build()
46 {
47 int i;
48 size=n;
49 for (i=n/2;i>0;i--) //对每个非叶子节点维护一次
50 ify(i);
51 }
52 template<typename T>
53 void Heap<T>::heapsort()
54 {
55 build();
56 for (int i=n;i>1;i--)
57 {
58 change(data[1],data[i]); //将最大数扔到最后
59 --size;
60 ify(1); //维护
61 }
62 }
63 template<typename T>
64 istream& Heap<T>::scan(istream& is) //读入
65 {
66 for (int i=1;i<=n;i++)
67 is>>data[i];
68 return is;
69 }
70 template<typename T>
71 ostream& Heap<T>::print(ostream& os) //输出
72 {
73 for (int i=1;i<n;i++)
74 os<<data[i]<<' ';
75 os<<data[n];
76 return os;
77 }
78 template<typename T>
79 istream& operator>>(istream& is,Heap<T>& a) //重载运算符
80 {
81 return a.scan(is);
82 }
83 template<typename T>
84 ostream& operator<<(ostream& os,Heap<T>& a) //同上
85 {
86 return a.print(os);
87 }
88 int main()
89 {
90 int n;
91 cin>>n;
92 Heap<int> a(n);
93 cin>>a;
94 a.heapsort();
95 cout<<a<<endl;
96 }
6.优先队列priority_queue
下面给出如下代码:
1 #include<cstdio>
2 #include<algorithm>
3 #include<queue>
4 using namespace std;
5 int main(){
6 priority_queue<int,vector<int>,greater<int> > q;
7 int n,x;
8 scanf("%d",&n);
9 for(int i=1;i<=n;i++){
10 scanf("%d",&x);
11 q.push(x);
12 }
13 for(int i=1;i<=n;i++){
14 x=q.top();
15 printf("%d ",x);
16 q.pop();
17 }
18 return 0;
19 }
7.用一个红黑树来实现
下面给出如下代码:
1 #include <cstdlib>
2 #include <iostream>
3 #include <set>
4 #include <string>
5 using namespace std;
6 int main(int argc, char *argv[])
7 {
8 multiset<int>sort;//新建一个红黑树
9 int n;
10 scanf("%d",&n);
11 for(int i=1;i<=n;i++)
12 {
13 int a;
14 cin>>a;
15 sort.insert(a);//将数据插入红黑树
16 }
17 set<int>::iterator it;
18 for(it=sort.begin();it!=sort.end();it++)
19 cout << *it<<' ';//遍历输出红黑树,即排序结果
20 cout<< endl;
21 return 0;
22 }
8.排序二叉树
有一种很好的办法是用排序二叉树。。。建好树后中序遍历输出。。。就好了。
不过二叉排序树有退化成链的可能,所以可以用splay或是treap甚至AVL以及红黑树来排序。。。
伸展树(splay)的写法:
1 #include<iostream>
2 #include<algorithm>
3 #include<cstdio>
4 #include<cstdlib>
5 #include<cstring>
6 #define xh(a,b,c)for(int a=(b);a<=(c);a++)
7 #define dxh(a,b,c)for(int a=(b);a>=(c);a--)
8 #define hy(a)memset(a,0,sizeof(a))
9 using namespace std;
10 void qin(int &x){//快速读入
11 int base=1,num;
12 char c=getchar();
13 while(!(c=='-'||c>='0'&&c<='9'||c==EOF))c=getchar();
14 if(c==EOF)exit(0);
15 if(c=='-')base=-1,c=getchar();
16 num=c-'0';
17 c=getchar();
18 while(c>='0'&&c<='9'){
19 num*=10;
20 num+=c-'0';
21 c=getchar();
22 }
23 x=num*base;
24 }
25 char integ[50];
26 void qout(int x){//快速输出
27 if(x<0)putchar('-'),x=-x;
28 int len=0;
29 do{
30 integ[len++]=x%10+'0';
31 x/=10;
32 }while(x);
33 while(len--){
34 putchar(integ[len]);
35 }
36 }
37 struct jd{//静态splay
38 int x;
39 int l,r,h;
40 };
41 const int N=101010;
42 jd bst[N];
43 int root,n;//root表示根节点的编号
44 void lj(int u,int d,int fx){
45 if(fx==1)bst[u].r=d;
46 else bst[u].l=d;
47 bst[d].h=u;
48 }
49 void zig(int x){//左旋
50 int b1=bst[x].l,b2=bst[x].r,h=bst[x].h,b3=bst[h].r;
51 root=x;
52 bst[x].h=0;
53 lj(x,h,1);
54 lj(x,b1,-1);
55 lj(h,b2,-1);
56 lj(h,b3,1);
57 }
58 void zag(int x){//右旋
59 int b1=bst[x].l,b2=bst[x].r,h=bst[x].h,b3=bst[h].l;
60 root=x;
61 bst[x].h=0;
62 lj(x,h,-1);
63 lj(x,b2,1);
64 lj(h,b3,-1);
65 lj(h,b1,1);
66 }
67 void zigzig(int x){//略。。。反正是向上调
68 int b1=bst[x].l,
69 b2=bst[x].r,
70 h=bst[x].h,
71 b3=bst[h].r,
72 hh=bst[h].h,
73 b4=bst[hh].r,
74 hhh=bst[hh].h;
75 if(hhh==0){
76 root=x;
77 bst[x].h=0;
78 }else if(bst[hhh].l==hh)lj(hhh,x,-1);
79 else lj(hhh,x,1);
80 lj(x,h,1);
81 lj(h,hh,1);
82 lj(x,b1,-1);
83 lj(h,b2,-1);
84 lj(hh,b3,-1);
85 lj(hh,b4,1);
86 }
87 void zagzag(int x){//略。。。反正是向上调*2
88 int h=bst[x].h,
89 hh=bst[h].h,
90 hhh=bst[hh].h,
91 b1=bst[hh].l,
92 b2=bst[h].l,
93 b3=bst[x].l,
94 b4=bst[x].r;
95 if(hhh==0){
96 root=x;
97 bst[x].h=0;
98 }else if(bst[hhh].l==hh)lj(hhh,x,-1);
99 else lj(hhh,x,1);
100 lj(x,h,-1);
101 lj(h,hh,-1);
102 lj(x,b4,1);
103 lj(h,b3,1);
104 lj(hh,b1,-1);
105 lj(hh,b2,1);
106 }
107 void zigzag(int x){//略。。。反正是向上调*3
108 int b1=bst[x].l,
109 b2=bst[x].r,
110 h=bst[x].h,
111 b3=bst[h].r,
112 hh=bst[h].h,
113 b4=bst[hh].l,
114 hhh=bst[hh].h;
115 if(hhh==0){
116 root=x;
117 bst[x].h=0;
118 }else if(bst[hhh].l==hh)lj(hhh,x,-1);
119 else lj(hhh,x,1);
120 lj(x,h,1);
121 lj(x,hh,-1);
122 lj(hh,b1,1);
123 lj(h,b2,-1);
124 lj(h,b3,1);
125 lj(hh,b4,-1);
126 }
127 void zagzig(int x){////略。。。反正是向上调
128 int b1=bst[x].l,
129 b2=bst[x].r,
130 h=bst[x].h,
131 b3=bst[h].l,
132 hh=bst[h].h,
133 b4=bst[hh].r,
134 hhh=bst[hh].h;
135 if(hhh==0){
136 root=x;
137 bst[x].h=0;
138 }else if(bst[hhh].l==hh)lj(hhh,x,-1);
139 else lj(hhh,x,1);
140 lj(x,h,-1);
141 lj(x,hh,1);
142 lj(h,b1,1);
143 lj(hh,b2,-1);
144 lj(h,b3,-1);
145 lj(hh,b4,1);
146 }
147 void splay(int x){//伸展操作(把x节点调到根节点)
148 while(bst[x].h){
149 if(bst[bst[x].h].h==0){
150 if(bst[bst[x].h].l==x)zig(x);
151 else zag(x);
152 }
153 else{
154 int h=bst[x].h,hh=bst[h].h;
155 if(bst[h].l==x){
156 if(bst[hh].l==h)zigzig(x);
157 else zigzag(x);
158 }
159 else{
160 if(bst[hh].l==h)zagzig(x);
161 else zagzag(x);
162 }
163 }
164 }
165 }
166 void ins(int r,int i){//插入
167 if(bst[i].x<bst[r].x){
168 if(bst[r].l==0){
169 lj(r,i,-1);
170 splay(i);//每当插入一个数后都要把这个数调到根节点
171 }
172 else ins(bst[r].l,i);
173 }
174 else{
175 if(bst[r].r==0){
176 lj(r,i,1);
177 splay(i);;//每当插入一个数后都要把这个数调到根节点
178 }
179 else ins(bst[r].r,i);
180 }
181 }
182 void bl(int x){//中序遍历
183 if(x==0)return;
184 bl(bst[x].l);
185 qout(bst[x].x);
186 putchar(' ');
187 bl(bst[x].r);
188 }
189 int main(){
190 qin(n);
191 qin(bst[1].x);
192 root=1;
193 xh(i,2,n){
194 qin(bst[i].x);
195 ins(root,i);
196 }
197 bl(root);
198 putchar('\n');
199 return 0;
200 }
9.可并堆
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define fr(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
4 struct tree{
5 tree *l,*r,*f;
6 int v,sl,sr;
7 tree(){
8 l=r=f=NULL;
9 v=sl=sr=0;
10 }
11 }*root,*k,*d;
12 tree* merge(tree *x,tree *y){//合并
13 if(x==NULL)return y;
14 if(y==NULL)return x;
15 if(x->v>y->v)
16 swap(x,y);
17 x->r=merge(x->r,y);
18 x->sr++;
19 if((x->sl)<(x->sr)){
20 swap(x->l,x->r);
21 swap(x->sl,x->sr);
22 }
23 return x;
24 }
25 void insert(int x){//插入
26 k=new tree;
27 k->v=x;
28 if(root==NULL)root=k;
29 else root=merge(root,k);
30 }
31 int top(){//顶端元素
32 if(root!=NULL)return root->v;
33 return -1;
34 }
35 void pop(){//弹出
36 if(root!=NULL)root=merge(root->l,root->r);//合并左右子数
37 }
38 int main(){
39 root=NULL;
40 int n;
41 scanf("%d",&n);
42 fr(i,1,n){
43 int a;
44 scanf("%d",&a);
45 insert(a);
46 }
47 fr(i,1,n){
48 printf("%d ",top());
49 pop();
50 }
51 return 0;
52 }
10.希尔排序
1 #include <cstdio>
2 using namespace std;
3 int i,j,k,n,m,x,y,t,d,a[100001];
4 void ShellInsert(int* pDataArray, int d, int iDataNum){
5 for (int i = d; i < iDataNum; i += 1){
6 int j = i - d;
7 int temp = pDataArray[i];
8 while (j >= 0 && pDataArray[j] > temp){pDataArray[j+d] = pDataArray[j];j -= d;}
9 if (j != i - d)pDataArray[j+d] = temp;
10 }
11 }
12 void ShellSort(int* pDataArray, int iDataNum){
13 int d = iDataNum / 2;
14 while(d >= 1){ShellInsert(pDataArray, d, iDataNum);d = d / 2;}
15 }
16 int main(){
17 scanf("%d",&n);if (n==0) return 0;
18 for (i=0;i<n;i++) scanf("%d",&a[i]);
19 ShellSort(a,n);
20 for (i=0;i<n;i++) printf("%d ",a[i]);
21 return 0;
22 }
11.用动态插入堆排序
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5 typedef long long ll;
6 ll heap[1001000];
7 #define lson(x) x<<1
8 #define rson(x) x<<1|1
9 #define fa(x) x>>1
10 ll N;
11 struct Heap{
12 int size;
13 Heap(){
14 size=0;
15 }
16 void pushDown(int i){ //从顶部向下推至合适位置
17 int l,r,k;
18 while(lson(i)<=size){
19 l=lson(i);r=rson(i);k=i;
20 if(heap[k]>heap[l]){
21 k=l;
22 }
23 if(r<=size && heap[k]>heap[r]){
24 k=r;
25 }
26 if(k!=i){
27 swap(heap[i],heap[k]);
28 i=k;
29 }else break;
30 }
31 }
32 void pushUp(int i){ // 从底部推至合适位置
33 while(fa(i)>=1){
34 if(heap[fa(i)]>heap[i]){
35 swap(heap[fa(i)],heap[i]);
36 i=fa(i);
37 }else break;
38 }
39 }
40 void pop(){ //删除堆顶元素
41 heap[1]=heap[size--];
42 pushDown(1);
43 }
44 ll top(){
45 return heap[1];
46 }
47 void insert(int x){ //插入一个新元素到堆底
48 heap[++size]=x;
49 pushUp(size);
50 }
51 }H;
52 inline ll read(){
53 ll a=0;
54 char ch=getchar();
55 bool flag = false;
56 while(ch>'9' || ch<'0' || ch=='-'){
57 if(ch=='-') flag=true;
58 ch=getchar();
59 }
60 while(ch>='0' && ch<='9'){
61 a=a*10+ch-'0';
62 ch=getchar();
63 }
64 if(flag) a=-a;
65 return a;
66 }
67 int main(){
68 N=read();ll v;
69 for(int i=1;i<=N;++i){
70 v=read();H.insert(v);
71 }
72 while(H.size){
73 printf("%lld ",H.top());
74 H.pop();
75 }
76 return 0;
77 }
12.基数排序(O(n))
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cstring>
5 #include<string>
6 #define Z 1000000+10
7 #define K 10+10//位数设为20 , 11 也可以
8 #define FORZ(a,b,c) for(a=b;a<=c;a++)
9 #define FORJ(a,b,c) for(a=b;a>=c;a--)
10 #define M0(a) memset(a,0,sizeof(a))
11 using namespace std;
12 int a[Z];
13 int b[Z];
14 int cnt[K];
15 int getmax(const int n)
16 {
17 int i,p=1,sum=10;
18 FORZ(i,1,n)
19 {
20 while(a[i]>=sum)
21 {
22 sum*=10;
23 p++;
24 }
25 }
26 return p;
27 }
28 void JS_sort(const int n)
29 {
30 int i,j,k,l,o,p,u;
31 int wei=getmax(n);
32 int ord=1;
33 FORZ(k,1,wei)
34 {
35 M0(cnt);
36 FORZ(i,1,n)
37 {
38 u=a[i]/ord%10;
39 cnt[u]++;
40 }
41 FORZ(i,1,9)
42 {
43 cnt[i]+=cnt[i-1];
44 }
45 //滚包裹
46 FORJ(i,n,1)
47 {
48 u=a[i]/ord%10;
49 b[cnt[u]]=a[i];
50 cnt[u]--;
51 }
52 FORZ(i,1,n)
53 {
54 a[i]=b[i];
55 }
56 ord*=10;
57 }
58 }
59 int main()
60 {
61 int n,i,j,k,l,u,o,p;
62 scanf("%d",&n);
63 FORZ(i,1,n)scanf("%d",&a[i]);
64 JS_sort(n);
65 FORZ(i,1,n)printf("%d ",a[i]);
66 }
13.最不值得一提的sort(不建议,毕竟这是一道模版题)
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 ll a[100010];
5 int main()
6 {
7 int n;
8 cin>>n;
9 for(int i=1;i<=n;i++)
10 cin>>a[i];
11 sort(a+1,a+1+n);
12 for(int i=1;i<n;i++)
13 cout<<a[i]<<" ";
14 cout<<a[n]<<endl;
15 return 0;
16 }