论坛 › 《带你学C带你飞》（语法篇） › 各种各这样的排序算法：计数排序（*）

小甲鱼 发表于 2016-12-10 02:39:51

已有 12 人购买  本主题需向作者支付 10 鱼币 才能浏览 购买主题

自由深渊 发表于 2017-3-5 14:47:47

没看懂这算法什么意思{:10_282:}

jerrychou 发表于 2019-3-19 15:08:47

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

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

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

夏天了 发表于 2019-10-6 11:46:23

      直接遍历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={0};

    for( j=0;j<length;j++ )
    {
         t = array;
         c +=1;//直接记录array[]中某元素个数
    }

    while( n<length )
    {
      if( temp != 0 )//按从小到大顺序输出array[]中元素
      {
            for( j=1; j<=temp; 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);

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

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

    return 0;
}

MoukuC 发表于 2019-12-10 12:42:17

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

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

Acacia 发表于 2020-2-12 22:55:40

全麻{:10_266:}

波拉 发表于 2021-8-25 21:40:58

1

ilovefishC5 发表于 2021-10-23 00:36:55

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

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

3192575523 发表于 2022-3-7 22:41:18

人麻了，┭┮﹏┭┮

Puppet16 发表于 2022-5-3 18:23:38

好好学习才能天天向上！

阿伟同学 发表于 2022-7-31 22:55:47

没看懂我敲{:10_266:}

查看完整版本: 各种各这样的排序算法：计数排序（*）