实现一个排序算法时间复杂度为O(n)

实现一个排序算法，要求时间效率为O(n)

• 面试官：实现一个排序算法，要求时间效率为O(n)

• 应聘者：对什么数字，有多少个数字

• 面试官：对几万名公司员工的年龄

• 应聘者：也就是说大小在一定的范围内是吧

• 面试官：是的

• 应聘者：可以使用辅助空间吗

• 面试官：可以但是空间复杂度不能超过O(n)

我们遇到这个问题的思路。

• 运行使用辅助空间，可以搞一个HashTable或者数组之类的辅助
• 写代码的时候边界条件控制。第一位
• 用一个数组记录每个年龄出现的此时。然后从0到n开始遍历
• 然后从低位到高位遍历。根据当前年龄对应的次数数组，修改原来数组的排序。

废话不多说了，直接上代码。有错希望给指正~ 。

void SortAges(int ages[],int length){

//边界条件控制
if (ages == nullptr||length<=0) {
    return;
}

const int oldestAge = 99 ;
//记录每个年龄出现的次数
int timesOfAge[oldestAge+1];
//初始化数组
for (int i=0 ; i<=oldestAge; i++) {
    timesOfAge[i] = 0;
}
for (int i= 0; i<length; i++) {
    int age =  ages[i];
    if (age<0 || age>oldestAge) {
        return;
    }
    // 这个年龄出现的次数+1
    ++timesOfAge[age];
}
int index = 0;

for (int i =0 ; i<oldestAge; i++) {
    // 遍历次数的数组。根据年龄。
    for (int j =0 ; j<timesOfAge[i]; j++) {
        ages[index] = i ;
        ++ index;
    }
}
}