计数排序：内存优化与速度提升的完美结合

# 1. 计数排序算法概述

计数排序（Counting Sort）是一种非比较型的排序算法，适用于一定范围内的整数排序。在计数排序中，我们利用数组下标来确定元素的正确位置。它将输入数据的每个元素值作为计数数组的索引，计数数组的值表示元素出现的次数。

计数排序的基本思想是为每一个输入的元素 x，确定小于 x 的元素个数，然后直接把 x 放在目标数组的第 k 个位置，其中 k 是小于 x 的元素个数。由于是基于计数来确定元素位置的，计数排序能够突破比较排序算法的下限 O(n log n)。

计数排序有着稳定性和非适应性两个显著特点。稳定性保证了排序后相等元素的相对顺序不变，而非适应性意味着它并不关心元素间的大小关系，只关心元素出现的次数。这一算法尤其适合用在那些待排序的关键字范围不大的应用场景中。

# 2. 计数排序理论基础与优化原理

## 2.1 计数排序算法介绍

### 2.1.1 算法的基本概念

计数排序（Counting Sort）是一种非比较型排序算法，适用于一定范围内的整数排序。在计数排序中，我们使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置上。这个算法的名字由此而来：我们根据数组中每个值出现的次数来进行计数排序。

计数排序的核心在于将输入数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序在某些情况下比比较类排序算法更加高效。然而，它也有一些限制：一是当输入的数值范围大小远远大于实际元素个数时，计数排序需要额外的大量空间；二是计数排序只适用于非负整数的排序。

### 2.1.2 算法的特点及适用场景

计数排序的特点是能够对一定范围内的整数进行排序，并且排序速度极快，其时间复杂度为O(n+k)，其中n是待排序数组的长度，k是输入数据的范围大小。由于计数排序避免了比较操作，其性能通常要优于基于比较的排序算法，比如快速排序、归并排序等。

计数排序的适用场景主要包括以下几点：

- 输入数据范围有限，且这个范围远小于数据的数量。
- 需要排序的数组中没有重复的值。
- 对于稳定性要求不高的场合，因为计数排序是一种非稳定排序。

计数排序并不适用于数据分布不均匀的情况，且当数据范围很大时，它的空间复杂度会变得非常高。因此，在实际应用中需要权衡计数排序的优缺点，选择最合适的排序方法。

## 2.2 计数排序的核心机制

### 2.2.1 基本计数排序流程

计数排序的基本步骤可以分为以下几个阶段：

1. 找出数组中的最大值`max`和最小值`min`，确定数组中数据的范围。
2. 初始化一个大小为`max-min+1`的数组C，所有元素设为0。这个数组用于记录每个数据出现的次数。
3. 遍历原数组A，将A中的每个元素减去最小值`min`，并将结果作为索引存入数组C中，相应的计数加1。
4. 对数组C进行累加操作，使得C[i]的值表示了小于等于i的所有元素的个数。
5. 创建一个输出数组B，并从后向前遍历原数组A，根据C数组中的计数将A中的元素放入B中正确的位置上，每次放置后C中对应计数减1。
6. 最后，将排序好的数组B复制回原数组A。

### 2.2.2 算法的时间复杂度分析

计数排序的时间复杂度主要取决于对输入数据的扫描次数和对计数数组C的操作次数。从上述步骤可以看出：

1. 找出最大值和最小值需要O(n)的时间。
2. 初始化计数数组C和遍历原数组A进行计数也分别需要O(n)的时间。
3. 累加数组C和从后向前填充输出数组B需要O(k)的时间，其中k是原数组A中数据的范围。
4. 将排序好的数组B复制回原数组A需要O(n)的时间。

因为k是常数，所以整体的时间复杂度可以简化为O(n)。这里的关键点是，与元素数量n相比，k必须是一个很小的常数，否则空间复杂度会变得不可接受。因此，计数排序在理论上是一种线性时间复杂度的算法，适用于数据范围较小、元素数量较多的场合。

## 2.3 计数排序的内存优化策略

### 2.3.1 算法的空间复杂度优化

计数排序的空间复杂度为O(k)，其中k是输入数据的范围。在输入数据范围非常大时，这可能导致大量的内存消耗。为了优化内存使用，可以采取以下策略：

- 使用动态内存分配，仅在必要时才分配足够的内存空间，而不是一开始分配整个可能的最大范围。
- 如果输入数据是随机分布的，可以考虑使用更小的数据结构，比如哈希表，来替代大范围的数组。这可以在保证计数准确性的同时，减少内存消耗。

### 2.3.2 动态内存分配的应用

动态内存分配允许我们在程序运行时根据实际需要分配内存，这样就可以根据实际数据的范围动态调整计数数组的大小。以下是一个使用动态内存分配优化计数排序空间复杂度的示例代码：

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

void countingSort(int *arr, int n) {
    int max = arr[0], min = arr[0];
    for (int i = 0; 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));
    if (count == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    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];
    }

    int *output = (int *)malloc(n * sizeof(int));
    if (output == NULL) {
        printf("Memory allocation failed!\n");
        exit(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);
}

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