计数排序 - 算法实现 - 计数排序的代码实现

计数排序 - 算法实现 - 计数排序的代码实现

在计算机科学的浩瀚算法海洋中，排序算法是基础且至关重要的一部分。常见的排序算法有冒泡排序、快速排序、归并排序等，而计数排序则是一种非比较型的整数排序算法，在特定场景下能展现出卓越的性能。本文将深入探讨计数排序的原理、实现过程以及代码示例。

计数排序的原理

计数排序的核心思想是通过统计待排序数组中每个元素出现的次数，然后根据这些统计信息将元素有序地放回原数组或新数组中。它的工作原理基于一个简单的事实：如果我们知道一个元素在整个序列中前面有多少个元素比它小，那么就可以直接确定该元素在排序后的位置。

具体步骤

1. 找出待排序数组中的最大值和最小值：确定统计数组的范围。
2. 统计每个元素出现的次数：创建一个统计数组，其长度为最大值与最小值的差值加 1，数组的每个索引对应一个可能的元素值，数组的值表示该元素出现的次数。
3. 计算累计次数：对统计数组进行累加操作，使得每个位置的值表示小于等于该位置索引对应元素的元素总数。
4. 将元素放入排序后的数组：根据累计次数数组，将待排序数组中的元素依次放入新的排序数组中。

计数排序的代码实现（Python）

def counting_sort(arr):
    # 找出数组中的最大值和最小值
    max_val = max(arr)
    min_val = min(arr)
    # 计算统计数组的长度
    range_of_elements = max_val - min_val + 1
    # 初始化统计数组
    count = [0] * range_of_elements
    # 初始化排序后的数组
    output = [0] * len(arr)
    # 统计每个元素出现的次数
    for num in arr:
        count[num - min_val] += 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] - min_val] - 1] = arr[i]
        count[arr[i] - min_val] -= 1
    return output
# 测试代码
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("排序前的数组:", arr)
print("排序后的数组:", sorted_arr)

代码解释

1. 找出最大值和最小值：使用 Python 的内置函数 max() 和 min() 找出数组中的最大值和最小值，从而确定统计数组的范围。
2. 统计元素出现次数：遍历待排序数组，将每个元素出现的次数记录在统计数组 count 中。
3. 计算累计次数：对统计数组进行累加操作，得到每个元素在排序后数组中的最终位置。
4. 将元素放入排序后的数组：从后往前遍历待排序数组，根据累计次数数组将元素放入排序后的数组 output 中，并更新累计次数数组。

复杂度分析

计数排序的适用场景

计数排序适用于以下场景：

• 数据范围较小：当待排序数组中的元素取值范围较小时，计数排序的空间复杂度相对较低，性能较好。
• 整数排序：计数排序是一种整数排序算法，要求待排序数组中的元素必须是整数。

总结

计数排序是一种简单而高效的排序算法，它通过统计元素出现的次数来实现排序，避免了比较排序算法的时间复杂度下限。虽然计数排序在特定场景下表现出色，但也有一定的局限性，如需要额外的空间来存储统计数组，且只适用于整数排序。在实际应用中，我们应根据具体问题选择合适的排序算法。

通过本文的介绍，相信你已经对计数排序的原理和代码实现有了更深入的理解。不妨亲自尝试编写代码，体验计数排序的魅力吧！