C井算法设计排序篇之计数排序（附带动画演示程序）

计数排序（Counting Sort）

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的时间复杂度为线性的O(n+k)（其中k是整数的范围，即max - min + 1），快于任何比较排序算法，这是一种典型的空间换时间的算法。

示例：

1. 
   
2. public class Program {
4. public static void Main(string[] args) {
5. int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
7. CountingSort(array);
8. ShowSord(array);
10. Console.ReadKey();
11. }
13. private static void ShowSord(int[] array) {
14. foreach (var num in array) {
15. Console.Write($"{num} ");
16. }
17. Console.WriteLine();
18. }
20. public static void CountingSort(int[] array) {
21. if (array.Length == 0) return;
22. int min = array[0];
23. int max = min;
24. foreach (int number in array) {
25. if (number > max) {
26. max = number;
27. }
28. else if (number < min) {
29. min = number;
30. }
31. }
32. int[] counting = new int[max - min + 1];
33. for (int i = 0; i < array.Length; i++) {
34. counting[array[i] - min] += 1;
35. }
36. int index = -1;
37. for (int i = 0; i < counting.Length; i++) {
38. for (int j = 0; j < counting[i]; j++) {
39. index++;
40. array[index] = i + min;
41. }
42. }
43. }
45. }

以上是计数排序算法的一种实现，以下是这个案例的输出结果：

8 11 21 28 32 43 48 56 69 72 80 94

分析：

计数排序算法的时间复杂度为：

，即其时间复杂度是线性的，所以结果同

。

AlgorithmMan：

AlgorithmMan by Iori，AlgorithmMan是使用C#开发的一套用于算法演示的工具。

下载链接：AlgorithmMan-CountingSort