排序集锦（选择，冒泡，快速，归并，插入，希尔）

#include<bits/stdc++.h> using namespace std; int n,a[100010],b[100010],ans[100010]; inline int read() { int res=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();} while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch&15);ch=getchar();} return res*f; } inline void out() { for(int i=1;i<=n;i++) printf("%d ",a[i]); putchar('\n'); } inline void change() { for(int i=1;i<=n;i++) a[i]=b[i]; } inline void choose() { for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[i]>a[j])swap(a[i],a[j]); return ; } inline void mao() { for(int i=1;i<=n;i++) for(int j=1;j<=n-i;j++) if(a[j]>a[j+1])swap(a[j],a[j+1]); return ; } inline void qsort(int l,int r) { int i=l,j=r; int mid=a[(l+r)>>1]; while(i<=j) { while(a[i]<mid)i++; while(a[j]>mid)j--; if(i<=j) { swap(a[i],a[j]); i++;j--; } } if(l<j)qsort(l,j); if(i<r)qsort(i,r); } inline void msort(int l,int r) { if(l==r)return; int mid=(l+r)/2; msort(l,mid);msort(mid+1,r); int i=l,k=l,j=mid+1; while(i<=mid&&j<=r) { if(a[i]>a[j])ans[k]=a[j],j++,k++; else ans[k]=a[i],i++,k++; } while(i<=mid)ans[k]=a[i],i++,k++; while(j<=r)ans[k]=a[j],j++,k++; for(int i=l;i<=r;i++)a[i]=ans[i]; } inline void csort() { memset(ans,0,sizeof(ans)); for(int i=1;i<=n;i++) { int p=i; for(int j=1;j<i;j++)if(ans[j]>a[i]){p=j;break;} if(p==i)ans[i]=a[i]; else { for(int j=i;j>=p;j--)ans[j]=ans[j-1]; ans[p]=a[i]; } } for(int i=1;i<=n;i++)a[i]=ans[i]; } inline void xsort() { for(int gap=n/2;gap;gap/=2) { for(int k=gap;k<=n;k++) { int t=a[k]; int j=k-gap; while(j>=1&&t<a[j]) { a[j+gap]=a[j]; j-=gap; } a[j+gap]=t; } } } int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i]; change(); choose();//选择 out(); change(); mao();//冒泡 out(); change(); qsort(1,n);//快排 out(); change(); msort(1,n);//归并 out(); change(); csort(); //插入 out(); change(); xsort();//希尔 out(); return 0; }