有一种排序叫做计数排序(它是与桶排序不同的)，虽然它们的时间复杂度都是O(n)，但是计数排序比桶排序更稳定....
下面就根据代码看一下计数排序的模板以及其原理：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int n,z[100],cnt[100],m; 5 int main() 6 { 7 scanf("%d",&n); 8 for (int a=1;a<=n;a++) 9 { 10 scanf("%d",&z[a]); 11 cnt[z[a]] += 1;//注意cnt为一个用来计数的数组，z[a]可视为一个数，所以cnt++,表示z[a]共有多少个 12 m =max(m,z[a]);//m等于m和z[a]中较大的一个数，记录最大值是为了第15行的for循环 13 } 14 n=0;//在这里将n初始化 15 for (int a=0;a<=m;a++)/*m为这一些数据中的最大值，从0开始的原因是数据中可能有0， 16 在16行中，a充当了z[a]的角色，为输入的数据，输入数据只能在0到最大值m之间*/ 17 for (int b=1;b<=cnt[a];b++)//枚举a出现的次数，并将所有的a都加入到数组中 18 { 19 n++; 20 z[n] = a;//n++后将a储存到z数组中 21 } 22 for (int a=1;a<=n;a++) 23 printf("%d ",z[a]);//将排好的z数组进行输出 24 }
注意：在计数排序中，一般最大可适用于10^6的数据.....