# 基數排序(Radix Sort)

* 基數排序(Radix Sort)屬於分配式排序(Distribution Sort)，又稱 **桶排序(Bucket Sort)** 或Bin Sort，是1887年 *赫爾曼·何樂禮* 發明的。
* 實現方式是：將整數按位數切割成不同的數字，然後按每個位數分別比較。
* 基數排序法是屬於**穩定性**的排序。
* 基數排序是對傳統桶排序的擴展，速度很快。
* 基數排序是經典的空間換時間的方式，佔用記憶體很大，當對海量數據排序時容易造成**OutOfMemoryError**。
* 有負數的陣列，我們**不用**基數排序法來進行排序，若要支持負數，可以參考：https://code.i-harness.com/zh-CN/q/e98fa9 。

**何謂穩定性排序？**

當有一陣列值為 `[1, 3, 7, 1, 3]`
排序後結果為 `[1, 1, 3, 3, 7]`
排序後第一個1 就是原陣列`arr[0]` 的 1，第二個 1 是原陣列`arr[1]` 的 1 ，也就是說，即使是相同值的元素排序前後次序依然不變，這就是穩定性排序。

## 基本思想

1. 將所有待比較數值統一為同樣的位數長度，位數較短的數前面補零。
1. 然後，從最低位開始，依次進行一次排序。
1. 這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。
2. 要做多少輪排序取決於所有元素中最高位數元素的位數。

## 舉例說明

設原始陣列為 `{53, 3, 542, 748, 14, 214}`，請使用基數排序為由小到大。

**第一輪：**
1. 將每個元素的個位數取出，依個位數放到對應的桶(一個一維陣列)。
2. 按照這個桶的順序(一維陣列的索引依次取出數據，放入原來陣列)。


第一輪後，排序結果為 `{542, 53, 3, 14, 214, 748}`

**第二輪：**
1. 將每個元素的十位數取出，依十位數放到對應的桶，沒有十位數就補零。
2. 按照這個桶的順序(一維陣列的索引依次取出數據，放入原來陣列)。


第二輪後，排序結果為 `{3, 14, 214, 542, 748, 53}`

**第三輪：**
1. 將每個元素的百位數取出，依百位數放到對應的桶，沒有百位數就補零。
2. 按照這個桶的順序(一維陣列的索引依次取出數據，放入原來陣列)。


第三輪後，排序結果為 `{3, 14, 53, 214, 542, 748}`

此時，已經由小到大排序完畢。

## 程式碼實現

package Sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int arr[] = {53,  3,  542,  748,  14,  214};
        radixSort(arr);
    }

    public static void radixSort(int[] arr) {
        // 得到陣列中最大的數的位數
        int max = arr[0];
        for(int i = 1; i < arr.length; i++) {
            if(arr[i] > max) {
                max = arr[i];
            }
        }
        
        int maxLength = (max + "").length(); 

        // 定義一個二維陣列,表示10個桶,每個桶就是一個一維陣列
        // 1. 二維陣列包含10個一維陣列
        // 2. 為了防止在放入數的時候，數據溢出，則每個一維陣列大小定為arr.length => 空間換時間
        int[][] bucket = new int[10][arr.length];

        // 定義為一個一維陣列,紀錄各個桶每次放入的數據個數
        int[] bucketElementCounts = new int[10];

        // 針對每個元素的各位數進行排序處理
        for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
            for(int j = 0; j < arr.length; j++) {
                // 取出每個元素的的對應位數的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到對應的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++ ;
            }
    
            // 遍歷每個桶, 並將桶中數據放入到原陣列
            int index = 0;
            for(int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中有數據才放入到原陣列
                if(bucketElementCounts[k] != 0) {
                    // 遍歷該桶 放入
                    for(int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                // 每輪處理後要將 bucketElementCounts 清零
                bucketElementCounts[k] = 0;
            }
            System.out.println("第 "+(i+1)+" 輪排序後為："+Arrays.toString(arr));
        }
    }
}

output

第 1 輪排序後為：[542, 53, 3, 14, 214, 748]
第 2 輪排序後為：[3, 14, 214, 542, 748, 53]
第 3 輪排序後為：[3, 14, 53, 214, 542, 748]

## 速度測試

public static void main(String[] args) {
        // int arr[] = {53,  3,  542,  748,  14,  214};
        int arr[] = new int[80000];
        for(int i = 0; i < 80000; i++) {
            arr[i] = (int)(Math.random() * 80000);
        }
        Instant startTime = Instant.now();
        radixSort(arr);
        Instant endTime = Instant.now();
        System.out.println("共耗時：" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
}

output

共耗時：15 毫秒
共耗時：15 毫秒
共耗時：15 毫秒
共耗時：15 毫秒

測了四次都是很穩定的 15ms 就能排序八萬筆數據。