计数排序
2021-01-20 20:14
阅读：692
计数排序
排序思想： 对于数组 a[ ] 排序 ，先用数组c[ a[ i ] ] 记录其中的值出现的次数，然后计算前缀和；得出的值的意义就是 对于c[ a[i] ] 的值就是 对于所有的 a[ i ] 最后一个 a[ i ] 在数组中有序的排名，所以借助 ans[ ] 数组记录下标c[a[i] ] 的值为 a[i] ，- - c[ a [ i ] ] 就是 对于所有a[i] ，a[ i ] 的倒数第二个位置。
1/**计数排序 1~10以内的数*/
2#include
3#include
4#include
5void printArr(int a[],int n)
6{
7 for(int i=0;i 8 printf("%d%c",a[i],i==n-1?‘\n‘:‘ ‘);
9}
10void countSort(int a[],int n)
11{
12 int c[12];
13 for(int i=0;i11;i++)
14 c[i]=0;/**清空*/
15
16 for(int i=0;i17 c[a[i]]++;/**计数*/
18
19 for(int i=1;i20 c[i]+=c[i-1];/**前缀和*/
21
22 /**
23 有了前缀和后，数字最后一个a[j]的排名为c[a[j]]
24 所以访问每个数字时，只是把a[j]放到对应的名次上
25 因为可能有多个a[j],所以名次可以从最后一个向前分配
26 */
27 int ans[12];
28 for(int j=n-1;j>=0;j--)
29 {
30 ans[--c[a[j]]]=a[j];
31 }
32 printf("排序后：\n");
33 printArr(ans,10);
34}
35int main()
36{
37 int a[12];
38 int n=10;
39 /*srand函数设定rand函数所用随机数演算法的种子值*/
40 //srand(time(NULL));
41 /*time(t) t==NULL 返回当前时间，若非空：返回当前时间的同时，将返回值赋予t 指向的内存空间*/
42 for(int i=0;i43 a[i]=rand()%7+1;
44 printArr(a,10);
45 countSort(a,10);
46 return 0;
47}
评论
亲，登录后才可以留言！