今天的这个比较神奇，是一个线性复杂度的排序算法O(n)，算法导论在这一部分先证明了比较排序的复杂度下界是nlgn，所以基数排序不是基于比较的排序。
其实这种比较方法我们应该都接触过。假设输入的数都是三位以下的数（当然其他位数也可以，类比一下，这里就假设是三位数、两位数、一位数），那么只需要大致3n的复杂度就可以排好序。过程是这样：
先设置辅助空间t[0..9][n]
然后扫第一遍n个数，个位是几就放在t[几]那一行。然后扫一遍t数组，按顺序放回原数组中
然后扫第二遍n个数，十位是几就放在t[几]那一行。然后扫一遍t数组，按顺序放回原数组中
然后扫第三遍n个数，百位是几就放在t[几]那一行。然后扫一遍t数组，按顺序放回原数组中
现在原数组已经是按顺序排好的了。其实就是最原始的比较方法，先比较个位，再比较十位，再比较百位。
代码如下：（这里为了好理解先用冗长的代码，其实这里的代码还可以再简化，然后修改以后适用于任何位数）
#include<stdio.h> #include<string.h> int t[10][20]; int cou[10]; void jishusort(int *a,int l,int r) { memset(cou,0,sizeof(cou)); memset(t,0,sizeof(t)); int i; for (i=l;i<=r;i++) { int k=a[i]%10; t[k][cou[k]]=a[i]; cou[k]++; } int c=l; for (i=0;i<=9;i++) { int j; for (j=0;j<cou[i];j++) { a[c]=t[i][j]; c++; } } memset(cou,0,sizeof(cou)); memset(t,0,sizeof(t)); for (i=l;i<=r;i++) { int k=a[i]/10%10; t[k][cou[k]]=a[i]; cou[k]++; } c=l; for (i=0;i<=9;i++) { int j; for (j=0;j<cou[i];j++) { a[c]=t[i][j]; c++; } } memset(cou,0,sizeof(cou)); memset(t,0,sizeof(t)); for (i=l;i<=r;i++) { int k=a[i]/100; t[k][cou[k]]=a[i]; cou[k]++; } c=l; for (i=0;i<=9;i++) { int j; for (j=0;j<cou[i];j++) { a[c]=t[i][j]; c++; } } } int main() { int n; scanf("%d",&n); int i; int a[20]={}; for (i=1;i<=n;i++) { scanf("%d",&a[i]); } jishusort(a,1,n); for (i=1;i<=n;i++) { printf("%d |",a[i]); } return 0; }
在这之前，书中还讲了一个计数排序，也是一种线性复杂度的算法。大体思想是这样：如果输入的数一定在1..k之间，那么对于每一个输入的元素x，确定出小组x的元素个数。利用这一信息就可以直接把x放在输出数组的相应位置了。算法导论里的伪代码真的太厉害了，用了几个线性的操作就实现了上面的思想。
下面是代码：（按照输入的数不超过100写的）
#include<stdio.h> #include<string.h> int c[101]; void ji4shusort(int *a,int *b,int k,int n) { memset(c,0,sizeof(c)); int i; for (i=1;i<=n;i++) { c[a[i]]++; } for (i=1;i<=k;i++) { c[i]+=c[i-1]; } for (i=1;i<=n;i++) { b[c[a[i]]]=a[i]; c[a[i]]--; } for (i=1;i<=n;i++) a[i]=b[i]; } int main() { int n; scanf("%d",&n); int i; int a[20]={},b[20]={}; int max=0; for (i=1;i<=n;i++) { scanf("%d",&a[i]); if (a[i]>max) max=a[i]; } ji4shusort(a,b,max,n); for (i=1;i<=n;i++) { printf("%d |",a[i]); } return 0; }
可以注意到上面两个算法基本上只适用于排整数。
然后书上又讲了桶排序，目测虽然思想和基数排序差不多，但好像略复杂一些，以后有机会再研究。部分习题也不好意思先略过了。