(二)給定 100 萬個介於 0 到 100（含 0 及 100）的整數，請利用任一種高階 程式語言寫出一個 O（N）的由大至小的排序演算法，並說明此演算法 為何是 O（N）的方法。（15 分）

以下使用C語言實作之。

void sort(int ori_array[],int size){//概念取至counting_sort，ori_array[]為100萬個隨機0~100的數字，size為100萬
int count_array[101] = {0};
for(int i=0;i<size;i++){//O(size)
count_array[ori_array[i]] += 1;//將原本的100萬個數字的值，當作索引存入count_array當中，count_array最終會記錄每一個數字出現幾次。
}
int index=0;
for(int i=100;i>=0;i–){//遍歷整個count_array，O(1)
while(count_array[i] != 0){//若count_array[i]內的值不為0，代表該數字出現在100萬個數字當中。O(1)
ori_array[index] = i;//將原本的陣列依據大而小排序。
index++;
count_array[i]–;//每排一個就減去count_array內的值，直到0為止。
}
}
}
此題size就是總數量，也就是N，故時間複雜度為O(N)

AI创作