C++ 计数排序详解 - 威海悦创

1. 知识点介绍

计数排序是一种非比较型的排序算法，其核心思想是通过统计待排序元素中每个元素出现的次数，然后按照元素的大小顺序依次输出元素。计数排序的时间复杂度为O(n+k)，其中n是待排序元素的数量，k是元素的取值范围。

计数排序的特点：

适用于数据范围较小的情况
不需要进行元素之间的比较
时间复杂度较低
需要额外的存储空间

计数排序的基本步骤：

找出待排序数组中的最大值和最小值
创建一个计数数组，用于统计每个元素出现的次数
根据计数数组中的数据，将原数组中的元素按照顺序重新排列

2. 基本操作

2.1 声明与初始化

在实现计数排序时，需要声明并初始化原数组和计数数组。


#include <iostream>
using namespace std;

int main() {
    // 原数组
    int arr[] = {4, 2, 3, 1, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // 找出最大值和最小值
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    
    // 创建计数数组
    int count[max - min + 1] = {0};
    
    return 0;

2.2 访问元素

通过遍历原数组，统计每个元素出现的次数并存储到计数数组中。


#include <iostream>
using namespace std;

int main() {
    int arr[] = {4, 2, 3, 1, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    
    int count[max - min + 1] = {0};
    
    // 统计元素出现次数
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    
    return 0;

2.3 遍历数组

根据计数数组中的数据，将原数组中的元素按照顺序重新排列。


#include <iostream>
using namespace std;

int main() {
    int arr[] = {4, 2, 3, 1, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    
    int count[max - min + 1] = {0};
    
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    
    // 重新排列原数组
    int index = 0;
    for (int i = 0; i < max - min + 1; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
    
    return 0;

2.4 修改元素

在计数排序过程中，原数组的元素会被重新排列，因此需要修改原数组中的元素值。


#include <iostream>
using namespace std;

void countingSort(int arr[], int n) {
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    
    int* count = new int[max - min + 1]{0};
    
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    
    int index = 0;
    for (int i = 0; i < max - min + 1; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
    
    delete[] count;
}

int main() {
    int arr[] = {4, 2, 3, 1, 5, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    countingSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;

3. 应用场景

计数排序在实际开发中应用广泛，以下是一些常见场景：

对数据范围较小的数组进行排序
作为其他排序算法的基础步骤，如基数排序
处理统计类问题，如统计某个范围内元素的出现次数
用于需要高效排序且数据分布集中的场景

图：计数排序在不同场景中的应用示意

4. 对比分析

计数排序与其他排序算法的对比：

排序算法	时间复杂度	空间复杂度	稳定性	适用场景
计数排序	O(n+k)	O(k)	稳定	数据范围较小的情况
冒泡排序	O(n²)	O(1)	稳定	数据规模较小的情况
快速排序	O(nlogn)	O(logn)	不稳定	通用场景
归并排序	O(nlogn)	O(n)	稳定	对稳定性要求较高的场景

5. 练习题推荐

以下是一些有助于巩固计数排序知识的练习题：

目录