十大排序算法——计数排序（C语言）_c语言计数排序

计数排序（适用于在一定范围内的整数排序，取值范围不是很大的情况下，效率快过时间复杂度为O（nlogn）的排序）

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

基本思想

首先根据原数组的大小创建一个相同的新数组，用于存放原数组中计数完毕的数据；对于一个待排序序列中的元素X，计算待排序序列中比X小的数，假如有A个，就把X放在新数组的第A个下标的位置上，依次计算第二个，第三个等等的数据，直到原数组的数据全部计数完毕，就得到了一个排序完成的新数组，在把新数组的数据全部赋值给原数组。

代码实现

#include<stdio.h>
#include<stdlib.h>

#define MAXNUM 80

//计数排序法
void Count_Sort(int a[],int n)
{
    int i,j,count,*data;
    data = (int *)malloc(sizeof(int)*n);   //动态分配内存空间
    for ( i = 0; i < n; i++)  //初始化data为0
    {
        data[i] = 0;
    }
    for ( i = 0; i < n; i++)
    {
        count = 0;     //计数值
        for ( j = 0; j < n; j++)  //扫描待排序数组
        {
            if (a[j] < a[i])  //统计比a[i]值小的值的个数
            {
                count++;
            }
            
        }
        while (data[count] != 0)//对于相等非0的数据，应向后措一位。数据为0时，因数组data被初始化为0，故不受影响。
        /* 注意此处应使用while循环进行判断，若用if条件则超过三个重复值后有0出现 */   
        {
            count++;
        }
        data[count] = a[i];  //把计数完毕的数据存放到data中的对应位置
        
    }
    for ( i = 0; i < n; i++)  //把排序完的数据复制到a中
    {
        a[i] = data[i];
    }
    free(data);  //释放data
    data = NULL;
    
    
}
void main()
{
    int i;
    /* int a[MAXNUM];
    printf("请输入十个待排序数据");
    for (int j = 0; j < MAXNUM; j++)
    {
        scanf("%d",&a[j]);
    } */
    int a[MAXNUM]={12,23,69,65,45,23,69,56,85,4212,23,69,65,45,23,69,56,85,42,12,23,69,65,45,23,69,56,85,4212,23,69,65,45,23,69,56,85,42,23,56,12,23,69,65,45,23,69,56,85,4212,23,69,65,45,23,69,56,85,42,12,23,69,65,45,23,69,56,85,4212,23,69,65,45,23,69,56,85,42,23,56};
    Count_Sort(a,MAXNUM);
    for ( i = 0; i < MAXNUM; i++)
    {
        printf("%d ",a[i]);
    }
    system("pause");   //防止控制台闪退
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

参考文献
漫画：什么是计数排序？
百度百科