年齢順9

題目説明:1社の全従業員(おそらく万人以上)の年齢順に並べ替えて、一定の大きさの補助空間しか使用できない.解題構想:長さ100の整数配列を補助空間として用いて、0-99歳で出現した回数を計数する.ある年齢が何度も出現した場合、元の配列に順番に(下に)値順に並べ替える.テスト例:

//    
int main(){
    //          （0-99 ）
    int ages[20000];
    for(int i = 0; i < 20000; ++i)
        ages[i] = rand() % 100;  //      99

    //            
    sortAges(ages, 20000);
    //        
    for(int i = 0; i < 20000; ++i)
        std::cout << ages[i] << " ";

    return 0;
}

sortAges関数実装:

void sortAges(int ages[], int length){
    if(ages == NULL || length <= 0)
        return;
    //        0-99   ,     ，         0 
    int timesOfArges[100];
    for(auto i = 0; i < 100; ++i)
        timesOfArges[i] = 0;
    //     99
    const int oldestAge = 99;
    //      
    for(auto i = 0; i < length; ++i){
        //      
        int age = ages[i];
        //          （0-99）
        if(age < 0 || age > oldestAge)
            throw new std::exception("Age out of range.");
        ++timesOfArges[age]; //  ，   （   ）      
    }
    int index = 0; //    
    //            ，        ，           
    for(auto i = 0; i <= oldestAge; ++i){
        for(auto j = 0; j < timesOfArges[i]; ++j){ //j          
            ages[index] = i;
            ++index;
        }
    }
}