计数排序代码：深入解析与应用

计数排序是一种非常高效的排序算法，特别适用于数据范围有限且数据量较大的情况。今天我们将深入探讨计数排序代码的实现原理、优缺点以及其在实际应用中的表现。

计数排序的基本原理

计数排序的核心思想是利用数组的索引来确定元素的正确位置。具体步骤如下：

确定数据范围：首先需要知道待排序数据的最大值和最小值，以便确定计数数组的大小。
初始化计数数组：创建一个计数数组，其长度为数据范围内的元素个数，初始值都为0。
统计元素出现次数：遍历原始数组，每遇到一个元素，就在计数数组中对应位置加1。
累加计数数组：将计数数组中的每个元素与前一个元素相加，这样每个位置上的值就表示小于等于该索引的元素个数。
构建输出数组：从后向前遍历原始数组，根据计数数组中的值将元素放入输出数组的正确位置。
输出结果：将排序后的数组输出。

计数排序代码示例

下面是一个简单的Python实现：

def counting_sort(arr):
    if not arr:
        return arr

    # 确定数据范围
    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1

    # 初始化计数数组
    count = [0] * range_of_elements

    # 统计元素出现次数
    for num in arr:
        count[num - min_val] += 1

    # 累加计数数组
    for i in range(1, len(count)):
        count[i] += count[i-1]

    # 构建输出数组
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1

    return output

# 测试
arr = [4, 2, 2, 8, 3, 3, 1]
print("排序前:", arr)
print("排序后:", counting_sort(arr))

优点与缺点

优点：

时间复杂度为O(n+k)，其中n是元素个数，k是数据范围。适用于数据范围较小的情况。
稳定性：保持了元素的相对顺序。
适用于大数据量：当数据范围较小时，性能优于其他排序算法。

缺点：

空间复杂度较高：需要额外的空间来存储计数数组。
不适用于数据范围很大的情况：如果数据范围很大，计数数组会占用大量内存。
不适用于负数：原始算法不处理负数。

应用场景

计数排序在以下场景中表现出色：

选举投票：统计每个候选人的得票数。
成绩排序：学生成绩的排序，通常成绩范围有限。
IP地址排序：IP地址的排序，IP地址的范围是有限的。
图像处理：像素值的排序，通常像素值在0到255之间。
数据库查询：在某些数据库查询优化中，用于快速排序和统计。

总结

计数排序是一种简单而高效的排序算法，特别是在数据范围有限且数据量较大的情况下。通过理解其原理和实现，我们可以更好地应用这种算法来解决实际问题。希望本文对你理解计数排序代码有所帮助，并能在实际应用中灵活运用。