一个时间效率为O(n)的排序算法（Java实现）

题目：请实现一个排序算法，要求时间效率为O(n).(允许使用常量大小的辅助空间不得超过O（n）)

该题来自于剑指offer，用空间来换时间效率

package cn.stack.queue; //该方法用长度为100的整数数组作为辅助空间换来了O（N）的时间效率 public class Demo3 { public void sortAge(int[] ages) { int length = ages.length; int oldestAge = 99; // 建立一个数组，用来存储每个年龄员工的数量 int[] timesOfAge = new int[oldestAge + 1]; // 初始化 for (int i = 0; i <= 99; i++) { timesOfAge[i] = 0; } // 循环统计 int age = 0; for (int i = 0; i < length; i++) { age = ages[i]; if (age > 99 || age < 0) { System.out.println("年龄输入有误"); return; } timesOfAge[age]++; } //进行排序，结果存储在ages数组中 int index = 0; for (int i = 0; i <= oldestAge; i++) { for (int j = 0; j < timesOfAge[i]; j++) { ages[index] = i; ++index; } } } }