简介

在计算机科学中，排序算法是将一组数据按照特定顺序排列的算法。计数排序（Counting Sort）是一种非比较排序算法，它利用数组下标的映射关系来实现排序。与基于比较的排序算法（如冒泡排序、快速排序）不同，计数排序的时间复杂度可以达到线性级别，在特定条件下能够显著提高排序效率。本文将深入探讨C语言中计数排序的基础概念、使用方法、常见实践以及最佳实践。

目录

  1. 计数排序基础概念
    • 什么是计数排序
    • 计数排序的原理
  2. C语言中计数排序的使用方法
    • 基本步骤
    • 代码示例
  3. 常见实践
    • 对整数数组排序
    • 处理不同范围的整数
  4. 最佳实践
    • 优化空间复杂度
    • 稳定性的保证
  5. 小结

计数排序基础概念

什么是计数排序

计数排序是一种排序算法，它通过统计每个元素在输入数组中出现的次数，然后利用这些统计信息将元素按顺序输出到新的数组中。它适用于元素范围相对较小且为整数的情况。

计数排序的原理

计数排序的核心思想是创建一个额外的数组，该数组的下标对应输入数组中的元素值，数组的值则记录该元素出现的次数。具体步骤如下：

  1. 统计计数：遍历输入数组，统计每个元素出现的次数，并将其记录在计数数组中。
  2. 累加计数：对计数数组进行累加操作，使每个元素的值表示小于等于该下标的元素的总个数。
  3. 输出排序结果：从后向前遍历输入数组，根据计数数组确定每个元素在输出数组中的位置，将其放入相应位置。

C语言中计数排序的使用方法

基本步骤

  1. 确定输入数组的范围：找出输入数组中的最大值和最小值，以确定计数数组的大小。
  2. 初始化计数数组：创建一个大小为（最大值 - 最小值 + 1）的计数数组，并初始化为0。
  3. 统计计数：遍历输入数组，将每个元素在计数数组中的对应位置的值加1。
  4. 累加计数：对计数数组进行累加操作，使每个元素的值表示小于等于该下标的元素的总个数。
  5. 输出排序结果：从后向前遍历输入数组，根据计数数组确定每个元素在输出数组中的位置，将其放入相应位置。

代码示例

#include <stdio.h>

// 计数排序函数
void countingSort(int arr[], int n) {
    int max = arr[0];
    int 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 range = max - min + 1;
    int *count = (int *)malloc(range * sizeof(int));
    int *output = (int *)malloc(n * sizeof(int));

    // 初始化计数数组
    for (int i = 0; i < range; i++) {
        count[i] = 0;
    }

    // 统计计数
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }

    // 累加计数
    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] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // 将排序结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
}

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

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    countingSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

常见实践

对整数数组排序

上述代码示例展示了如何对整数数组进行计数排序。通过确定数组的范围，统计每个元素的出现次数，并利用累加计数将元素按顺序放入输出数组，最终实现排序。

处理不同范围的整数

如果输入数组中的整数范围较大，可以考虑对数据进行预处理，例如将数据映射到一个较小的范围内，然后再进行计数排序。这样可以减少计数数组的大小，提高算法的效率。

最佳实践

优化空间复杂度

在上述代码中，我们使用了两个额外的数组 count 和 output。为了优化空间复杂度，可以在某些情况下直接在输入数组上进行操作，避免使用额外的 output 数组。具体实现需要根据具体需求进行调整。

稳定性的保证

计数排序是一种稳定的排序算法，这意味着相等的元素在排序前后的相对顺序保持不变。在实现过程中，要确保在将元素放入输出数组时，按照从后向前的顺序遍历输入数组，以保证稳定性。

小结

计数排序是一种高效的非比较排序算法，在处理元素范围相对较小的整数数组时表现出色。通过统计元素出现的次数并利用数组下标的映射关系，计数排序能够在线性时间内完成排序。在实际应用中，要根据数据的特点和需求选择合适的排序算法，并注意优化空间复杂度和保证算法的稳定性。希望本文能帮助读者深入理解并高效使用C语言计数排序。