算法释义:计数排序是一种非基于比较的排序算法,它不依赖于比较操作来确定元素的顺序,而是通过键值索引直接确定元素的输出位置。计数排序适用于一定范围内的整数排序。为什么说是一定范围之内呢?原因如下:计数排序的复杂度为Ο(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;
}