实现一个排序,要求时间效率O(n)

数据大小是在一个范围内的,可以使用常量大小的辅助空间.不得超过O(n);

 1 #include "stdafx.h"
 2 #include <iostream>
 3 #include<stack>
 4 #include<exception>
 5 using namespace std;
 6 
 7 void SortAges(int ages[],int length)
 8 {
 9     if(ages==NULL||length<=0)
10         return;
11     const int oldestAge = 10;
12     int timesOfAge[oldestAge+1];
13     for(int i = 0;i<=oldestAge;++i)
14         timesOfAge[i]=0;
15     //统计出各个年龄段人数,timesOfAge用来统计每个年龄出现的次数.
16     for(int i = 0;i<length;++i)
17     {
18         int age =  ages[i];
19         if(age<0||age>oldestAge)
20             throw new std::exception("age out of range.");
21         ++timesOfAge[age];
22     }
23     int index = 0;
24     //某个年龄出现了多少次，就在数组ages里设置几次该年龄.
25     for(int i = 0;i<=oldestAge;++i)
26     {
27         for(int j = 0;j<timesOfAge[i];++j)
28         {
29             ages[index]=i;
30             ++index;
31         }
32     }
33 
34 }
35 int _tmain(int argc, _TCHAR* argv[])
36 {
37     int a[11]={4,5,3,6,2,3,4,6,8,4,3};
38     SortAges(a,11);
39     for(int i = 0;i!=11;++i)
40         cout<<a[i]<< "  ";
41     return 0;
42 }