使用C语言实现计数排序

计数排序（Counting Sort）是一种线性时间复杂度的非比较排序算法。相较于常见的比较排序算法如快速排序和归并排序，计数排序在数据范围较小的情况下，能够以更快的速度完成排序任务。它的基本思想是通过统计每个元素出现的次数，从而计算出每个元素在排序后数组中的正确位置。接下来，我们将详细探讨如何使用C语言实现计数排序，并分析其时间和空间复杂度。

算法思想

计数排序适用于一定范围内的整数排序。它通过一个额外的数组来计数数组元素出现的次数，然后对计数数组进行累加处理，以便直接确定每个元素在排序后数组中的位置。具体步骤如下：

找出待排序数组中的最大值，以确定计数数组的大小。
分配计数数组并初始化为0。
遍历待排序数组，记录每个元素出现的次数。
对计数数组进行累加，处理后计数数组中的每个值表示小于等于当前索引的元素个数。
从后向前遍历原数组，根据计数数组中的信息，将每个元素放到其排序后的位置，并更新计数数组，以便处理相同元素的情况。
输出结果存储在新的数组中。

代码实现

下面是用C语言实现计数排序的代码示例：

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

// 计数排序函数
void countingSort(int arr[], int n) {
    if (n <= 0) return;

    // 找到数组中的最大值
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // 创建计数数组并初始化为0
    int *count = (int *)calloc(max + 1, sizeof(int));

    // 统计每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 计算计数数组的累加和
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }

    // 创建输出数组
    int *output = (int *)malloc(n * sizeof(int));

    // 从后向前遍历原数组，将每个元素放到其正确的位置
    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 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("原始数组: ");
    printArray(arr, n);

    countingSort(arr, n);

    printf("排序后数组: ");
    printArray(arr, n);

    return 0;
}

复杂度分析

时间复杂度：计数排序的时间复杂度为O(n + k)，其中n是数组的长度，k是数组中元素的范围。因为计数排序不涉及比较操作，所以在数据范围k相对小时具有极高的效率。
空间复杂度：需要额外的O(k)空间来保存计数数组。如果k远大于n，计数排序的空间效率会变低，不如比较排序算法。

应用与局限

计数排序适用于范围较小的正整数排序，当数组的最大值k远大于数组长度n时，会导致空间浪费和效率低下。在分布式系统和大数据处理中，可以考虑将计数排序与其他算法结合使用，以获得更好的性能。

通过对计数排序原理和实现的学习，我们可以更好地理解如何在具体问题中选择合适的排序算法，以优化程序的性能。希望本篇博客能够帮助你掌握计数排序及其C语言实现方法。

算法思想

代码实现

复杂度分析

应用与局限

最新文章