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

自由深渊

没看懂这算法什么意思

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[],再循环输出效率会比较慢吗？

#include<stdio.h>

#define MAX 1024
void counting_sort( int array[],int length);
void counting_sort( int array[],int length)
{
    int t,n=0,j=0,i=0;
    int c[MAX]={0};
  
    for( j=0;j<length;j++ )
    {
         t = array[j];
         c[t] +=1;//直接记录array[]中某元素个数
    }

    while( n<length )
    {
        if( temp[i] != 0 )//按从小到大顺序输出array[]中元素
        {
            for( j=1; j<=temp[i]; j++ )
            {
                printf("%d ",i);
                n += 1;
            }
        }
        i++;
    }


}
int main(void)
{
    int i,length;
    int array[]={42,2,98,76,345,26,54,61,19,84};
    length = sizeof(array)/sizeof(array[0]);

    printf("original array is :\n");
    for( i=0;i<length;i++)
    {
        printf("%d ",array[i]);
    }
    putchar('\n');

    printf("after sorting is :\n");
    counting_sort(array,length);
    putchar('\n');

    return 0;
}

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

好好学习才能天天向上！

阿伟同学

没看懂我敲