programming

计数排序算法：非比较的线性排序

算法原理

计数排序（Counting Sort）是一种非比较排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

基本思想

  1. 统计频次：统计每个值出现的次数
  2. 计算位置：根据频次计算每个值的起始位置
  3. 放置元素：将元素放到正确位置
  4. 输出结果：得到排序后的数组

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void counting_sort(int arr[], int n, int max_value) {
    // 创建计数数组
    int* count = (int*)calloc(max_value + 1, sizeof(int));
    int* output = (int*)malloc(n * sizeof(int));
    
    // 统计每个元素的出现次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    
    // 计算累积计数
    for (int i = 1; i <= max_value; i++) {
        count[i] += count[i - 1];
    }
    
    // 从后向前构建输出数组（保持稳定性）
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    free(count);
    free(output);
}

// 处理负数的计数排序
void counting_sort_with_negative(int arr[], int n) {
    if (n <= 0) return;
    
    // 找到最大值和最小值
    int max_val = arr[0], min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) max_val = arr[i];
        if (arr[i] < min_val) min_val = arr[i];
    }
    
    int range = max_val - min_val + 1;
    int* count = (int*)calloc(range, sizeof(int));
    int* output = (int*)malloc(n * sizeof(int));
    
    // 统计频次（使用偏移）
    for (int i = 0; i < n; i++) {
        count[arr[i] - min_val]++;
    }
    
    // 累积计数
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    // 构建输出数组
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i] - min_val] - 1] = arr[i];
        count[arr[i] - min_val]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[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]);
    int max_value = 8;
    
    printf("原数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    counting_sort(arr, n, max_value);
    
    printf("排序后: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

复杂度分析

  • 时间复杂度：O(n + k)，其中k是数据范围
  • 空间复杂度：O(k)
  • 稳定性：稳定

优缺点

优点

  1. 时间复杂度是线性的
  2. 稳定排序
  3. 不是基于比较的排序

缺点

  1. 只能用于整数排序
  2. 当数据范围很大时，空间复杂度很高
  3. 不适用于稀疏数据

版权所有，如有侵权请联系我