计数排序（Counting Sort）是一种简单、高效的排序算法，它不基于比较，而是利用数组下标的计数来实现排序。本文将详细介绍计数排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
计数排序的基本思想
计数排序的核心思想是统计数组中每个元素的出现次数，然后根据元素的大小依次放置到有序的结果数组中。具体步骤如下：
1.统计频次： 遍历待排序数组，统计每个元素出现的频次，以数组的值为索引。
2.计算累积频次： 计算每个元素的累积频次，确定元素在排序数组中的位置。
3.构建有序数组： 根据元素的累积频次，将元素放入有序数组中，同时更新累积频次。
计数排序的关键在于构建辅助数组，辅助数组用于存储每个元素的出现次数，以及计算每个元素在排序后的数组中的位置。
计数排序的示例
让我们通过一个示例来理解计数排序的工作原理。假设我们有一个整数数组 [3, 1, 4, 1, 5, 9, 2, 6, 5]，我们希望按升序排序它。
1.统计频次： 统计每个元素的出现次数。
待排序数组： [3, 1, 4, 1, 5, 9, 2, 6, 5] 频次数组： [0, 1, 1, 1, 2, 1, 1, 0, 1]
1.计算累积频次： 计算每个元素的累积频次。
累积频次数组： [0, 1, 2, 3, 5, 6, 7, 7, 8]
1.构建有序数组： 根据元素的累积频次，将元素放入有序数组中。
排序后的数组： [1, 1, 2, 3, 4, 5, 5, 6, 9]
计数排序的时间复杂度
计数排序的时间复杂度为O(n + k)，其中n是数组的长度，k是数组中元素的取值范围。计数排序的时间复杂度非常稳定，性能优异，尤其适合对整数进行排序。但需要注意，计数排序仅适用于非负整数或确定范围的整数排序。
计数排序是一种稳定的排序算法，通过对元素的频次统计和累积频次计算，实现了线性时间的排序。
示例代码
以下是计数排序的示例代码，分别使用Python、Go、Java和C语言编写。
Python 计数排序
def counting_sort(arr): max_val = max(arr) counts = [0] * (max_val + 1) # 统计每个元素的频次 for num in arr: counts[num] += 1 # 计算每个元素的累积频次 for i in range(1, max_val + 1): counts[i] += counts[i - 1] # 构建有序数组 sorted_arr = [0] * len(arr) for i in range(len(arr)): sorted_arr[counts[arr[i]] - 1] = arr[i] counts[arr[i]] -= 1 return sorted_arr arr = [3, 1, 4, 1, 5, 9, 2, 6, 5] sorted_arr = counting_sort(arr) print("排序后的数组:", sorted_arr)
Go 计数排序
package main import "fmt" func countingSort(arr []int) []int { maxVal := arr[0] for _, num := range arr { if num > maxVal { maxVal = num } } counts := make([]int, maxVal+1) // 统计每个元素的频次 for _, num := range arr { counts[num]++ } // 计算每个元素的累积频次 for i := 1; i <= maxVal; i++ { counts[i] += counts[i-1] } // 构建有序数组 sortedArr := make([]int, len(arr)) for i := len(arr) - 1; i >= 0; i-- { sortedArr[counts[arr[i]]-1] = arr[i] counts[arr[i]]-- } return sortedArr } func main() { arr := []int{3, 1, 4, 1, 5, 9, 2, 6, 5} sortedArr := countingSort(arr) fmt.Println("排序后的数组:", sortedArr) }
Java 计数排序
import java.util.Arrays; public class CountingSort { public static int[] countingSort(int[] arr) { int maxVal = Arrays.stream(arr).max().getAsInt(); int[] counts = new int[maxVal + 1]; // 统计每个元素的频次 for (int num : arr) { counts[num]++; } // 计算每个元素的累积频次 for (int i = 1; i <= maxVal; i++) { counts[i] += counts[i - 1]; } // 构建有序数组 int[] sortedArr = new int[arr.length]; for (int i = arr.length - 1; i >= 0; i--) { sortedArr[counts[arr[i]] - 1] = arr[i]; counts[arr[i]]--; } return sortedArr; } public static void main(String[] args) { int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5}; int[] sortedArr = countingSort(arr); System.out.print("排序后的数组: "); System.out.println(Arrays.toString(sortedArr)); } }
C 语言 计数排序
#include <stdio.h> #include <stdlib.h> void countingSort(int arr[], int n) { int maxVal = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > maxVal) { maxVal = arr[i]; } } int *counts = (int *)malloc((maxVal + 1) * sizeof(int)); int *sortedArr = (int *)malloc(n * sizeof(int)); // 初始化计数数组 for (int i = 0; i <= maxVal; i++) { counts[i] = 0; } // 统计每个元素的频次 for (int i = 0; i < n; i++) { counts[arr[i]]++; } // 计算每个元素的累积频次 for (int i = 1; i <= maxVal; i++) { counts[i] += counts[i - 1]; } // 构建有序数组 for (int i = n - 1; i >= 0; i--) { sortedArr[counts[arr[i]] - 1] = arr[i]; counts[arr[i]]--; } // 将有序数组拷贝回原数组 for (int i = 0; i < n; i++) { arr[i] = sortedArr[i]; } free(counts); free(sortedArr); } int main() { int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5}; int n = sizeof(arr) / sizeof(arr[0]); countingSort(arr, n); printf("排序后的数组: "); for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } return 0; }
以上示例代码展示了不同编程语言中的计数排序算法实现。这些示例帮助你理解计数排序的工作原理，并提供了可供参考和使用的代码示例。计数排序是一种稳定且高效的排序算法，尤其适用于整数排序。
