排序算法之计数排序（排序算法12计数排序）
排序算法之计数排序（排序算法12计数排序）// 数据结构 --------- 数组// 分类 ------------ 内部非比较排序附代码：#include<iostream>using namespace std;
各类排序方法在时间、空间复杂度及稳定性（通俗地讲，就是两个相等的数会不会交换位置）方面各有优势：
计数排序（Counting Sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n2 n3 ..，就得不到线性时间的上界。
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n k)，空间复杂度也是O(n k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
1 算法描述- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
附代码：
#include<iostream>
using namespace std;
// 分类 ------------ 内部非比较排序
// 数据结构 --------- 数组
// 最差时间复杂度 ---- O(n k)
// 最优时间复杂度 ---- O(n k)
// 平均时间复杂度 ---- O(n k)
// 所需辅助空间 ------ O(n k)
// 稳定性 ----------- 稳定
const int k = 100; // 基数为100，排序[0 99]内的整数
int C[k]; // 计数数组
void CountingSort(int A[] int n)
{
for (int i = 0; i < k; i )
// 初始化，将数组C中的元素置0(此步骤可省略，整型数组元素默认值为0)
{
C[i] = 0;
}
//int A[] = { 15 22 19 46 27 73 1 19 8 };
for (i = 0; i < n; i ) // 使C[i]保存着等于i的元素个数
{
C[A[i]] ;
}
for (i = 1; i < k; i )
// 使C[i]保存着小于等于i的元素个数，排序后元素i就放在第C[i]个输出位置上
{
C[i] = C[i] C[i - 1];
}
int *B = (int *)malloc((n) * sizeof(int));
// 分配临时空间 长度为n，用来暂存中间数据
for (i = n - 1; i >= 0; i--)
// 从后向前扫描保证计数排序的稳定性(重复元素相对次序不变)
{
B[--C[A[i]]] = A[i];
// 把每个元素A[i]放到它在输出数组B中的正确位置上
// 当再遇到重复元素时会被放在当前元素的前一个位置上保证计数排序的稳定性
}
for (i = 0; i < n; i ) // 把临时空间B中的数据拷贝回A
{
A[i] = B[i];
}
free(B); // 释放临时空间
}
int main()
{
int A[] = { 15 22 19 46 27 73 1 19 8 };
// 针对计数排序设计的输入，每一个元素都在[0 100]上且有重复元素
int n = sizeof(A) / sizeof(int);
CountingSort(A n);
printf("计数排序结果：");
for (int i = 0; i < n; i )
{
printf("%d " A[i]);
}
printf("\n");
cin.get();
return 0;
}
－End－
