C++實現計數排序

Question

我正在做一個基於計數排序的非基於比較的排序。

我在紙上做了一個模擬，但實際上在編碼時遇到了麻煩。

我知道我需要創建一個count數組，然後在計數之後使用另一個數組累加它，然後用這個數組作爲一個新的數組使用累加和對它進行排序。我怎樣才能讓count數組跟蹤？那部分讓我困惑

任何人都可以引導我在正確的方向？

int schoolToIndex(string school) { 
    if (school == "UCB") return 0; 
    if (school == "UCD") return 1; 
    if (school == "UCI") return 2; 
    if (school == "UCLA") return 3; 
    if (school == "UCM") return 4; 
    if (school == "UCSD") return 5; 
    if (school == "UCSF") return 6; 

    cerr << "Unknown school " << school << endl; 
    return -1; 
} 

/* 
* Sorts students by school. An implementation of counting sort. 
* @param students array already sorted by ID 
* @param len Array length 
*/ 
void sortByGroupById2(Student students[], int len) { 
    int temp[len]; 
    int count[7]; 

    // Creates an array where schools are converted to ints by using schoolToIndex 
    for(int i = 0; i < len; i++) { 
     temp[i] =schoolToIndex(students[i].getSchool()); 

    } 

    for(int i =0; i < 7; i++) { 
     count[i]=0; 
    } 


    for(int j =0; j < len; j++) { 
     count[temp[j]]++; 
     cout << j << " " << count[j] << endl; 

    } 
} 

使用

Joe Paarmann,10000010,UCSF 
Otha Baloy,10000053,UCSD 
Alton Hamblet,10000110,UCM 
Jessie Merle,10000345,UCI 
Lawanda Doell,10000455,UCM 
Alva Zajicek,10000479,UCI 
Chester Kemfort,10000529,UCD 
Alice Mines,10000579,UCI 
Gary Vongunten,10000875,UCM 
Adrian Shbi,10001036,UCSD 

Answer 1

計數排序test.txt文件IM，你先統計有多少學生通過學校的存在（第一傳遞陣列）。然後你推斷每所學校的第一名學生的指數。最後你將學生存儲在目標數組中的正確位置（第二次傳遞數組）

計數排序不是就地排序，因此應該將另一個數組傳遞給函數以獲取排序值。

/* 
* Sorts students by school. An implementation of counting sort. 
* @param students array already sorted by ID 
* @param len Array length 
*/ 
void sortByGroupById2(Student students[], Student* sorted[], int len) { 
    int count[6]; 

    // initialization 
    for(int i=0; i<6; i++) count[i] = 0; 

    // how many students by school 
    for (int i=0; i<len; i++) { 
     count[schoolToIndex(students[i].getSchool())]++ 
    } 

    // convert number of students per school into index of first student 
    int rank = 0, old; 
    for (int i=0; i<6; i++) { 
     old = count[i]; 
     count[i] = rank; 
     rank += old; 
    } 

    // affect students in correct places 
    for (int i=0; i<len; i++) { 
     rank = count[students[i].getSchool()]++; // rank in sorted array will be current 
       // value of count for the school (first place for first time) and that 
       // value is incremented to be ready for next student for this school 
     sorted[rank] = &Student[i]; 
    } 
} 

這樣sorted countains指向學生由學校來分類的。

參考文獻：Wikipedia