计数排序算法

计数排序

1.计数排序基本思想

2.计数排序代码

2.1.代码思路步骤

2.2.代码

3.代码解析

3.1.计数排序过程的解析

(1)为什么使用相对位置 a[i] - min 访问统计数组 countA？

(2)为什么在排序过程中使用 j + min？

4.计数排序的时间复杂度和空间复杂度的计算过程

4.1.时间复杂度

4.2.空间复杂度

5.总结

计数排序

1.计数排序基本思想

图形解析：

计数排序的思路是通过统计数组中每个元素出现的次数来进行排序，具体步骤如下：

找出数组中的最大值和最小值：确定数组中元素的范围，即最大值和最小值之间的差值。
开辟统计数组：根据元素的范围，开辟一个统计数组，用于记录每个元素出现的次数。
统计次数：遍历原数组，将每个元素的值作为统计数组下标，并增加对应下标的计数。
排序：遍历统计数组，根据统计数组中每个元素的值（即原数组中对应元素出现的次数），将元素值按顺序放回原数组。

总的来说，计数排序操作步骤主要有两点：①统计相同元素出现次数；②根据统计的结果将序列回收到原来的序列中。

2.计数排序代码

2.1.代码思路步骤

图形解析：

(1)确定范围

遍历数组找出最大值 max 和最小值 min。
计算范围 range = max - min + 1。

(2)初始化统计数组

使用 calloc 开辟大小为 range 的统计数组 countA，并将所有元素初始化为 0。

(3)统计元素出现次数

遍历原数组 a，对于每个元素 a[i]，计算其在统计数组中的位置 index = a[i] - min，并将 countA[index] 加 1。

(4)排序原数组

初始化一个索引 k 为 0，用于指向原数组 a 中下一个要填充的位置。
遍历统计数组 countA，对于每个下标 j，如果 countA[j] 大于 0，则执行以下操作：
- 将 j + min（即原数组的元素值）赋值给 a[k]。
- 将 countA[j] 减 1，并将 k 加 1。
- 如果 countA[j] 仍然大于 0，重复上述赋值和减一操作，直到 countA[j] 为 0。

(5)释放统计数组空间

使用 free 释放统计数组 countA 占用的动态分配内存。

2.2.代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>//时间复杂度:0(N+Range)
//空间复杂度:0(Range)
//适合范围集中的数据，只适合整形void CountSort(int* a, int n)
{//1.求出数组a中的最大、最小值以此确定数组a的范围从而决定开辟多大的统计数组空间。//1.1.假设数组a中的a[0]是最大、最小值int max = a[0], min = a[0]; //1.2.从左向右依次遍历数组a找出数组a中的最大、最小值for (int i = 1; i < n; ++i){if (a[i] < min)min = a[i];if(a[i] > max)max = a[i];}//2.利用range表示统计数组的大小，并用数组a的最大、最小值确定开辟多大的统计数组空间。int range = max - min + 1;//3.开辟range大小的统计数组countA//注意：利用calloc函数来开辟统计数组countA空间的同时把统计数组countA的所有元素初始化为0.int* countA = (int*)calloc(range, sizeof(int)); //3.1.判断统计数组countA是否开辟成功if (countA == NULL){perror("calloc fail\n");exit(-1);}//4.计数排序的过程//4.1.统计次数->统计思路：从左向右依次遍历数组a并统计数组a中每个元素出现的次数，并把数 组a中每个元素的值作为访问统计数组countA的下标，然后把数组a中每个元素出现的次数放到统计 数组A对应下标的位置。for(int i=0;i <n; ++i)countA[a[i]-min]++;//注意：由于我们是利用数组a的最大、最小值的差值来开辟统计数组countA的空间的，使得直接用 数组a的元素a[i]作为下标访问统计数组countA是不可行的，我们必须通过相对位置a[i]-min来访 问统计数组countA。//4.2.排序->排序思路：从左向右遍历整个统计数组countA，然后统计数组countA的每个元素的值 val是多少，就把val个的统计数组countA每个元素对应的下标j + min的值 从左向右依次存入数组 a中。int k=0;//4.2.1.从左向右遍历整个统计数组countAfor (int j = 0; j < range; ++j){//(1)while循环的作用是：统计数组countA的1个元素的值val是多少，就把val个的统计数组 countA该元素对应的下标j + min的值 从左向右依次存入数组a中。while (countA[j]--)a[k++] = j + min;//注意：由于我们是利用数组a的最大、最小值的差值来开辟统计数组countA的空间的，使得统计数 组countA的下标j不是数组a的元素，而是统计数组countA的下标j + min才是数组a的元素。}//5.释放掉统计数组countA的动态空间free(countA);
}

