C语言计数排序（附带源码和解析）

计数排序是一种非比较性的整数排序算法，它的核心思想是通过统计每个元素出现的次数来实现排序。这种算法特别适用于对整数进行排序，尤其是当待排序的整数范围不是很大时。计数排序的时间复杂度为 O(n+k)，其中 n 是待排序元素的个数，k 是整数的范围。

计数排序的基本原理

计数排序的工作原理可以分为以下几个步骤：

1. 找出待排序数组中的最大值和最小值，确定整数范围。
2. 创建一个计数数组，用于统计每个整数出现的次数。
3. 遍历待排序数组，统计每个整数出现的次数。
4. 对计数数组进行累加，得到每个整数在排序后数组中的位置。
5. 创建一个输出数组，根据计数数组中的信息，将原数组中的元素放入正确的位置。
6. 将排序后的结果复制回原数组。

让我们通过一个具体的例子来深入理解计数排序的过程，假设要对数组 [4, 2, 2, 8, 3, 3, 1] 进行排序
 

1) 找出最大值和最小值：最小值为 1，最大值为 8。
 

2) 创建计数数组：计数数组的大小为 8（最大值） - 1（最小值） + 1 = 8。初始值都为 0。

count[] = [0, 0, 0, 0, 0, 0, 0, 0]
           1  2  3  4  5  6  7  8

3) 统计每个整数出现的次数：

count[] = [1, 2, 2, 1, 0, 0, 0, 1]
           1  2  3  4  5  6  7  8

4) 对计数数组进行累加：

count[] = [1, 3, 5, 6, 6, 6, 6, 7]
           1  2  3  4  5  6  7  8

5) 创建输出数组，并将原数组中的元素放入正确的位置：

从原数组的末尾开始遍历，对于每个元素：

• 最后一个元素是 1，count[1] = 1，将 1 放入输出数组的第 1 个位置，然后将 count[1] 减 1。
• 倒数第二个元素是 3，count[3] = 5，将 3 放入输出数组的第 5 个位置，然后将 count[3] 减 1。
• 依此类推...

6) 最终得到排序后的数组：[1, 2, 2, 3, 3, 4, 8]

C语言实现计数排序

下面是计数排序的 C 语言实现：

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

void countingSort(int arr[], int size) {
    int i, max = arr[0], min = arr[0];
    
    // 找出数组中的最大值和最小值
    for (i = 1; i < size; i++) {
        if (arr[i] > max)
            max = arr[i];
        if (arr[i] < min)
            min = arr[i];
    }
    
    int range = max - min + 1;
    
    // 创建计数数组
    int *count = (int *)calloc(range, sizeof(int));
    
    // 统计每个元素出现的次数
    for (i = 0; i < size; i++)
        count[arr[i] - min]++;
    
    // 计算累加和
    for (i = 1; i < range; i++)
        count[i] += count[i - 1];
    
    // 创建输出数组
    int *output = (int *)malloc(size * sizeof(int));
    
    // 将元素放入正确的位置
    for (i = size - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
    
    // 将排序后的结果复制回原数组
    for (i = 0; i < size; i++)
        arr[i] = output[i];
    
    // 释放动态分配的内存
    free(count);
    free(output);
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    printArray(arr, size);
    
    countingSort(arr, size);
    
    printf("排序后数组: ");
    printArray(arr, size);
    
    return 0;
}

运行结果：

原始数组: 4 2 2 8 3 3 1
排序后数组: 1 2 2 3 3 4 8 

总结

计数排序是一种简单而高效的整数排序算法，特别适用于整数范围不大的情况。通过统计每个元素出现的次数，计数排序可以在线性时间内完成排序，这使得它在某些特定场景下比比较排序算法更加高效。尽管计数排序有一些局限性，但在处理整数数据时，它仍然是一个强大的算法。
 

计数排序具有以下优点：

• 时间复杂度为 O(n+k)，在整数范围不大的情况下，效率非常高。
• 是一种稳定的排序算法，相同的元素在排序前后的相对位置不变。
• 适用于对整数或者可以转化为整数的数据进行排序。

计数排序也有一些局限性：

• 只适用于非负整数，如果要排序的数据是其他类型，需要进行转换。
• 当整数范围 k 远大于待排序数组的大小 n 时，会浪费大量空间。
• 不适用于排序浮点数或字符串等非整数类型的数据。

计数排序在以下场景中特别有用：

• 对年龄、成绩等范围有限的整数数据进行排序。
• 在需要统计某些整数出现次数的场景中，如词频统计。
• 作为基数排序的一个子过程，用于对数字的每一位进行排序。

你可能还想关注其它 9 种排序算法：

1. C语言冒泡排序（附带源码和解析）
2. C语言快速排序（附带源码和解析）
3. C语言选择排序（附带源码和解析）
4. C语言插入排序（附带源码和解析）
5. C语言希尔排序（附带源码和解析）
6. C语言归并排序（附带源码和解析）
7. C语言堆排序（附带源码和解析）
8. C语言桶排序（附带源码和解析）
9. C语言基数排序（附带源码和解析）

声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。