基數排序

習題預習

1. Radix Sort是使用哪種排序演算法來排序數據？
2. 在Radix Sort中，什麼是基數？
3. 為什麼Radix Sort通常被視為一種穩定的排序演算法？
4. Radix Sort的時間複雜度是多少？此時間複雜度下如何優化？
5. 在什麼情況下，Radix Sort的效率最高？在什麼情況下，效率最低？

說明知識

Radix Sort是根據每個元素的位數來進行排序的一種排序算法。具體來說，它會先按照最低有效位來排序，然後依次往上排序，直到排完最高有效位。這樣排序完成後，元素就會被排好序了。

例如，對以下數列進行排序：
[170, 45, 75, 90, 802, 24, 2, 66]
首先按照最低有效位進行排序，即按照個位數進行排序，得到下列數列：
[170, 90, 802, 2, 24, 45, 75, 66]
再按照十位數進行排序，得到下列數列：
[2, 24, 45, 66, 75, 90, 170, 802]
這樣數列就被成功排序了。

優點：相對於其他排序算法，Radix Sort比較簡單，而且不需要比較元素的大小，只需要對每個元素進行指定位數的操作即可完成排序。在元素數量很大時，Radix Sort的效率會明顯高於其他排序算法。

缺點：需要額外的空間。

總體而言，Radix Sort是一種穩定、有效的排序算法。

彙總重點

1. Radix Sort是一種非比較性排序算法。

2. 排序的主要方式是通過比較數字的每一位，以確定它們的位置和順序。

3. 數字的每一位都被視為一個鍵(key)，每一個鍵都要排序。

4. Radix Sort可以使用LSD(Least Significant Digit)和MSD(Most Significant Digit)兩種方式進行排序。

5. LSD表示最不顯著位排序，MSD表示最顯著位排序。

6. MSD排序通常使用遞迴算法實現，LSD排序通常使用迭代算法實現。

7. 數字的每個鍵可以使用桶排序(bucket sort)或計數排序(counting sort)進行排序。

8. 實現Radix Sort，需要適當的預處理，以使得數據可以按照位數進行排序。

9. Radix Sort的時間複雜度為O(nd)，其中n是排序數列的元素個數，d是數字的最大位數。

10. Radix Sort通常用於排序長度固定的數字序列，如IP地址等。

知識測驗

1. 假設有一個包含10個亂數的整數陣列，要求使用Radix Sort由小到大排序，請列出排序後的陣列。

答案：排序後的陣列為{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}，但因為沒有給定範圍，數字可能不同。

2. 假設有一個字串陣列，要求使用Radix Sort按照字典序由小到大排序，請列出排序後的陣列。

答案：排序後的陣列會按照字典序由小到大排列，但因為未給定字串陣列，所以無法給出具體答案。

3. 假設有一個包含100個隨機數的整數陣列，要求使用Radix Sort由大到小排序，請列出排序後的前10個數字。

答案：排序後的前10個數字可能為{100, 99, 98, 97, 96, 95, 94, 93, 92, 91}，但因為數字隨機，有可能不同。

4. 假設有一個包含1000個整數的陣列，其中每個數字的值為1到1000之間的隨機數，要求使用Radix Sort將所有數字分成10組，請問在最後一輪排序完成後，第5組內會有哪些數字？

答案：最後一輪排序完成後，第5組內可能包含從401到500之間的數字。

5. 假設有一個包含10000個隨機英文字母的字串陣列，要求使用Radix Sort以ASCII碼由小到大排序，請列出排序後前20個字串。

答案：排序後前20個字串可能為{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t}，但因為字串隨機，有可能不同。