programming

计数排序算法解析：非比较排序的线性时间解决方案

计数排序是一种非比较排序算法，其核心思想是统计每个元素出现的次数，然后根据统计结果重建有序序列。当输入元素的范围不大时，计数排序具有线性时间复杂度。

1. 算法原理

1.1 基本思想

计数排序的核心思想：

  1. 统计频次：统计每个元素出现的次数
  2. 累积计数：计算每个元素在输出数组中的位置
  3. 构建输出：根据统计信息构建有序数组

1.2 算法步骤

1
2
3
4
5
6
7
8
9
10
11
12
输入数组: [4, 2, 2, 8, 3, 3, 1]
数据范围: 1-8

步骤1: 统计频次
count[1] = 1, count[2] = 2, count[3] = 2, count[4] = 1, count[8] = 1

步骤2: 累积计数
count[1] = 1, count[2] = 3, count[3] = 5, count[4] = 6, count[8] = 7

步骤3: 构建输出
从右到左扫描原数组，根据累积计数确定位置
结果: [1, 2, 2, 3, 3, 4, 8]

2. C语言实现

2.1 基础版本

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 寻找数组中的最大值和最小值
void find_range(int arr[], int n, int* min_val, int* max_val) {
    *min_val = *max_val = arr[0];
    
    for (int i = 1; i < n; i++) {
        if (arr[i] < *min_val) {
            *min_val = arr[i];
        }
        if (arr[i] > *max_val) {
            *max_val = arr[i];
        }
    }
}

// 基础计数排序实现
void counting_sort_basic(int arr[], int n) {
    printf("开始计数排序...\n");
    
    // 步骤1: 找到数据范围
    int min_val, max_val;
    find_range(arr, n, &min_val, &max_val);
    int range = max_val - min_val + 1;
    
    printf("数据范围: [%d, %d], 范围大小: %d\n", min_val, max_val, range);
    
    // 步骤2: 创建计数数组
    int* count = (int*)calloc(range, sizeof(int));
    
    // 步骤3: 统计每个元素的出现次数
    printf("\n统计频次:\n");
    for (int i = 0; i < n; i++) {
        count[arr[i] - min_val]++;
    }
    
    for (int i = 0; i < range; i++) {
        if (count[i] > 0) {
            printf("值 %d 出现 %d 次\n", i + min_val, count[i]);
        }
    }
    
    // 步骤4: 重建排序数组
    printf("\n重建数组:\n");
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            printf("放置值 %d 到位置 %d\n", i + min_val, index);
            arr[index++] = i + min_val;
            count[i]--;
        }
    }
    
    free(count);
}

