排序算法大集锦_线性时间_计数排序
这个之前在《编程珠玑》上面看到过,当时就感觉特别神奇!
速度突破了其他排序算法的下限
后来在《算法导论》上面又看到了,感触颇深!所以一定好好啃透《算法导论》
这一系列博客的特点就是——给出每趟排序的结果
本来想着好好写一下过程,弄个图片什么的,不过觉得网上的解析太多了,都比较好,所以这些博客就算是对自己的总结吧。
#include <stdio.h> #include <string.h> int a[10]={2,8,6,7,3,3,1,9,6,0}; int b[10],c[10]; void CountSort(int *a, int *b, int n) { int i; //c[i]表示,a[0...9]中,i出现的次数 for(i=0;i<=n;i++) c[a[i]]=c[a[i]]+1; //c[i]表示,a[0...9]中,i/<=i的数 出现的次数 for(i=1;i<=n;i++) c[i]=c[i]+c[i-1]; //向数组b中放置元素 for(i=n;i>=0;i--) { b[c[a[i]]-1]=a[i]; //!防止a[i]中有重复的元素 c[a[i]]-=1; } } int main() { int i; for(i=0;i<10;i++) printf("%d ",a[i]); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); printf("\n排序后\n"); CountSort(a,b,9); for(i=0;i<10;i++) printf("%d ",b[i]); printf("\n"); return 0; }
之前看《编程珠玑》的时候,也写了一个类似的,不过有不如上面的那个强大
#include <stdio.h> void SpecialSort(int *m, int n) { int i,mm[10]; for(i=0;i<n;i++) mm[i]=m[i]; for(i=0;i<n;i++) m[mm[i]-1]=mm[i]; } int main() { int i; int a[10]={2,8,5,7,4,3,1,9,6,10}; for(i=0;i<10;i++) printf("%d ",a[i]); printf("\n排序后\n"); SpecialSort(a,10); for(i=0;i<10;i++) printf("%d ",a[i]); printf("\n"); return 0; }
运行之后
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。