CSP-J算法基础 计数排序

前言

计数排序

计数排序（Counting Sort）是一种线性时间复杂度的排序算法，适用于范围有限的整数排序。它通过计数每个值出现的次数，依次排列这些值。该算法不通过比较元素大小进行排序，而是根据值的分布情况完成排序。

计数排序的过程

假设我们有一个数组 [4, 2, 2, 8, 3, 3, 1]，需要对它进行升序排序。

1. 初始数组：
   [4, 2, 2, 8, 3, 3, 1]

2. 找到最大值和最小值：
   计数数组大小的公式是：

其中：

• 最大值 是输入数组中的最大元素；
• 最小值 是输入数组中的最小元素；
• 加上 1 是为了包括最大值和最小值之间的所有可能值。

这个公式确保计数数组有足够的空间来记录所有输入数组中可能的整数值的出现次数。

• 最大值是 8，最小值是 1。因此，计数数组的大小为 8 - 1 + 1 = 8。

3. 构建计数数组：

   • 创建一个大小为 8 的计数数组 count，初始时所有值为 0。即：
     [0, 0, 0, 0, 0, 0, 0, 0]

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

   • 遍历输入数组，并增加计数数组对应位置的值：
     • 数字 4：count[4 - 1]++，count 变为 [0, 0, 0, 1, 0, 0, 0, 0]
     • 数字 2：count[2 - 1]++，count 变为 [0, 1, 0, 1, 0, 0, 0, 0]
     • 数字 2：count[2 - 1]++，count 变为 [0, 2, 0, 1, 0, 0, 0, 0]
     • 数字 8：count[8 - 1]++，count 变为 [0, 2, 0, 1, 0, 0, 0, 1]
     • 数字 3：count[3 - 1]++，count 变为 [0, 2, 1, 1, 0, 0, 0, 1]
     • 数字 3：count[3 - 1]++，count 变为 [0, 2, 2, 1, 0, 0, 0, 1]
     • 数字 1：count[1 - 1]++，count 变为 [1, 2, 2, 1, 0, 0, 0, 1]

   现在，计数数组显示了输入数组中每个元素出现的次数：
   [1, 2, 2, 1, 0, 0, 0, 1]

5. 累加计数数组：

   • 修改计数数组，使其变成累计计数数组。这表示每个数字应当出现在最终数组中的位置：
     • count[1] = count[0] + count[1] → [1, 3, 2, 1, 0, 0, 0, 1]
     • count[2] = count[1] + count[2] → [1, 3, 5, 1, 0, 0, 0, 1]
     • count[3] = count[2] + count[3] → [1, 3, 5, 6, 0, 0, 0, 1]
     • count[4] = count[3] + count[4] → [1, 3, 5, 6, 6, 0, 0, 1]
     • count[5] = count[4] + count[5] → [1, 3, 5, 6, 6, 6, 0, 1]
     • count[6] = count[5] + count[6] → [1, 3, 5, 6, 6, 6, 6, 1]
     • count[7] = count[6] + count[7] → [1, 3, 5, 6, 6, 6, 6, 7]

   累加后的计数数组为：
   [1, 3, 5, 6, 6, 6, 6, 7]

6. 构建排序后的数组：

   • 使用计数数组将输入数组中的每个元素放到正确的位置：
     • 数字 1：count[1 - 1]--，将 1 放入排序后的数组第 0 位。数组变为 [1, _, _, _, _, _, _]
     • 数字 2：count[2 - 1]--，将 2 放入排序后的数组第 2 位。数组变为 [1, _, 2, _, _, _, _]
     • 数字 2：count[2 - 1]--，将 2 放入排序后的数组第 1 位。数组变为 [1, 2, 2, _, _, _, _]
     • 数字 3：count[3 - 1]--，将 3 放入排序后的数组第 4 位。数组变为 [1, 2, 2, _, 3, _, _]
     • 数字 3：count[3 - 1]--，将 3 放入排序后的数组第 3 位。数组变为 [1, 2, 2, 3, 3, _, _]
     • 数字 4：count[4 - 1]--，将 4 放入排序后的数组第 5 位。数组变为 [1, 2, 2, 3, 3, 4, _]
     • 数字 8：count[8 - 1]--，将 8 放入排序后的数组第 6 位。数组变为 [1, 2, 2, 3, 3, 4, 8]

7. 最终结果：

   • 输入数组 [4, 2, 2, 8, 3, 3, 1] 被排序为 [1, 2, 2, 3, 3, 4, 8]。

总结

计数排序通过创建一个计数数组来记录每个元素出现的次数，然后使用这些计数信息将元素放置在正确的位置。这个算法的时间复杂度是 O(n+k)，其中 n 是输入数据的大小，k 是数据的取值范围。对于元素范围较小且数据量大的情况，计数排序表现非常出色。然而，当数据范围较大时，计数排序的空间复杂度较高，使用效果可能不理想。

代码实现计数排序

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

// 计数排序函数
void countingSort(int arr[], int n) {
    int i, max = arr[0], min = arr[0];

    // 找到数组中的最大值和最小值
    for (i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }

    printf("最大值: %d, 最小值: %d\n", max, min);

    // 计算计数数组的大小
    int range = max - min + 1;
    int *count = (int *)calloc(range, sizeof(int));  // 动态分配内存并初始化为0

    // 计算每个元素出现的次数
    for (i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }

    // 打印计数数组
    printf("计数数组:\n");
    for (i = 0; i < range; i++) {
        printf("%d ", count[i]);
    }
    printf("\n");

    // 将计数数组累加，调整为位置索引
    for (i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }

    // 打印累加后的计数数组
    printf("累加后的计数数组:\n");
    for (i = 0; i < range; i++) {
        printf("%d ", count[i]);
    }
    printf("\n");

    // 创建输出数组
    int *output = (int *)malloc(n * sizeof(int));

    // 按照计数数组的值，构建排序后的数组
    //从后向前遍历排序 
    for (i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;  // 更新计数数组
    }

    // 打印排序后的数组
    printf("排序后的数组:\n");
    for (i = 0; i < n; i++) {
        arr[i] = output[i];
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 释放动态分配的内存
    free(count);
    free(output);
}

int main() {
    int arr[] = {5, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 调用计数排序
    countingSort(arr, n);

    return 0;
}

总结