【剑指offer】员工年龄排序

转载请注明出处：http://blog.csdn.net/ns_code/article/details/25144793

对公司全部员工的年龄进行排序，公司总共同拥有几万名员工，要求时间复杂度为O（n）。

非常明显的计数排序题目，员工的年龄肯定在一个范围之内，我们这里如果在0-99之内，算非常大了，这样就能够开辟一个长度为100的数组，保存各个年龄的员工的个数。

代码例如以下：

/*
员工年龄排序，主要用计数排序的思想,
时间复杂度为O(n)，须要固定大小的额外辅助空间
*/
#include<stdio.h>
#include<string.h>

/*
计数排序，员工年龄肯定在0-99之间
*/
void SortAge(int ages[],int len)
{
	if(ages == NULL || len<1)
		return ;
	int timesOfAge[100];
	memset(timesOfAge,0,sizeof(timesOfAge));
	int i;
	//计算每一个年龄员工的个数
	for(i=0;i<len;i++)
	{
		if(ages[i]<=99 && ages[i]>=0)
			timesOfAge[ages[i]]++;
	}
	//对ages进行排序
	int index = 0;
	for(i=0;i<100;i++)
	{
		int j = 0;
		while(j<timesOfAge[i])
		{
			ages[index++] = i;
			j++;
		}
	}
} 

int main()
{
	int ages[] = {33,34,45,24,36,23,21,22,19,26,45,34,21,34,34,33,52,22,32,25,27,43,22,21,20,33,26,27,15,29};
	int len = 30;
	SortAge(ages,len);
	int i;
	for(i=0;i<len;i++)
		printf("%d ",ages[i]);
	printf("
");
	return 0;
}

測试结果：

算法准备放一放了，立即就要开题了，竟然一点紧张感都没有，论文方向是搞视频异常检測的，还是有点小难度的，导师尽管是所谓的国家有突出贡献科学家，可是依旧无论不问，毕竟这么大把年纪了。也能够理解，万事还是要靠自己。

渐渐从实习生招聘的阴影中走出来了，事实上也就面了两家公司而已。开题后要转移重点了。做了些Android项目，可是掌握比較深入的却在jvm和java并发机制，Android平台相关的技术掌握的比較皮毛。接下来要加深对网络协议，java网路编程和Android平台的学习，再做个比較好点的项目。完好下之前的项目，总感觉自己的项目拿不出手，并且又不太会吹，哎！

！