排序算法之计数排序

计数排序是一种非基于比较的排序算法，它通过统计数组中每个元素出现的次数，将其按次数从小到大排序。

以下是计数排序的基本步骤：

1. 统计：统计数组中每个元素出现的次数。
2. 计数：将每个元素的出现次数存储在另一个数组中。
3. 累加：从第二个元素开始，每个元素的值是其前一个元素的值加上1。
4. 映射：将原始数组中的每个元素映射到累加数组中的相应位置。
5. 复制：将映射后的元素复制回原始数组。

计数排序的时间复杂度为O(n+k)，其中n是需要排序的元素数量，k是数组中的最大值与最小值的差值。这是因为计数排序需要遍历整个数组来统计元素出现的次数，然后还需要执行一次线性复制操作来将排序后的元素复制回原始数组。

以下是一个Python实现计数排序的例子：

def counting_sort(arr):  
    size = len(arr)  
    output = [0] * size  
    count = [0] * 10000  # 根据最大值和最小值的差值确定数组的大小  
  
    # 统计每个元素出现的次数  
    for i in range(size):  
        index = arr[i]  
        count[index] += 1  
  
    # 累加出现次数  
    for i in range(1, 10000):  
        count[i] += count[i - 1]  
  
    # 将元素放入输出数组中  
    i = size - 1  
    while i >= 0:  
        index = arr[i]  
        output[count[index] - 1] = index  
        count[index] -= 1  
        i -= 1  
  
    # 将输出数组复制回原数组  
    for i in range(size):  
        arr[i] = output[i]