基數排序

基數排序

基數排序不基于比較和移動，而是基于關鍵字的大小進行排序。

基數排序通常有最高位優先與最低為優先兩種實作方法。

主要思想為：按照關鍵字的權重大小依次進行排序，最後形成一個有序序列。

取到數組中的最大值，計算出它的位數，設為n（它的位數就是最外層循環的次數）

如何計算位數 n ？

規律如下：

建立十個空隊列（每1位數字最大可表示0-9共十位數字，是以要十個）

隊列也是資料結構的一種，在此就不另行提供啦，我用的是自己寫的鍊隊列。

設外層循環進度為 i (循環進行到了第 i 次， i >= 1)，目前進行到了第 i 次最外層循環，則将有序清單中的每個元素第 i 位（個位為1，十位為2，百位為3...以此類推）放入 i 的值所對應的隊列中

舉例:（比如2021，第一次循環時，它的個位為1，是以将它放在queue[1]中，第三次循環時，它的百位為0，是以将它放在queue[0]中....）

一次外層循環結束後，從隊列0開始依次将元素出隊，放入原先的數組中

隊列先進先出，是以第0（從0開始計數）個隊列的第1（從1開始計數）個元素就放在數組下标為0的位置上，以此類推，一個隊列空換下一個隊列，直到全部隊列都出隊完成。

如此重複n次，你就會發現神奇的一件事情——數組竟然有序啦！

基數排序也屬于穩定排序；

基數排序的空間複雜度為O（r）【r個隊列：r個隊頭指針和r個隊尾指針】，時間複雜度為O（d(n+r)）。