计数排序

**计数排序**

计数排序是一种稳定的、线性时间复杂度的整数排序算法。它适用于输入数据范围是有限且确定的场景。

### 算法原理计数排序的基本思想是将要排序的元素作为索引，统计每个元素出现的次数，然后根据这些计数来确定元素的顺序。

假设我们有一个长度为 `n` 的整数数组 `arr`，其中所有元素都在范围 `[0, k]` 内。我们可以创建一个大小为 `k+1` 的计数数组 `count`，用于存储每个元素出现的次数。

### 算法步骤1. **初始化计数数组**：将 `count` 数组所有元素都设置为0。
2. **统计元素出现次数**：遍历 `arr` 数组，每遇到一个元素，就在 `count` 中加一。
3. **根据计数确定顺序**：从 `count` 数组中读取每个元素的值，按照这个值来决定 `arr` 中该元素的位置。

###代码示例

def count_sort(arr):
 # 初始化计数数组 max_val = max(arr)
 min_val = min(arr)
 count = [0] * (max_val - min_val +1)

 # 统计元素出现次数 for num in arr:
 count[num - min_val] +=1 # 根据计数确定顺序 sorted_arr = []
 for i, cnt in enumerate(count):
 sorted_arr.extend([i + min_val] * cnt)

 return sorted_arr# 测试用例arr = [4,2,2,8,3,3,1]
sorted_arr = count_sort(arr)
print(sorted_arr) # 输出: [1,2,2,3,3,4,8]