排序算法 -计数排序

1. 计数排序（Counting Sort）

1.1 简介

计数排序（Counting Sort）是一种非比较型整数排序算法，适用于一定范围内的整数排序。它的基本思想是通过计数来确定每个元素在排序后数组中的位置，从而实现排序。计数排序的时间复杂度为 O(n + k)，其中 n 是待排序数组的元素个数，k 是待排序元素的取值范围。

1.2 计数排序的步骤

计数排序（Counting Sort）是一种非比较型整数排序算法，适用于一定范围内的整数排序。它的基本思想是通过计数来确定每个元素在排序后数组中的位置，从而实现排序。计数排序的时间复杂度为 O(n + k)，其中 n 是待排序数组的元素个数，k 是待排序元素的取值范围。

1. 找出待排序数组中的最大值和最小值，以确定元素的取值范围。
2. 创建一个计数数组，其大小为最大值与最小值之差加一（因为包含边界值）。
3. 遍历待排序数组，统计每个元素出现的次数，并将结果存储在计数数组中。
4. 计算前缀和，以确定每个元素在排序后数组中的位置。
5. 创建输出数组，根据计数数组中的信息将元素放入正确的位置。

1.3 计数排序C语言实现

#include <stdio.h>
#include <stdlib.h>// 计数排序函数
void CountSort(int* a, int n) {// 初始化最大值和最小值为数组的第一个元素int max = a[0], min = a[0];// 遍历数组，找到最大值和最小值for (int i = 1; i < n; i++) { // 注意这里从1开始，因为第一个元素已经用于初始化if (a[i] > max)max = a[i]; // 更新最大值if (a[i] < min)min = a[i]; // 更新最小值}// 计算计数数组的大小，并动态分配内存int range = max - min + 1;int* count = (int*)malloc(range * sizeof(int));if (count == NULL) {// 内存分配失败处理（这里简单处理为退出程序，实际应用中可能需要更复杂的错误处理）fprintf(stderr, "Memory allocation failed\n");exit(EXIT_FAILURE);}// 初始化计数数组为0for (int i = 0; i < range; i++) {count[i] = 0;}// 统计每个元素出现的次数for (int i = 0; i < n; i++) {count[a[i] - min]++; // 使用元素值减去最小值作为计数数组的下标}// 重建排序后的数组int* output = (int*)malloc(n * sizeof(int));if (output == NULL) {// 内存分配失败处理free(count); // 释放已经分配的内存fprintf(stderr, "Memory allocation failed\n");exit(EXIT_FAILURE);}int index = 0; // 用于填充输出数组的索引for (int i = 0; i < range; i++) {// 对于每个在计数数组中出现的元素，将其填充到输出数组中while (count[i] > 0) {output[index] = i + min;index++;count[i]--;}}// 将排序后的数组复制回原数组for (int i = 0; i < n; i++) {a[i] = output[i];}// 释放动态分配的内存free(count);free(output);
}// 主函数，用于测试计数排序
int main() {int arr[] = {4, 2, 2, 8, 3, 3, 1};int n = sizeof(arr) / sizeof(arr[0]);// 调用计数排序函数CountSort(arr, n);// 打印排序后的数组for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

注释说明：

1. 初始化最大值和最小值：

   • 将数组的第一个元素赋值给最大值 max 和最小值 min。

2. 找到最大值和最小值：

   • 遍历数组（从第二个元素开始，因为第一个元素已经用于初始化），更新最大值和最小值。

3. 动态分配计数数组：

   • 根据最大值和最小值计算计数数组的大小（范围），并动态分配内存。
   • 检查内存分配是否成功，如果失败则处理错误（这里简单处理为退出程序）。
   • 初始化计数数组为0。

4. 统计每个元素出现的次数：

   • 遍历输入数组，使用元素值减去最小值作为计数数组的下标，统计每个元素的出现次数。

5. 重建排序后的数组：

   • 动态分配一个大小为 n 的输出数组。
   • 使用两个循环：外循环遍历计数数组，内循环（while 循环）根据计数数组的值将元素填充到输出数组中。
   • 注意，这里我们没有显式地计算前缀和，而是直接在填充输出数组时减少了计数数组的值。

6. 将排序后的数组复制回原数组：

   • 遍历输出数组，将排序后的元素复制回原数组。

7. 释放内存：

   • 释放计数数组和输出数组所占用的内存。

8. 主函数：

   • 初始化一个待排序的数组。
   • 调用计数排序函数。
   • 打印排序后的数组。

计数排序（Counting Sort）的时间复杂度和空间复杂度分析如下：

1.4 时间复杂度

1. 查找最大值和最小值：

   • 需要遍历整个数组一次，因此时间复杂度为 $O(n)$。

2. 初始化计数数组并统计元素出现次数：

   • 初始化计数数组的时间复杂度为 $O(k)$，其中 $k$ 是计数数组的大小（即输入数组中的最大值与最小值之差加一）。
   • 遍历输入数组并统计元素出现次数的时间复杂度为 $O(n)$。

3. 重建排序后的数组：

   • 遍历计数数组并根据其值填充输出数组的时间复杂度为 $O(n+k)$，但在最坏情况下（即所有元素都相同或非常接近时），这仍然可以看作是 $O(n)$，因为 $k$ 是由输入数据决定的，并且通常远小于 $n$ 的数量级时，我们可以忽略 $k$ 对时间复杂度的影响（但这取决于具体情况，如果 $k$ 和 $n$ 相近，则不能忽略）。

综上所述，计数排序的总时间复杂度在 $O(n+k)$，其中 $n$ 是输入数组的大小，$k$ 是输入数据的范围（最大值与最小值之差加一）。在输入数据范围较小的情况下，计数排序是非常高效的。

1.5 空间复杂度

• 计数数组：需要额外一个大小为 $k$ 的数组来存储每个元素的出现次数。
• 输出数组（如果单独分配）：在重建排序后的数组时，如果分配了一个单独的输出数组，则需要额外的 $n$ 个空间。但如前所述，这可以通过直接在原数组上重建来避免。