// 测试基础计数排序
void test_basic_counting_sort() {
    printf("=== 基础计数排序测试 ===\n");
    
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    counting_sort_basic(arr, n);
    
    printf("\n最终结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

2.2 稳定版本

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// 稳定的计数排序实现
void counting_sort_stable(int arr[], int n) {
    if (n <= 1) return;
    
    // 找到范围
    int min_val, max_val;
    find_range(arr, n, &min_val, &max_val);
    int range = max_val - min_val + 1;
    
    // 创建计数数组和输出数组
    int* count = (int*)calloc(range, sizeof(int));
    int* output = (int*)malloc(n * sizeof(int));
    
    printf("稳定计数排序过程:\n");
    
    // 统计频次
    for (int i = 0; i < n; i++) {
        count[arr[i] - min_val]++;
    }
    
    printf("频次统计: ");
    for (int i = 0; i < range; i++) {
        if (count[i] > 0) {
            printf("%d:%d ", i + min_val, count[i]);
        }
    }
    printf("\n");
    
    // 计算累积计数
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    printf("累积计数: ");
    for (int i = 0; i < range; i++) {
        if (count[i] > 0) {
            printf("%d:%d ", i + min_val, count[i]);
        }
    }
    printf("\n");
    
    // 从右到左构建输出数组（保证稳定性）
    printf("\n构建过程:\n");
    for (int i = n - 1; i >= 0; i--) {
        int val = arr[i];
        int pos = count[val - min_val] - 1;
        output[pos] = val;
        count[val - min_val]--;
        printf("元素 %d 放置到位置 %d\n", val, pos);
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    free(count);
    free(output);
}

// 稳定性验证
typedef struct {
    int value;
    char id;
} StableElement;

void print_stable_elements(StableElement arr[], int n, const char* title) {
    printf("%s: ", title);
    for (int i = 0; i < n; i++) {
        printf("(%d,%c) ", arr[i].value, arr[i].id);
    }
    printf("\n");
}

void counting_sort_stable_elements(StableElement arr[], int n) {
    if (n <= 1) return;
    
    // 找到范围（假设value都是正数）
    int min_val = arr[0].value, max_val = arr[0].value;
    for (int i = 1; i < n; i++) {
        if (arr[i].value < min_val) min_val = arr[i].value;
        if (arr[i].value > max_val) max_val = arr[i].value;
    }
    
    int range = max_val - min_val + 1;
    int* count = (int*)calloc(range, sizeof(int));
    StableElement* output = (StableElement*)malloc(n * sizeof(StableElement));
    
    // 统计频次
    for (int i = 0; i < n; i++) {
        count[arr[i].value - min_val]++;
    }
    
    // 计算累积计数
    for (int i = 1; i < range; i++) {
        count[i] += count[i - 1];
    }
    
    // 从右到左构建输出
    for (int i = n - 1; i >= 0; i--) {
        int val = arr[i].value;
        int pos = count[val - min_val] - 1;
        output[pos] = arr[i];
        count[val - min_val]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    free(count);
    free(output);
}

// 测试稳定性
void test_counting_sort_stability() {
    printf("=== 计数排序稳定性测试 ===\n");
    
    StableElement arr[] = {
        {4, 'A'}, {2, 'B'}, {2, 'C'}, {4, 'D'}, {1, 'E'}, {2, 'F'}
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    print_stable_elements(arr, n, "排序前");
    counting_sort_stable_elements(arr, n);
    print_stable_elements(arr, n, "排序后");
    
    printf("分析: 相同值的元素保持原有顺序，计数排序是稳定的\n\n");
}

2.3 优化版本

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// 优化版本：处理负数
void counting_sort_with_negatives(int arr[], int n) {
    if (n <= 1) return;
    
    int min_val, max_val;
    find_range(arr, n, &min_val, &max_val);
    
    printf("处理包含负数的数组，范围: [%d, %d]\n", min_val, max_val);
    
    int range = max_val - min_val + 1;
    int* count = (int*)calloc(range, sizeof(int));
    
    // 统计（使用偏移量处理负数）
    for (int i = 0; i < n; i++) {
        count[arr[i] - min_val]++;
    }
    
    // 重建数组
    int index = 0;
    for (int i = 0; i < range; i++) {
        int value = i + min_val;
        while (count[i] > 0) {
            arr[index++] = value;
            count[i]--;
        }
    }
    
    free(count);
}

// 内存优化版本：适用于稀疏数据
typedef struct {
    int value;
    int count;
} CountPair;

int compare_pairs(const void* a, const void* b) {
    CountPair* pair1 = (CountPair*)a;
    CountPair* pair2 = (CountPair*)b;
    return pair1->value - pair2->value;
}

void counting_sort_sparse(int arr[], int n) {
    printf("稀疏数据优化计数排序:\n");
    
    // 创建值-计数对数组
    CountPair* pairs = (CountPair*)malloc(n * sizeof(CountPair));
    int unique_count = 0;
    
    // 统计唯一值
    for (int i = 0; i < n; i++) {
        int found = 0;
        for (int j = 0; j < unique_count; j++) {
            if (pairs[j].value == arr[i]) {
                pairs[j].count++;
                found = 1;
                break;
            }
        }
        if (!found) {
            pairs[unique_count].value = arr[i];
            pairs[unique_count].count = 1;
            unique_count++;
        }
    }
    
    printf("发现 %d 个唯一值\n", unique_count);
    
    // 排序值-计数对
    qsort(pairs, unique_count, sizeof(CountPair), compare_pairs);
    
    // 重建数组
    int index = 0;
    for (int i = 0; i < unique_count; i++) {
        for (int j = 0; j < pairs[i].count; j++) {
            arr[index++] = pairs[i].value;
        }
        printf("值 %d 出现 %d 次\n", pairs[i].value, pairs[i].count);
    }
    
    free(pairs);
}

// 测试优化版本
void test_optimized_counting_sort() {
    printf("=== 优化版本测试 ===\n");
    
    // 测试包含负数的情况
    int arr1[] = {-5, -1, 0, 3, -2, 1, -1, 2};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("包含负数的数组:\n");
    printf("排序前: ");
    for (int i = 0; i < n1; i++) printf("%d ", arr1[i]);
    printf("\n");
    
    counting_sort_with_negatives(arr1, n1);
    
    printf("排序后: ");
    for (int i = 0; i < n1; i++) printf("%d ", arr1[i]);
    printf("\n\n");
    
    // 测试稀疏数据
    int arr2[] = {1000, 5, 1000, 2000, 5, 2000, 10};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    
    printf("稀疏数据数组:\n");
    printf("排序前: ");
    for (int i = 0; i < n2; i++) printf("%d ", arr2[i]);
    printf("\n");
    
    counting_sort_sparse(arr2, n2);
    
    printf("排序后: ");
    for (int i = 0; i < n2; i++) printf("%d ", arr2[i]);
    printf("\n\n");
}

3. 算法分析

3.1 时间复杂度分析

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
typedef struct {
    int n;              // 输入大小
    int k;              // 数据范围
    double time_taken;  // 执行时间
    int memory_used;    // 内存使用
} CountingSortStats;

void analyze_time_complexity() {
    printf("=== 时间复杂度分析 ===\n");
    
    printf("计数排序的时间复杂度:\n");
    printf("- 统计频次: O(n)\n");
    printf("- 计算累积: O(k)\n");
    printf("- 构建输出: O(n)\n");
    printf("- 总时间复杂度: O(n + k)\n\n");
    
    printf("空间复杂度: O(k) - k为数据范围\n\n");
    
    // 测试不同的n和k值
    printf("性能测试（不同的n和k值）:\n");
    printf("%-8s %-8s %-15s %-15s\n", "n", "k", "时间(秒)", "内存(KB)");
    printf("----------------------------------------\n");
    
    int test_cases[][2] = {{1000, 100}, {1000, 1000}, {10000, 100}, {10000, 1000}};
    
    for (int t = 0; t < 4; t++) {
        int n = test_cases[t][0];
        int k = test_cases[t][1];
        
        int* arr = (int*)malloc(n * sizeof(int));
        srand(42);
        
        // 生成范围为[0, k-1]的随机数据
        for (int i = 0; i < n; i++) {
            arr[i] = rand() % k;
        }
        
        clock_t start = clock();
        counting_sort_basic(arr, n);
        clock_t end = clock();
        
        double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
        int memory_kb = k * sizeof(int) / 1024;
        
        printf("%-8d %-8d %-15.6f %-15d\n", n, k, time_taken, memory_kb);
        
        free(arr);
    }
    printf("\n");
}

3.2 适用性分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void analyze_applicability() {
    printf("=== 适用性分析 ===\n");
    
    printf("计数排序的适用条件:\n");
    printf("1. 输入元素范围有限 (k << n²)\n");
    printf("2. 元素为非负整数或能映射为非负整数\n");
    printf("3. 内存允许创建大小为k的数组\n\n");
    
    printf("性能对比分析:\n");
    printf("%-15s %-15s %-15s %-15s\n", "数据特征", "计数排序", "快速排序", "归并排序");
    printf("---------------------------------------------------------------\n");
    printf("%-15s %-15s %-15s %-15s\n", "小范围整数", "O(n+k)", "O(n log n)", "O(n log n)");
    printf("%-15s %-15s %-15s %-15s\n", "大范围整数", "O(n+k)差", "O(n log n)", "O(n log n)");
    printf("%-15s %-15s %-15s %-15s\n", "重复元素多", "O(n+k)优", "O(n log n)", "O(n log n)");
    printf("%-15s %-15s %-15s %-15s\n", "稳定性", "稳定", "不稳定", "稳定");
    printf("%-15s %-15s %-15s %-15s\n", "空间复杂度", "O(k)", "O(log n)", "O(n)");
    printf("\n");
}

4. 优缺点与应用

4.1 优点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void counting_sort_advantages() {
    printf("=== 计数排序的优点 ===\n");
    
    printf("1. 线性时间复杂度\n");
    printf("   - 在适用条件下为O(n+k)\n");
    printf("   - 不受数据分布影响\n\n");
    
    printf("2. 稳定排序\n");
    printf("   - 保持相等元素的相对位置\n");
    printf("   - 适合多关键字排序\n\n");
    
    printf("3. 非比较排序\n");
    printf("   - 不依赖元素比较\n");
    printf("   - 突破了比较排序的下界\n\n");
    
    printf("4. 易于理解和实现\n");
    printf("   - 算法逻辑简单直观\n");
    printf("   - 代码实现相对简单\n\n");
}

4.2 缺点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void counting_sort_disadvantages() {
    printf("=== 计数排序的缺点 ===\n");
    
    printf("1. 适用范围有限\n");
    printf("   - 仅适用于整数或可映射为整数的数据\n");
    printf("   - 数据范围必须事先已知且不能太大\n\n");
    
    printf("2. 空间复杂度高\n");
    printf("   - 需要O(k)额外空间\n");
    printf("   - 当k很大时内存消耗巨大\n\n");
    
    printf("3. 不适合稀疏数据\n");
    printf("   - 数据范围大但数据量小时效率低\n");
    printf("   - 浪费大量内存空间\n\n");
    
    printf("4. 无法处理负数和浮点数\n");
    printf("   - 需要额外处理才能支持\n");
    printf("   - 增加实现复杂度\n\n");
}

4.3 应用场景

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void counting_sort_applications() {
    printf("=== 应用场景 ===\n");
    
    printf("1. 年龄排序\n");
    printf("   - 年龄范围有限(0-150)\n");
    printf("   - 数据量可能很大\n\n");
    
    printf("2. 成绩排序\n");
    printf("   - 分数范围固定(0-100)\n");
    printf("   - 需要保持稳定性\n\n");
    
    printf("3. 字符统计\n");
    printf("   - ASCII字符范围有限\n");
    printf("   - 频率统计和排序\n\n");
    
    printf("4. 基数排序的组成部分\n");
    printf("   - 作为基数排序的子程序\n");
    printf("   - 按位排序\n\n");
    
    printf("5. 数据预处理\n");
    printf("   - 为其他算法准备有序数据\n");
    printf("   - 去重和统计\n\n");
}

5. 主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    printf("========================================\n");
    printf("       计数排序算法完整演示\n");
    printf("========================================\n\n");
    
    test_basic_counting_sort();
    test_counting_sort_stability();
    test_optimized_counting_sort();
    analyze_time_complexity();
    analyze_applicability();
    counting_sort_advantages();
    counting_sort_disadvantages();
    counting_sort_applications();
    
    printf("========================================\n");
    printf("            测试完成\n");
    printf("========================================\n");
    
    return 0;
}

6. 总结

计数排序是一种特殊的排序算法，具有以下特点：

核心优势

  • 线性时间: 在适用条件下达到O(n+k)
  • 稳定性: 保持相等元素的相对位置
  • 非比较: 突破比较排序的理论下界

应用价值

计数排序在特定场景下具有无可比拟的优势，特别是：

  • 数据范围有限的整数排序
  • 需要稳定性的排序需求
  • 作为复合算法的组成部分

设计思想

计数排序体现了”用空间换时间”的算法设计思想，通过额外的空间开销获得线性时间复杂度，是算法优化的重要策略之一。

理解计数排序有助于掌握非比较排序的核心思想，为学习基数排序、桶排序等算法奠定基础。

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