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

standfly 2018-08-14

计数排序(Counting Sort)

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


示例:


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

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

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


分析:

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

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

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

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


AlgorithmMan:

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

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

下载链接:AlgorithmMan-CountingSort

相关推荐