Python、PHP、Java怎么实现计数排序

# Python、PHP、Java怎么实现计数排序

计数排序（Counting Sort）是一种非基于比较的排序算法，其核心思想是通过统计数组中每个元素出现的次数，然后根据统计结果将元素放回原数组的正确位置。本文将详细介绍计数排序的原理，并通过Python、PHP和Java三种语言展示其实现方式。

## 目录
1. [计数排序的原理](#计数排序的原理)
2. [计数排序的步骤](#计数排序的步骤)
3. [Python实现计数排序](#python实现计数排序)
4. [PHP实现计数排序](#php实现计数排序)
5. [Java实现计数排序](#java实现计数排序)
6. [计数排序的复杂度分析](#计数排序的复杂度分析)
7. [计数排序的优缺点](#计数排序的优缺点)
8. [适用场景](#适用场景)
9. [总结](#总结)

---

## 计数排序的原理

计数排序是一种线性时间复杂度的排序算法，适用于整数排序且数据范围不大的场景。其基本原理如下：

1. **统计频率**：遍历数组，统计每个元素出现的次数，存入一个辅助数组（计数数组）。
2. **计算位置**：对计数数组进行累加，得到每个元素在排序后数组中的最终位置。
3. **重构数组**：根据计数数组的信息，将原始数组中的元素放置到正确的位置。

计数排序的时间复杂度为O(n + k)，其中n是数组长度，k是数组中元素的最大值。

---

## 计数排序的步骤

以下是计数排序的具体步骤：

1. **找出最大值**：遍历数组，找到最大值`max_val`。
2. **初始化计数数组**：创建一个长度为`max_val + 1`的数组`count`，初始化为0。
3. **统计频率**：遍历原始数组，统计每个元素出现的次数，存入`count`数组。
4. **累加计数数组**：将`count`数组中的每个元素与前一个元素相加，得到每个元素的最终位置。
5. **构建排序数组**：从后向前遍历原始数组，根据`count`数组的值将元素放入结果数组的对应位置。

---

## Python实现计数排序

以下是Python实现计数排序的代码：

```python
def counting_sort(arr):
    if len(arr) == 0:
        return arr

    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 num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1

    return output

# 测试代码
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("排序后的数组:", sorted_arr)

代码解析

1. max_val是数组中的最大值，用于确定计数数组的长度。
2. count数组用于统计每个元素的出现次数。
3. 累加count数组是为了计算每个元素的最终位置。
4. 从后向前遍历原始数组是为了保证排序的稳定性。

PHP实现计数排序

以下是PHP实现计数排序的代码：

function countingSort($arr) {
    if (empty($arr)) {
        return $arr;
    }

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

    // 统计每个元素的出现次数
    foreach ($arr as $num) {
        $count[$num]++;
    }

    // 累加计数数组
    for ($i = 1; $i <= $max_val; $i++) {
        $count[$i] += $count[$i - 1];
    }

    // 构建输出数组
    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $output[$count[$arr[$i]] - 1] = $arr[$i];
        $count[$arr[$i]]--;
    }

    return $output;
}

// 测试代码
$arr = [4, 2, 2, 8, 3, 3, 1];
$sorted_arr = countingSort($arr);
echo "排序后的数组: " . implode(", ", $sorted_arr);

代码解析

1. array_fill用于初始化计数数组和输出数组。
2. 遍历原始数组时，使用foreach统计频率。
3. 累加count数组的逻辑与Python版本一致。
4. 从后向前遍历原始数组以保证稳定性。

Java实现计数排序

以下是Java实现计数排序的代码：

import java.util.Arrays;

public class CountingSort {
    public static int[] countingSort(int[] arr) {
        if (arr.length == 0) {
            return arr;
        }

        int max_val = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max_val + 1];
        int[] output = new int[arr.length];

        // 统计每个元素的出现次数
        for (int num : arr) {
            count[num]++;
        }

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

        // 构建输出数组
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        return output;
    }

    // 测试代码
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        int[] sorted_arr = countingSort(arr);
        System.out.println("排序后的数组: " + Arrays.toString(sorted_arr));
    }
}

代码解析

1. Arrays.stream(arr).max().getAsInt()用于找到数组中的最大值。
2. count数组和output数组的长度分别由max_val和arr.length决定。
3. 累加count数组的逻辑与其他语言一致。
4. 从后向前遍历原始数组以保证稳定性。

计数排序的复杂度分析

时间复杂度

• 最佳情况：O(n + k)
• 最坏情况：O(n + k)
• 平均情况：O(n + k)

其中，n是数组长度，k是数组中元素的最大值。

空间复杂度

• O(n + k)，需要额外的计数数组和输出数组。

计数排序的优缺点

优点

1. 线性时间复杂度：当k较小时，性能优于基于比较的排序算法（如快速排序、归并排序）。
2. 稳定性：通过从后向前遍历原始数组，可以保证相同元素的相对顺序不变。

缺点

1. 空间消耗大：当k很大时（例如排序[1, 10000]），需要大量的额外空间。
2. 仅适用于整数：无法直接对浮点数或字符串排序。

适用场景

计数排序适用于以下场景： 1. 数据范围较小（k远小于n）。 2. 需要稳定排序。 3. 数据为整数或可以映射为整数。

总结

计数排序是一种高效的线性排序算法，适用于特定场景。本文通过Python、PHP和Java三种语言实现了计数排序，并分析了其时间复杂度和空间复杂度。虽然计数排序在某些场景下表现优异，但其局限性（如仅适用于整数）也需要开发者注意。

”`