您现在的位置是：网站首页>技术百科技术百科

排序算法之计数排序 (Counting Sort)

小大寒2024-01-01[技术百科]博学多闻

排序算法之计数排序 (Counting Sort)计数排序（Counting Sort）是一种非比较排序算法，适用于数据范围有限且为非负整数的数组。通过统计每个元素出现的次数构造计数数组，按计数值累加确定排序位置。时间复杂度为O(n + k)，空间复杂度为O(k)。

排序算法之计数排序 (Counting Sort)

1. 基础概念

1.1 定义

计数排序是一种基于键值计数的分配排序算法。其核心思想是：

统计每个元素在输入数组中的出现次数。
根据统计结果生成一个累加计数数组，确定元素的排序位置。
最后根据累加计数数组将元素放入输出数组中。

1.2 特点

适用于离散且范围较小的整数排序。
时间复杂度较低，但需要额外空间存储计数数组。
是一种稳定的排序算法。

1.3 使用场景

排序考试成绩、年龄等范围有限的整数数据。
快速统计频率并生成排名或排序列表。

2. 实现与操作

2.1 核心操作实现

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // 计数排序函数
    void countingSort(int arr[], int size, int range) {
        // 创建计数数组并初始化为0
        int *count = (int *)calloc(range + 1, sizeof(int));
        int *output = (int *)malloc(size * sizeof(int));
    
        // 统计每个元素的出现次数
        for (int i = 0; i < size; i++) {
            count[arr[i]]++;
        }
    
        // 构建累加计数数组
        for (int i = 1; i <= range; i++) {
            count[i] += count[i - 1];
        }
    
        // 根据计数数组将元素放入输出数组
        for (int i = size - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }
    
        // 将结果复制回原数组
        for (int i = 0; i < size; i++) {
            arr[i] = output[i];
        }
    
        // 释放内存
        free(count);
        free(output);
    }
    
    // 主函数：演示计数排序
    int main() {
        int arr[] = {4, 2, 2, 8, 3, 3, 1};
        int size = sizeof(arr) / sizeof(arr[0]);
        int range = 8; // 最大值
    
        printf("排序前的数组: ");
        for (int i = 0; i < size; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    
        countingSort(arr, size, range);
    
        printf("排序后的数组: ");
        for (int i = 0; i < size; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    
        return 0;
    }
        </string.h></stdlib.h></stdio.h>

2.2 代码详解

calloc 用于初始化计数数组，确保所有值为 0。
累加计数数组构建了元素的排序索引。
从后往前遍历原数组，以确保计数排序的稳定性。
最后将输出数组结果复制回原数组。

3. 时间与空间复杂度分析

3.1 时间复杂度

构建计数数组：O(n)
累加计数：O(k)
输出排序：O(n)
总体时间复杂度：O(n + k)

3.2 空间复杂度

计数数组：O(k)
输出数组：O(n)
总体空间复杂度：O(n + k)

4. 优缺点与局限性

4.1 优点

速度快，适合排序范围有限的整数数组。
稳定性强，可用于需要保留相同值原顺序的场景。

4.2 缺点与局限性

对数据范围要求较高，范围大时效率降低。
需要额外空间存储计数数组。

5. 常见应用场景

5.1 实际应用

以下示例演示统计频率最高的数字：

    #include <stdio.h>
    #include <stdlib.h>
    
    int findMostFrequent(int arr[], int size, int range) {
        int *count = (int *)calloc(range + 1, sizeof(int));
    
        for (int i = 0; i < size; i++) {
            count[arr[i]]++;
        }
    
        int maxCount = 0, mostFrequent = -1;
        for (int i = 0; i <= range; i++) {
            if (count[i] > maxCount) {
                maxCount = count[i];
                mostFrequent = i;
            }
        }
    
        free(count);
        return mostFrequent;
    }
    
    int main() {
        int arr[] = {1, 3, 2, 3, 4, 3, 1};
        int size = sizeof(arr) / sizeof(arr[0]);
        int range = 4;
    
        int result = findMostFrequent(arr, size, range);
        printf("出现次数最多的数字是: %d\n", result);
    
        return 0;
    }
        </stdlib.h></stdio.h>