计数排序 0（n+m）.txt

来自「包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题」· 文本 代码 · 共 43 行

#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

//计数排序 
//时间复杂度为n+m(m<n,n为要排序的数字个数，m为这些数字中不同数字的个数
/*
输入：
10 8 5
7 5 6 8 8 5 6 7 7 6

输出：
5 5 6 6 6 7 7 7 8 8
*/
int D[10];

void init(int num)
{
	int i;
	for(i=0;i<num;i++) D[i]=0;
}

int main()
{
	int num,a[11],high,low,b[11],i;
	scanf("%d%d%d",&num,&high,&low);
	init(num);
	for(i=0;i<num;i++)
	{
		scanf("%d",&a[i]);
		D[a[i]-low]++;
	}
	for(i=1;i<=high-low;i++)
		D[i]=D[i-1]+D[i];
	for(i=num-1;i>=0;i--)
	{
		b[--D[a[i]-low]]=a[i];
	}
	for(i=0;i<num;i++)
		printf("%d ",b[i]);
	return 0;
}