🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥
🏀一、计数排序
?计数排序：是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)(其中k是整数的范围)，快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法。
?二、计数排序思路
我们以以下的序列为例：
在对以上序列排序前，我们先建立一个新的数组，新数组的大小为原数组的最大值加1，也就是10（这样能保证新数组最大的下标是9）。
| 💉然后我们做一个映射处理，将第一个数组里面的值作为第二个数组的下标映射下来,而第二个数组里面存放的值就是第一个数组里面值出现的次数。 |
这里我们采用的是绝对映射，眼尖的同学已经发现了，现在我们只需要按照新数组下标的顺序去遍历新数组，依次按次数（也就是数组里面存的值）输出新数组的下标，按顺序赋值到原数组，那我们是不是就排好序了。
🏐三、代码实现
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//计数排序(优化前)
void CountSort1(int* arr, int n)
{
//找到最大值
int max = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
int range = max + 1;//开辟空间的数量
int* countArr = (int*)malloc(sizeof(int)*range);//开辟空间
//初始化数组全部为0
memset(countArr, 0, sizeof(int)*range);
//开始计数
for (int i = 0; i < n; i++)
{
countArr[arr[i]]++;
}
//开始排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (countArr[i]--)
{
arr[j] = i ;
j++;
}
}
free(countArr);
}
void Print(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
void test()
{
int arr[] = { 5,8,5,4,6,8,9,7,2,3,4,5 };
int n = sizeof(arr) / sizeof(arr[0]);
CountSort1(arr, n);
Print(arr, n);
}
int main()
{
test();
return 0;
}
运行结果如下图所示：
看来我们写的逻辑确实是对的。但是我们来排一下下面这个序列
int arr[] = { -5,8,5,4,6,8,9,7,2,3,4,5 };
运行结果为：
程序直接崩掉了。
简单解释一下这里为什么崩掉，这个序列和上面的序列差在哪？没错，就是负数问题。很明显，在开始往新数组里面计数时，计到负数时就已经存在数组越界问题了，因为数组下标没有负数。
而且程序还不止这一个问题，眼尖的小伙伴应该也已经想到了，如果待排序序列是下面这个：
int arr1[] = { 1001,1000,1020,999};
这个序列的特点就是数据跨度大，按照上面的思路，我们要开辟的空间数量为1000+1个这么多，但是0至998这么多的空间根本就没有数据映射，太浪费空间了，所以我们必须解决这个问题。
?四、解决问题
🌴为了解决上述的负数问题和空间浪费问题，这里我们采用相对映射的方法。具体思路就是，找到序列的最大值和最小值，则开辟的空间数range=max-min+1。关键的一步来了，我们在映射时，将每个数据减去序列的最小值，将这个值做为新数组的下标。在还原时，只需要加上这个最小值，就能还原出原来的值，同时还解决了负数问题。
接下来演示一下负数问题是怎么解决的。
还是拿这个例子
int arr[] = { -5,8,5,4,6,8,9,7,2,3,4,5 };
在映射时，开辟的空间数为最大值减去最小值加1，也就是
9-（-5）+1=15。每次映射时都用该值减去最小值也就是-5得到下标。
这样操作之后，-5成功被映射到下标为0上面了。并且解决了空间浪费问题。
🎱五、代码优化
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//计数排序(优化后)
void CountSort(int* arr, int n)
{
//找到序列中的最大值和最小值
int max = arr[0];
int min = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
int range = max - min + 1;//开辟空间的数量
int* countArr = (int*)malloc(sizeof(int)*range);//开辟空间
//初始化数组全部为0
memset(countArr, 0, sizeof(int)*range);
//开始计数
for (int i = 0; i < n; i++)
{
countArr[arr[i]-min]++;
}
//开始排序
int j = 0;
for (int i = 0; i < range; i++)
{
while (countArr[i]--)
{
arr[j] = i + min;
j++;
}
}
free(countArr);
}
void Print(int* arr, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
void test()
{
int arr[] = { -5,8,5,4,6,8,9,7,2,3,4,5 };
int n = sizeof(arr) / sizeof(arr[0]);
CountSort(arr, n);
Print(arr, n);
}
int main()
{
test();
return 0;
}
运行结果如下：
由此可见，问题被很好的解决了。
🏈六、计数排序的优缺点
缺点1：不能对小数进行排序；
缺点2：空间复杂度O（range），空间浪费不能彻底的解决。
比如以下序列：
int arr1[] = { 1,2,3,5,8,100000000,10000000000};
优点：时间复杂度为：O（N+range），对集中的数据排序效率极高。