Counting Sort (計數排序法)

概念 - 教學影片

想像在票選班長，有很多候選人，接下來老師一張一張票拿出來唱名。

作法

1. 開一個夠大的陣列 ( map )
2. 針對每一個元素，把元素當索引值，把陣列值+1

Pseudo Code

const int N = 5;
int students[N] = {4,3,5,1,7};

// 最大數字到7
int counting[ 8 ];

// 初始化
for ( int i = 0 ; i < 8 ; i++ )
    counting[i] = 0;

for ( int i = 0 ; i < N ; i++ ){
    counting[ students[i] ]++;
}

// 把counting換算成總和
for ( int i = 0 ; i < 8 ; i++ ){
    counting[i+1] += counting[i];
}

for(int i=0;i<N;i++){
    int element = students[i];
    int index = counting[element]-1;
    sortedStudents[index]=element;
    counting[element]--;
}

// sortedStudents 是排序過的陣列