注意！此处没有打广告！
ps：计数排序就是桶排序，不是基数排序
补充两种排序：希尔排序和基数排序
基数排序：桶排序plus，把每个数分个，十，百位来桶排，复杂度O (nlog(r)m)，其中r为所采取的基数，而m为堆数
希尔排序：插入排序plus，以空间换时间，把每个数间隔加大，插入时便无需向后移动所有元素，时间复杂度介于对数线性阶与平方阶之间
时间复杂度其实很好理解。
直接插入，直接选择，冒泡排序都是n方，因为都是双重循环。
快排和归并都是1生2，2生4，4生8，子子孙孙无穷匮，所以类似于二分，时间复杂度是nlogn
附上快排代码，完善程序有可能考
#include <cstdio> #include <algorithm> using namespace std; const int maxn=1e5+5; int n; int a[maxn]; int read() //快速读入
{ int x=0,f=1;char ch=getchar(); for(;ch<‘0‘||ch>‘9‘;ch=getchar())if(ch==‘-‘)f=-1; for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar())x=x*10+ch-‘0‘; return x*f; } void Qsort(int l,int r) { int i=l,j=r,mid=a[(l+r)>>1];//mid作为键值 注意 n>>1表示n/2，位运算基本操作 while(i<=j) { while(a[i]<mid)i++;//小于mid的值放在左半部分不用管 while(a[j]>mid)j--;//大于mid的值放在右半部分不用管 if(i<=j)swap(a[i++],a[j--]);//维护序列 }//[l,i]始终小于等于mid，区间[j,r]始终大于等于mid if(l<j)Qsort(l,j);//递归处理 if(i<r)Qsort(i,r);//递归处理 } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); Qsort(1,n); for(int i=1;i<=n;i++) printf("%d ",a[i]); return 0; }
由于各种神奇的数据，快排其实是可以优化一下的。
最简单的就是mid=(l+r)/2
再者是随机化，用rand（）函数随机mid（基准数）的值。
用随机化和不用时间比较
左用，右不用
少了一点点吧。。。
原文：https://www.cnblogs.com/huaruoji/p/11701109.html