计数排序
浏览数：72 /
时间：2015年06月08日
比较排序的极限是O(nlgn)
而计数排序非比较排序 他的复杂度只有O(n)
基本思想是：
1、统计a数组中每个数字出现的次数放在临时数组c中，c的大小为a中最大的数
2、在第一步统计的基础上遍历一遍统计小于等于i的数出现的次数即c[i]+=c[i-1]
3、通过数组c确定a[i]的位置，放在结果数组b中，出现相同元素的时候下一个相同元素的位置前移一位
代码如下：
1 #include<iostream> 2 #include<stdio.h> 3 #include<stdlib.h> 4 #define random(x) (rand()%x) 5 using namespace std; 6 7 void counting_sort(int *a,int *b,int n,int k){ 8 int *c=new int[k+1]; 9 memset(c,0,sizeof(int)*(k+1)); 10 int i; 11 for(i=0;i<n;i++) 12 c[a[i]]++; 13 for(i=1;i<=k;i++) 14 c[i]+=c[i-1]; 15 for(int j=n-1;j>=0;j--){ 16 b[c[a[j]]-1]=a[j]; 17 c[a[j]]--; 18 } 19 } 20 21 int main(){ 22 int a[100],b[100],max=0; 23 for(int i=0;i<100;i++){ 24 a[i]=random(1000); 25 if(a[i]>max) max=a[i]; 26 } 27 counting_sort(a,b,100,max); 28 for(int i=0;i<100;i++){ 29 cout<<b[i]<<" "; 30 } 31 cout<<endl; 32 return 0; 33 }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
