前言：
而今各位老铁们对“histogram算法”大致比较关切，同学们都需要剖析一些“histogram算法”的相关内容。那么小编在网上收集了一些关于“histogram算法””的相关知识，希望兄弟们能喜欢，小伙伴们一起来了解一下吧！计数排序（Counting Sort）
计数排序（Counting Sort）假设 n 个输入元素中的每一个都是介于 0 到 k 之间的整数，此处 k 为某个整数。
计数排序的基本思想就是对每一个输入元素 x，确定出小于 x 的元素个数。有了这一信息，就可以把 x 直接放到它在最终输出数组中的位置上。
例如：有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。
算法描述
算法的步骤如下：
找出待排序的数组中最大和最小的元素；统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；反向填充目标数组，将每个元素 i 放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1；
算法复杂度
最差时间复杂度 O(n + k)平均时间复杂度 O(n + k)最差空间复杂度 O(n + k)
计数排序不是比较排序，排序的速度快于任何比较排序算法。
计数排序的一个重要性质就是它是稳定的：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的次序相同。
之所以说计数排序的稳定性非常重要，还有一个原因是因为计数排序经常用作基数排序算法的一个子过程，其稳定性对于基数排序的正确性来说非常关键。
代码示例
class Program
{
static void Main(string[] args)
{
int[] unsorted =
{
5, 9, 3, 9, 10, 9, 2, 4, 13, 10
};
OptimizedCountingSort(unsorted);
foreach (var key in unsorted)
{
Console.Write("{0} ", key);
}
Console.Read();
}
static int[] CountingSort(int[] unsorted)
{
// find min and max value
int min = unsorted[0], max = unsorted[0];
for (int i = 1; i < unsorted.Length; i++)
{
if (unsorted[i] < min) min = unsorted[i];
else if (unsorted[i] > max) max = unsorted[i];
}
// creates k buckets
int k = max - min + 1;
int[] C = new int[k];
// calculate the histogram of key frequencies
for (int i = 0; i < unsorted.Length; i++)
{
C[unsorted[i] - min]++;
}
// recalculate
C[0]--;
for (int i = 1; i < C.Length; i++)
{
C[i] = C[i] + C[i - 1];
}
// sort the array
int[] B = new int[unsorted.Length];
for (int i = unsorted.Length - 1; i >= 0; i--)
{
// keep stable
B[C[unsorted[i] - min]--] = unsorted[i];
}
return B;
}
static void OptimizedCountingSort(int[] unsorted)
{
// find min and max value
int min = unsorted[0], max = unsorted[0];
for (int i = 1; i < unsorted.Length; i++)
{
if (unsorted[i] < min) min = unsorted[i];
else if (unsorted[i] > max) max = unsorted[i];
}
// creates k buckets
int k = max - min + 1;
int[] C = new int[k];
// calculate the histogram of key frequencies
for (int i = 0; i < unsorted.Length; i++)
{
C[unsorted[i] - min]++;
}
// copy to output array,
// preserving order of inputs with equal keys
int increment = 0;
for (int i = min; i <= max; i++)
{
for (int j = 0; j < C[i - min]; j++)
{
// in place, may not stable if you care
unsorted[increment++] = i;
}
}
}
}
注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。
标签： #histogram算法
