计数排序代码（计数排序算法）

# 计数排序代码## 简介计数排序是一种非比较型整数排序算法，其复杂度为O(n+k)，其中n是数组的长度，k是数组中元素的最大值。计数排序的核心思想是利用输入数据中的范围将数据映射到一个已知大小的范围内。它适用于处理数值范围有限的情况，并且当输入数据分布均匀时表现最佳。## 计数排序原理计数排序的基本步骤如下：1.

统计频率

：遍历数组，统计每个值出现的次数。 2.

构建输出数组

：基于频率信息，构建输出数组。 3.

填充结果

：根据频率信息填充输出数组，从而得到排序后的结果。## 计数排序代码实现### Python 实现以下是使用Python实现的计数排序代码示例：```python def counting_sort(arr):# 找出最大值和最小值max_val = max(arr)min_val = min(arr)# 初始化计数数组count_range = max_val - min_val + 1count = [0]

count_range# 统计每个值出现的次数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 = counting_sort(arr) print("Sorted array:", sorted_arr) ```### Java 实现以下是使用Java实现的计数排序代码示例：```java public class CountingSort {public static void countingSort(int[] arr) {// 找出最大值和最小值int maxVal = Integer.MIN_VALUE;int minVal = Integer.MAX_VALUE;for (int num : arr) {if (num > maxVal) maxVal = num;if (num < minVal) minVal = num;}// 初始化计数数组int range = maxVal - minVal + 1;int[] count = new int[range];// 统计每个值出现的次数for (int num : arr) {count[num - minVal]++;}// 构建输出数组int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {arr[index++] = i + minVal;count[i]--;}}}public static void main(String[] args) {int[] arr = {4, 2, 2, 8, 3, 3, 1};countingSort(arr);System.out.print("Sorted array: ");for (int num : arr) {System.out.print(num + " ");}} } ```## 计数排序的优缺点### 优点 -

时间复杂度低

：在输入数据范围较小时，计数排序的时间复杂度可以达到O(n)。 -

稳定性好

：计数排序是一种稳定排序算法，相同元素的相对顺序不会改变。### 缺点 -

空间复杂度高

：需要额外的空间来存储计数数组，空间复杂度为O(k)，其中k是数组中元素的最大值。 -

适用范围有限

：仅适用于整数排序，且当元素范围过大时，会导致空间浪费。## 总结计数排序是一种高效的排序算法，特别适用于元素范围较小的情况。通过统计每个元素的出现次数，然后根据这些计数构建最终的排序结果。虽然它的应用范围有一定的限制，但在合适的场景下，它可以提供非常高的效率和稳定性。

计数排序代码

简介计数排序是一种非比较型整数排序算法，其复杂度为O(n+k)，其中n是数组的长度，k是数组中元素的最大值。计数排序的核心思想是利用输入数据中的范围将数据映射到一个已知大小的范围内。它适用于处理数值范围有限的情况，并且当输入数据分布均匀时表现最佳。

计数排序原理计数排序的基本步骤如下：1. **统计频率**：遍历数组，统计每个值出现的次数。 2. **构建输出数组**：基于频率信息，构建输出数组。 3. **填充结果**：根据频率信息填充输出数组，从而得到排序后的结果。

计数排序代码实现

Python 实现以下是使用Python实现的计数排序代码示例：```python def counting_sort(arr):

找出最大值和最小值max_val = max(arr)min_val = min(arr)

初始化计数数组count_range = max_val - min_val + 1count = [0] * count_range

统计每个值出现的次数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 = counting_sort(arr) print("Sorted array:", sorted_arr) ```

Java 实现以下是使用Java实现的计数排序代码示例：```java public class CountingSort {public static void countingSort(int[] arr) {// 找出最大值和最小值int maxVal = Integer.MIN_VALUE;int minVal = Integer.MAX_VALUE;for (int num : arr) {if (num > maxVal) maxVal = num;if (num < minVal) minVal = num;}// 初始化计数数组int range = maxVal - minVal + 1;int[] count = new int[range];// 统计每个值出现的次数for (int num : arr) {count[num - minVal]++;}// 构建输出数组int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {arr[index++] = i + minVal;count[i]--;}}}public static void main(String[] args) {int[] arr = {4, 2, 2, 8, 3, 3, 1};countingSort(arr);System.out.print("Sorted array: ");for (int num : arr) {System.out.print(num + " ");}} } ```

计数排序的优缺点

优点 - **时间复杂度低**：在输入数据范围较小时，计数排序的时间复杂度可以达到O(n)。 - **稳定性好**：计数排序是一种稳定排序算法，相同元素的相对顺序不会改变。

缺点 - **空间复杂度高**：需要额外的空间来存储计数数组，空间复杂度为O(k)，其中k是数组中元素的最大值。 - **适用范围有限**：仅适用于整数排序，且当元素范围过大时，会导致空间浪费。

总结计数排序是一种高效的排序算法，特别适用于元素范围较小的情况。通过统计每个元素的出现次数，然后根据这些计数构建最终的排序结果。虽然它的应用范围有一定的限制，但在合适的场景下，它可以提供非常高的效率和稳定性。