Python的计数排序

计数排序是一种非比较排序算法，其时间复杂度为O(n+k)，其中n为待排序数组的大小，k为待排序数组中最大元素的大小。计数排序的核心思想是统计数组中每个元素出现的次数，然后根据这个统计信息将待排序数组重组成有序数组。

Python中，可以通过如下代码实现计数排序：

“`python
def counting_sort(arr):
# 找到数组中的最大值
max_val = max(arr)
# 统计数组中每个元素出现的次数
count_arr = [0] * (max_val + 1)
for i in arr:
count_arr[i] += 1
# 根据统计信息重新组织有序数组
sorted_arr = []
for i in range(max_val + 1):
sorted_arr.extend([i]*count_arr[i])
return sorted_arr
“`

在这段代码中，首先找到了数组中的最大值，然后创建了一个大小为max_val+1的数组count_arr来统计每个元素出现的次数。接下来，遍历待排序数组arr中的每个元素i，在count_arr中对应位置的次数加1。最后，根据count_arr的统计信息重新组织有序数组sorted_arr，具体实现方法是：从0到max_val遍历count_arr中的每个元素i，将i按照count_arr[i]的次数依次插入到sorted_arr的末尾。最终，返回排序好的有序数组sorted_arr。