首页 > 代码库 > 【剑指offer】员工年龄排序

【剑指offer】员工年龄排序

典型的以空间换时间问题,思路很重要!

/*
员工年龄排序
  员工可能有几万名,要求时间复杂度为O(n)
  思路:员工的年龄必然在一个范围内,比如0-99,那么我们建立一个大小为100的辅助数组,然后遍历
		员工年龄,取到一个年龄就将该年龄对应数组位置的值加1,最终数组中便保存了不同年龄的员工的个数
		最后,打印数组即可。
 by Rowandjj
2014/7/22
*/
#include<iostream>
using namespace std;
#define MAX 100
void sort(int ages[],int len)
{
	int temp[MAX],i,j;
	//初始化辅助数组
	for(i = 0; i < MAX; i++)
	{
		temp[i] = 0;
	}
	//遍历年龄数组,获取不同年龄的员工个数存到辅助数组中
	for(i = 0;i < len; i++)
	{
		temp[ages[i]]++;
	}
	//对年龄数组排序
	int index = 0;
	for(i = 0; i < MAX; i++)
	{
		for(j = 0; j < temp[i]; j++)
		{
			ages[index] = i;
			index++;
		}
	}
}
int main()
{
	int ages[] = {21,56,13,23,11,21,6,12,13,53,11,56,12,13,5,11,45,11,41,67,21,56,23,19,10};
	sort(ages,25);
	for(int i = 0; i < 25; i++)
	{
		cout<<ages[i]<<" ";
	}
	cout<<endl;
	
	return 0;
}

测试: