基數排序

基數排序（Radix Sort）是一種非比較型整數排序算法，其核心思想是將整數按位數切割成不同的數字，然後對每個位數分別進行比較和排序。基數排序適用於大範圍數據的排序，打破了計數排序的限制。

在基數排序中，有兩種主要的排序方式：最低位優先法（LSD）和最高位優先法（MSD）。LSD是從最低位開始向最高位依次進行排序，而MSD則是從最高位開始向最低位排序。LSD適用於位數較小的數列，而對於位數較多的數列，MSD的效率會更高。

基數排序的過程通常包括三個步驟：

統一數位長度：首先將所有待比較的數值統一為同樣的數位長度，數位較短的數前面補零。

依次排序：然後從最低位（或最高位）開始，依次進行一次排序。

合併回有序序列：這樣從最低位（或最高位）排序一直到最高位（或最低位）排序完成以後，數列就變成了一個有序序列。

基數排序不僅限於整數，由於其整數也可以表達字元串（如名字或日期）和特定格式的浮點數，基數排序也適用於這些類型的排序。

時間複雜度為O(k*N)，空間複雜度為O(k + N)，其中k是數字的位數，N是數字的數量。基數排序是穩定的，因為相同的元素在排序前後順序不變。