各种各这样的排序算法：计数排序（*）

自由深渊

没看懂这算法什么意思

jerrychou

array[5] = {3, 5, 6, 5, 1}
buffer[7] = {0, 1, 0, 1, 0, 2, 1}
buffer[7] = {0, 1, 1, 2, 2, 4, 5}

i        array[i-1]        m=--buffer[array[i-1]]        sorted[m]
5        1                        0                                                sorted[0]=array[4]=1
4        5                        3                                                sorted[3]=array[3]=5
3        6                        4                                                sorted[4]=array[2]=6
2        5                        3                                                sorted[--3]=array[1]=5
1        3                        1                                                sorted[1]=array[0]=3

sorted[5] = {1, 3, 5, 5, 6}

夏天了

      直接遍历array[],记录元素个数存至c[],再循环输出效率会比较慢吗？

1. #include<stdio.h>
   
2. 
   
3. #define MAX 1024
   
4. void counting_sort( int array[],int length);
   
5. void counting_sort( int array[],int length)
   
6. {
   
7.     int t,n=0,j=0,i=0;
   
8.     int c[MAX]={0};
   
9.   
   
10.     for( j=0;j<length;j++ )
    
11.     {
    
12.          t = array[j];
    
13.          c[t] +=1;//直接记录array[]中某元素个数
    
14.     }
    
15. 
    
16.     while( n<length )
    
17.     {
    
18.         if( temp[i] != 0 )//按从小到大顺序输出array[]中元素
    
19.         {
    
20.             for( j=1; j<=temp[i]; j++ )
    
21.             {
    
22.                 printf("%d ",i);
    
23.                 n += 1;
    
24.             }
    
25.         }
    
26.         i++;
    
27.     }
    
28. 
    
29. 
    
30. }
    
31. int main(void)
    
32. {
    
33.     int i,length;
    
34.     int array[]={42,2,98,76,345,26,54,61,19,84};
    
35.     length = sizeof(array)/sizeof(array[0]);
    
36. 
    
37.     printf("original array is :\n");
    
38.     for( i=0;i<length;i++)
    
39.     {
    
40.         printf("%d ",array[i]);
    
41.     }
    
42.     putchar('\n');
    
43. 
    
44.     printf("after sorting is :\n");
    
45.     counting_sort(array,length);
    
46.     putchar('\n');
    
47. 
    
48.     return 0;
    
49. }
    

复制代码

MoukuC

夏天了 发表于 2019-10-6 11:46
直接遍历array[],记录元素个数存至c[],再循环输出效率会比较慢吗？

你这里在输出的时候还是通过嵌套的循环来进行比较的啊，两层循环嵌套的话时间复杂度会比较高，而且这样也算不上计数排序了，只能说这样排序不太好，继承了计数排序的空间复杂度和比较排序的时间复杂度

Acacia

全麻

波拉

1

ilovefishC5

MoukuC 发表于 2019-12-10 12:42
你这里在输出的时候还是通过嵌套的循环来进行比较的啊，两层循环嵌套的话时间复杂度会比较高，而且这样也 ...

看的我血压飙升，他算法里的循环嵌套只是把小甲鱼的两道循环整合在了一起，外层循环k次，内层共循环n次，时间效率n+k完全没变，同时算法的核心步骤buffer[array[i]]++也没有改变，是完完全全无可置疑的计数排序。别不懂装懂误人子弟

3192575523

人麻了，┭┮﹏┭┮

Puppet16

好好学习才能天天向上！

阿伟同学

没看懂我敲