一、题目描述
实现一个排序算法，要求时间复杂度为O(n)。情景：公司共有几万名员工，想对公司所有员工的年龄（数字范围较小0-99）排序，可以使用常量大小的辅助空间，不得超过O(n)
二、解题思路
1）申请一个长度为100的数组timesofAges[100]--初始值赋0，用于记录在年龄ages数组中该年龄出现的次数：timesofAges[age]=times--（键是年龄，存储的时候就是从小到大，值是次数）---遍历一次ages，复杂度O(n)
2）从头到尾遍历timesofAges数组（实现年龄从小到大），将键age按照值times出现的个数重新写入原ages数组。辅助空间100<<n
三、解题算法
/********************************************************** 面试题8-O(n)的排序 Author:tmw date:2018-6-28 **********************************************************/ #include <stdio.h> #include <stdlib.h> #define CONST_AREA 100 //额外申请的空间，实际手工测试可按需修改此值 /** *@param *ages 为员工年龄数组 *@param *lenght 为年龄数组 * *！！注意：代码未用测试例，看逻辑就好 * 若需测试此代码，请设置：CONST_AREA<<length **/ int* sortAges( int* ages, int length ) { /**算法入口判断**/ if( ages==NULL || length==0 ) return NULL; /**申请额外空间数组timesofAges，并初始化0**/ int* timesofAges = (int*)malloc(CONST_AREA*sizeof(int)); int i,j; for( i=0; i<CONST_AREA; i ) timesofAges[i] = 0; /**遍历一遍ages数组，用timesofAges[CONST_AREA]记录各年龄出现的次数--O(n)**/ for( i=0; i<length; i ) { //年龄填写有误，则不做处理 if( ages[i] < 0 || ages[i] > CONST_AREA-1 ) continue; else timesofAges[ages[i]] ; } /**改写ages数组，完成排序**/ int index = 0; for( i=0; i<CONST_AREA; i ) { //该年龄i出现的次数 for(j=0; j<timesofAges[i]; j ) ages[index ] = i; } return ages; }
