【千锤百炼Python—10】：十大排序算法之计数排序

**

**

计数排序是排序算法系列的第九个要介绍的算法！

计数排序既属于非比较类排序也属于外部排序。

计数排序（Counting Sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

• 步骤一：找出待排序的数组中最大和最小的元素；
• 步骤二：统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 步骤三：对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 步骤四：反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

参考：

https://blog.csdn.net/weixin_43790276/article/details/107398262

def countingsort(array):
    if len(array) < 2:
        return array
    max_num = max(array)
    count = [0] * (max_num + 1)
    for num in array:
        count[num] += 1
    new_array = list()
    for i in range(len(count)):
        for j in range(count[i]):
            new_array.append(i)
    return new_array


if __name__ == '__main__':
    array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(countingsort(array))

输出结果为：

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]