数据大小是在一个范围内的,可以使用常量大小的辅助空间.不得超过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 }