【排序算法】—— 计数排序

一、简介

        计数排序，顾名思义就是记录数据出现的次数进行排序，时间复杂度为O(N+K)，空间复杂度为O(N)。只能用于整型，对于比力集中重复率比力高数据更为实用。
二、排序原理

比如对接下来这些数进行排序
                arr[11] = { 8,6,4,1,6,2,9,6,2,4,3 }
        界说一个tmp用来记录数字出现的次数，那么tmp的长度可以设为必要排序的最大的数字加1，因为我们要做的是用下标来表示这个数，
                比如tmp[6]=2，其中下标6表示6这个数字，2表示出现两次
        所以得先把tmp初始化为0，然后进行计数，比如第一个数字为1那么就在1下标位置加1，以此类推遍历完数组arr。然后根据每个数出现的个数依次赋值给原数组arr。

1. #include<stdio.h>
2. int main()
3. {
4.         int arr[11] = { 8,6,4,1,6,2,9,6,2,4,3 };
5.         int tmp[10] = { 0 };
6.         for (int i = 0; i < 11; i++)
7.                 tmp[arr[i]]++;
8.         for (int i = 0, j = 0; i < 10; i++)
9.         {
10.                 while (tmp[i]--)
11.                 {
12.                         arr[j++] = i;
13.                 }
14.         }
15.         for (int i = 0; i < 11; i++)
16.                 printf("%d ", arr[i]);
17.         return 0;
18. }

复制代码

        那这些数据比力大呢，比如下面这组数据
                {1004 1003 1000 1015 1004 1004 1012 1006 1003 1014}
        必要申请长为1015的数组巨细吗？
        实在并不必要，只必要申请长度为16的数组进行记录就行，记录的时候先减去1000，等赋值给原数组的时候再加回去就行。
        所以到底如何思量申请多少空间呢？，实在只必要最大的值减最小的值再加1的长度的数组空间就够用了。同样在记录时先减去最小值，等赋值给原数组的时候再加回去。

1. void Sort(int* arr, int size)
2. {
3.         int max = arr[0], min = arr[0];
4.         for (int i = 0; i < size; i++)
5.         {
6.                 if (max < arr[i])
7.                         max = arr[i];
8.                 if (min > arr[i])
9.                         min = arr[i];
10.         }
11.         int ret = max - min + 1;
12.         int* tmp = (int*)calloc(ret,sizeof(int));
13.         assert(tmp);
14.         for (int i = 0; i < size; i++)
15.                 tmp[arr[i]-min]++;
16.         for (int i = 0, j = 0; i < ret; i++)
17.         {
18.                 while (tmp[i]--)
19.                         arr[j++] = i + min;
20.         }
21. }

复制代码

三、实用范围

        计数排序的缺点就是只能对整型数据进行排序，不能对字符，浮点形还有布局体范例进行排序。而且对于整形的排序他更适合的是最小值和最大值跨度比力小的数据，或者重复率比力高的数据。比如10个整数最小的是1最大的谁人是100万。使用计数排序就会导致空间的开销很大，服从也比力低。
四、源码

1. #include<stdio.h>#include<stdlib.h>#include<assert.h>#include<time.h>void Sort(int* arr, int size)
2. {
3.         int max = arr[0], min = arr[0];
4.         for (int i = 0; i < size; i++)
5.         {
6.                 if (max < arr[i])
7.                         max = arr[i];
8.                 if (min > arr[i])
9.                         min = arr[i];
10.         }
11.         int ret = max - min + 1;
12.         int* tmp = (int*)calloc(ret,sizeof(int));
13.         assert(tmp);
14.         for (int i = 0; i < size; i++)
15.                 tmp[arr[i]-min]++;
16.         for (int i = 0, j = 0; i < ret; i++)
17.         {
18.                 while (tmp[i]--)
19.                         arr[j++] = i + min;
20.         }
21. }int main(){        srand((unsigned int)time(NULL));        int arr[15];        for (int i = 0; i < 15; i++)                arr[i] = rand() % 100 + 1;        for (int i = 0; i < 15; i++)                printf("%d ", arr[i]);        Sort(arr, 15);        printf("\n");        for (int i = 0; i < 15; i++)                printf("%d ", arr[i]);        return 0;}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。