计数排序
计数排序(Counting Sort)是一种非基于比较的排序方法，它要求所有的待排元素都必须是≥0的整数。它的排序步骤是首先根据数组中最大的元素值加1作为长度来定义一个计数数组C。然后统计待排数组中每个值为i的元素出现的次数，存入C的第i项中。再对所有的计数累加（从C中的第一项开始，每一项和前一项相加）。最后再反向填充辅助数组：将每个元素i放在辅助数组的第C(i)项，每放一个元素就将C(i)减去1。这样完成之后排序就已完毕，有序序列已存储在辅助数组中。如果结果想用原数组输出，则将它们从辅助数组考回到原数组即可。
计数排序的C/C++代码实现：
- void counting_sort(int a[], int length)
- {
- int i;
- int c[MAX_VALUE] = {0};
- int temp[ARRAY_SIZE] = {0};
- for (i = 0; i < length; ++i) c[a[i]]++;
- for (i = 1; i < MAX_VALUE; ++i) c[i] += c[i-1];
- for (i = length - 1; i >= 0; --i) {
- temp[c[a[i]]-1] = a[i];
- c[a[i]]--;
- }
- for (i = 0; i < length; ++i) a[i] = temp[i];
- }
计数排序是稳定的排序方法，这是它很重要的特性之一，也是为什么要在这里介绍它的原因：因为后面的LSD基数排序会因为它的这个特性而用到它。
计数排序的时间复杂度是O(n)，比之前所讲的所有比较排序算法都快。但由于它的限制条件苛刻，比如所排元素必须是≥0的正整数，并且数据范围和数据元素个数不宜过大等。虽然经过改进可以对数据项较大、包含范围较小的文件进行排序，但应用范围仍然不是很大。
文章若无注明则属原创，转载请以链接形式注明出处。
本文地址：http://www.juliuschen.com/archives/14.html
