#j. 计数排序
计数排序
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
计数排序不是一个比较排序算法，该算法于1954年由 Harold H. Seward提出，通过计数将时间复杂度降到了O(N)。
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
2.1 算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
#include <iostream>
using namespace std;
const int MAXN = 100000;
const int k = 1000; // range(范围)
int a[MAXN], c[MAXN], r[MAXN];// c数组用来计数，
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
++c[a[i]]; //计数
}
for (int i = 1; i < k; i++) //c[i]前缀和,得到i在排序后序列中的位置为c[i]
c[i]+= c[i-1];
for (int i = n-1; i >=0; i--) //反向倒填
-------//
for (int i = 1; i <=n; ++i)
cout << r[i] <<endl;
return 0;
}
Input Format
一个n，接下来n个整数m（ 0<m<100000）Output Format
从小到大输出n个数，以空格隔开6
1 89 5 6 23 51 5 5 6 23 89