3.代码解析

3.1.计数排序过程的解析

//4.计数排序的过程
//4.1.统计次数
for(int i=0;i <n; ++i)countA[a[i]-min]++;//4.2.排序
int k=0;//4.2.1.从左向右遍历整个统计数组countA
for (int j = 0; j < range; ++j)
{while (countA[j]--)a[k++] = j + min;
}

(1)为什么使用相对位置 `a[i] - min` 访问统计数组 `countA`？

统计数组 countA 的大小：统计数组 countA 的大小是由数组 a 中的最大值 max 和最小值 min 决定的，具体大小为 range = max - min + 1。这样做是为了最小化统计数组所需的空间。
下标偏移：由于统计数组 countA 的大小是基于 max 和 min 的差值，它的下标范围是从 0 到 range - 1。如果我们直接使用数组 a 中的元素值 a[i] 作为下标访问 countA，那么可能会超出 countA 的下标范围，因为 a[i] 可能大于 min。为了解决这个问题，我们需要将 a[i] 转换为相对于 min 的偏移量，即 a[i] - min，这样就可以在 countA 中正确地访问对应的统计位置。
举例说明：假设数组 a 的最小值 min 是 3，最大值 max 是 7，那么 range 是 5，统计数组 countA 的大小就是 5。如果数组 a 中有一个元素是 5，那么在统计数组 countA 中，我们应该在位置 5 - 3 = 2 上增加计数，而不是在位置 5 上，因为 countA 的下标是从 0 开始的。

(2)为什么在排序过程中使用 `j + min`？

恢复原值：在排序过程中，我们需要将统计数组 countA 中统计的元素值恢复成数组 a 中的原始值。因为我们在统计时使用的是相对位置 a[i] - min，所以在将元素放回原数组时，我们需要将统计数组 countA 的下标 j 转换回数组 a 中的原始值，即 j + min。
举例说明：继续上面的例子，如果统计数组 countA 在位置 2 的计数是 3，这意味着原始数组 a 中有 3 个元素是 5（因为 5 - 3 = 2）。当我们需要将这些元素放回数组 a 时，我们应该放回的是值 5，而不是下标 2。因此，我们使用 j + min 来计算应该放回的值。

通过以上操作，计数排序能够正确地统计数组中每个元素的出现次数，并在排序过程中将这些元素按照正确的顺序放回原数组。

4.计数排序的时间复杂度和空间复杂度的计算过程

4.1.时间复杂度

计数排序的时间复杂度主要由以下几个步骤决定：

找出最大最小值：需要遍历整个数组一次，以找出数组中的最大值和最小值。这一步的时间复杂度是 O(N)，其中 N 是数组的长度。
开辟统计数组：这一步是常数时间操作，可以认为是 O(1)。
统计元素出现次数：需要再次遍历数组，将每个元素的值作为统计数组下标，并增加对应下标的计数。这一步的时间复杂度也是 O(N)。
排序原数组：需要遍历统计数组，并根据统计数组中的值将元素放回原数组。这一步的时间复杂度是 O(Range)，其中 Range 是数组中最大值和最小值的差加 1。

综合上述步骤，计数排序的总时间复杂度是 O(N) + O(N) + O(Range)，即 O(N + Range)。通常，如果 Range 不是一个很大的数，我们可以认为计数排序的时间复杂度接近于 O(N)。