# 计数排序（Counting Sort）

URL: https://caijiao.org/sort/8-counting-sort
Source: docs/sort/8-counting-sort.md
Description: 计数排序是一种非比较类排序，适用于整数且范围有限的场景。本文详细介绍算法原理，并提供 JavaScript、Python、C++、Java、PHP、Go 多语言实现。

计数排序是一种**非比较类排序算法**，适用于**整数且范围不大**的数组。它通过统计每个数出现的次数，并根据这些统计信息计算出每个元素的最终位置，从而实现排序。

该算法的时间复杂度为 **O(n + k)**，其中 *n* 是元素数量，*k* 是值域范围大小。

## 📌 算法原理解释

计数排序流程如下：

1. 找出待排序数组中的最大值 max；
2. 创建一个长度为 max + 1 的计数数组 count，统计每个元素出现的次数；
3. 将 count 数组变为前缀和数组，表示元素在排序后应出现的位置；
4. 倒序遍历原数组，将每个元素放到结果数组中的正确位置（可保持稳定性）；
5. 返回结果数组。

⚠️ 注意事项：

- 不适用于小数、负数（需额外处理）；
- 适合范围有限的非负整数排序，如考试成绩、年龄等。

## 💻 多语言代码实现


// JavaScript 计数排序
function countingSort(arr) {
  if (arr.length === 0) return [];

  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  const output = new Array(arr.length);

  for (let num of arr) count[num]++;
  for (let i = 1; i <= max; i++) count[i] += count[i - 1];
  for (let i = arr.length - 1; i >= 0; i--) {
    const num = arr[i];
    output[--count[num]] = num;
  }

  return output;
}
````

```python
# Python 计数排序
def counting_sort(arr):
    if not arr:
        return []
    max_val = max(arr)
    count = [0] * (max_val + 1)
    output = [0] * len(arr)

    for num in arr:
        count[num] += 1
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1

    return output
```

```cpp
// C++ 计数排序
#include <vector>
using namespace std;

vector<int> countingSort(const vector<int>& arr) {
    if (arr.empty()) return {};
    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> count(maxVal + 1, 0), output(arr.size());

    for (int num : arr) count[num]++;
    for (int i = 1; i <= maxVal; i++) count[i] += count[i - 1];
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[--count[arr[i]]] = arr[i];
    }

    return output;
}
```

```java
// Java 计数排序
public class CountingSort {
    public static int[] countingSort(int[] arr) {
        if (arr.length == 0) return arr;
        int max = arr[0];
        for (int num : arr) max = Math.max(max, num);

        int[] count = new int[max + 1];
        int[] output = new int[arr.length];

        for (int num : arr) count[num]++;
        for (int i = 1; i < count.length; i++) count[i] += count[i - 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            output[--count[arr[i]]] = arr[i];
        }

        return output;
    }
}
```

```php
<?php
// PHP 计数排序
function countingSort(array $arr): array {
    if (empty($arr)) return [];

    $max = max($arr);
    $count = array_fill(0, $max + 1, 0);
    $output = array_fill(0, count($arr), 0);

    foreach ($arr as $num) $count[$num]++;
    for ($i = 1; $i <= $max; $i++) $count[$i] += $count[$i - 1];
    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $output[--$count[$arr[$i]]] = $arr[$i];
    }

    return $output;
}
?>
```

```go
// Go 计数排序
package main

func countingSort(arr []int) []int {
    if len(arr) == 0 {
        return []int{}
    }

    max := arr[0]
    for _, v := range arr {
        if v > max {
            max = v
        }
    }

    count := make([]int, max+1)
    output := make([]int, len(arr))

    for _, v := range arr {
        count[v]++
    }
    for i := 1; i <= max; i++ {
        count[i] += count[i-1]
    }
    for i := len(arr) - 1; i >= 0; i-- {
        output[count[arr[i]]-1] = arr[i]
        count[arr[i]]--
    }

    return output
}
```


## ✅ 算法特点与总结

| 属性     | 描述           |
| ------ | ------------ |
| 时间复杂度  | O(n + k)     |
| 空间复杂度  | O(k)（用于计数数组） |
| 稳定性    | ✅ 稳定         |
| 是否原地排序 | ❌ 否（需额外数组）   |
| 适用条件   | 元素为非负整数且范围不大 |

> 📌 提示：计数排序适用于整数、离散且范围较小的场景，如年龄、分数、ID 等。