计数排序（Counting Sort）是一种简单、高效的排序算法，它不基于比较，而是利用数组下标的计数来实现排序。本文将详细介绍计数排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。
计数排序的基本思想
计数排序的核心思想是统计数组中每个元素的出现次数，然后根据元素的大小依次放置到有序的结果数组中。具体步骤如下：
- 统计频次： 遍历待排序数组，统计每个元素出现的频次，以数组的值为索引。
- 计算累积频次： 计算每个元素的累积频次，确定元素在排序数组中的位置。
- 构建有序数组： 根据元素的累积频次，将元素放入有序数组中，同时更新累积频次。
计数排序的关键在于构建辅助数组，辅助数组用于存储每个元素的出现次数，以及计算每个元素在排序后的数组中的位置。
计数排序的示例
让我们通过一个示例来理解计数排序的工作原理。假设我们有一个整数数组 [3, 1, 4, 1, 5, 9, 2, 6, 5]，我们希望按升序排序它。
- 统计频次： 统计每个元素的出现次数。
- 待排序数组： [3, 1, 4, 1, 5, 9, 2, 6, 5]
- 频次数组： [0, 1, 1, 1, 2, 1, 1, 0, 1]
- 计算累积频次： 计算每个元素的累积频次。
- 累积频次数组： [0, 1, 2, 3, 5, 6, 7, 7, 8]
- 构建有序数组： 根据元素的累积频次，将元素放入有序数组中。
- 排序后的数组： [1, 1, 2, 3, 4, 5, 5, 6, 9]
计数排序的时间复杂度
计数排序的时间复杂度为O(n + k)，其中n是数组的长度，k是数组中元素的取值范围。计数排序的时间复杂度非常稳定，性能优异，尤其适合对整数进行排序。但需要注意，计数排序仅适用于非负整数或确定范围的整数排序。
计数排序是一种稳定的排序算法，通过对元素的频次统计和累积频次计算，实现了线性时间的排序。
示例代码
以下是计数排序的示例代码，分别使用Python、Go、Java和C语言编写。
Python 计数排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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 计数排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| 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 计数排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| 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 语言 计数排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #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;
}
|
以上示例代码展示了不同编程语言中的计数排序算法实现。这些示例帮助你理解计数排序的工作原理，并提供了可供参考和使用的代码示例。计数排序是一种稳定且高效的排序算法，尤其适用于整数排序。