P1177 【模板】快速排序
题目描述
利用快速排序算法将读入的N个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）
输入输出格式
输入格式： 输入文件sort.in的第1行为一个正整数N，第2行包含N个空格隔开的正整数a[i]，为你需要进行排序的数，数据保证了A[i]不超过1000000000。
输出格式： 输出文件sort.out将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入输出样例
说明
对于20%的数据，有N≤1000；
对于100%的数据，有N≤100000。
题目链接：
下面给出几种排序方法：
1.松式基排
所谓普通基排，就是以65536为底，用位运算，把一个数拆成两部分，要循环两遍
松式基排，就是以256为底，用位运算把一个数拆成四部分，要循环四遍
为什么松式基排在WC的时候会更快呢，因为这样的话cnt数组刚好能装进L1高速缓存
下面给出如下代码：
1 #include 2 #include 3 #include 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 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 =end||(i <=a[j]))17 {18 temp[count++]=a[i++];19 }20 else21 temp[count++]=a[j++];22 }23 //int x=0;24 for(int v=start;v >n;33 for(int i=0;i >a[i];36 }37 merge_sort(a,0,n);38 for(int i=0;i
3.快速排序(优化读入读出)
下面给出如下代码：
1 #include 2 #include 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!=026 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 do37 {38 while (a[i] 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
4.利用stl实现堆排序，不是优先队列，比优先队列快上不少，而且容易记
下面给出如下代码：
1 #include 2 #include 3 #include //头文件 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 ());13 for(int i=1;i<=n;i++)14 printf("%d ",Heap[1]),pop_heap(Heap+1,Heap+num+1,greater ()),num--;//这几步是关键15 return 0;16 }//代码比手搓堆短很多，而且时间差不多
5.朴素的堆排模板类
下面给出如下代码：
1 #include 2 using namespace std; 3 template //定义一个交换模板 4 void change(T& a,T& b) 5 { 6 T t; 7 t=a;a=b;b=t; 8 } 9 template //定义一个模板类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 22 Heap ::Heap(int n_):n(n_)23 {24 }25 template 26 Heap ::~Heap()27 {28 }29 template 30 void Heap ::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 45 void Heap ::build()46 {47 int i;48 size=n;49 for (i=n/2;i>0;i--) //对每个非叶子节点维护一次50 ify(i);51 }52 template 53 void Heap ::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 64 istream& Heap ::scan(istream& is) //读入 65 {66 for (int i=1;i<=n;i++)67 is>>data[i];68 return is;69 }70 template 71 ostream& Heap ::print(ostream& os) //输出 72 {73 for (int i=1;i 79 istream& operator>>(istream& is,Heap & a) //重载运算符 80 {81 return a.scan(is);82 }83 template 84 ostream& operator<<(ostream& os,Heap & a) //同上 85 {86 return a.print(os);87 }88 int main()89 {90 int n;91 cin>>n;92 Heap a(n);93 cin>>a;94 a.heapsort();95 cout< <
6.优先队列priority_queue
下面给出如下代码：
1 #include 2 #include 3 #include 4 using namespace std; 5 int main(){ 6 priority_queue ,greater > 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 2 #include 3 #include 4 #include 5 using namespace std; 6 int main(int argc, char *argv[]) 7 { 8 multiset 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 ::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 2 #include 3 #include 4 #include 5 #include 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){ //略。。。反正是向上调*3108 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
9.可并堆
1 #include 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 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
11.用动态插入堆排序
1 #include 2 #include 3 #include 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>>110 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 2 #include 3 #include 4 #include 5 #include 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 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