本文主要是介绍剑指offer——年龄排序问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：对某公司所有员工的年龄进行排序，要求时间复杂度为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++;}}}
｝这篇关于剑指offer——年龄排序问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
