C#算法之计数排序

        算法释义：计数排序是一种非基于比较的排序算法，它不依赖于比较操作来确定元素的顺序，而是通过键值索引直接确定元素的输出位置。计数排序适用于一定范围内的整数排序。为什么说是一定范围之内呢？原因如下：计数排序的复杂度为Ο(n+k)（其中k是整数的范围），这是一种牺牲空间换取时间的做法，而且当O(k)＞O(n*log(n))的时候其效率反而不如基于比较的排序。

        这个算法不太常用，基本的示例代码如下：

    public static void Main(){int[] array = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };int[] sortedArray = Countsort(array);}public static int[] Countsort(int[] arr){int min = arr.Min();int max = arr.Max();int range = max - min + 1;int[] count = new int[range];int[] sorted = new int[arr.Length];foreach (int i in arr){count[i - min]++;}for (int i = 1; i < count.Length; i++){count[i] += count[i - 1];}for (int i = arr.Length - 1; i >= 0; i--){sorted[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--;}return sorted;}