题目:对某公司所有员工的年龄进行排序,要求时间复杂度为O(n)
分析:
在已有的排序算法中,性能最好的是快速排序,但是他在最好的情况下时间复杂度只能达到O(nlogn),无法满足本题的要求。但是我们可以从“年龄”这一特殊条件入手。
年龄具有显著的特征,那就是这些数值都分布在0-99之间。由于待排序的数值均在0-99这个固定区间内,因此我们可以用一个长度为100的数组,记录0-99这100个年龄出现的次数。我们只需要扫描一遍所有员工的年龄,就能统计出这个数组。最后只需要将该数组展开即可获得想要的结果。
/**
* 对某公司所有员工的年龄进行排序,要求时间复杂度为O(n)
* @author chibozhou
*
*/
public class AgeSort {
/**
* 排序函数
* @param ages 存放公司全体人员年龄的数组
*/
public static void ageSort(int[] ages){
//countAge的下标i代表年龄,countAge[i]代表年龄为i的员工人数
int[] countAge = new int[100];
//健壮性判断
if(ages==null || ages.length<=0){
System.out.println("数组为空!");
return;
}
for(int i=0;i<ages.length;i++){
if(ages[i]<0 || ages[i]>99){
System.out.println("数组中存在非法年龄!");
return;
}
}
//统计每个年龄的人数,存储在countAge数组中
for(int i=0;i<ages.length;i++)
countAge[ages[i]]++;
//将countAge数组展开,存放在ages数组中
int curIndex = 0;//用于记录ages数组当前下标
for(int i=0;i<countAge.length;i++){
for(int j=0;j<countAge[i];j++){
ages[curIndex] = i;
curIndex++;
}
}
}
}