一：基本概念
1.1 基數排序(桶排序)介紹
-
基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是通過鍵值的各個位的值，將要排序的元素分配至某些“桶”中，達到排序的作用
-
基數排序法是屬于穩定性的排序，基數排序法的是效率高的穩定性排序法
-
基數排序(Radix Sort)是桶排序的擴展
-
基數排序是1887年赫爾曼·何樂禮發明的。它是這樣實現的：將整數按位數切割成不同的數字，然后按每個位數分別比較。
1.2 實現原理
將所有待比較數值統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。
1.3 將{53, 3, 542, 748, 14, 214} 使用基數排序, 進行升序排序
1.3.1 第1輪排序
數組的初始狀態 arr = {53, 3, 542, 748, 14, 214}
(1) 將每個元素的個位數取出，然后看這個數應該放在哪個對應的桶(一個一維數組)
(2) 按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)
1.3.2 第2輪排序
數組的第1輪排序 arr = {542, 53, 3, 14, 214, 748}
(1) 將每個元素的十位數取出，然后看這個數應該放在哪個對應的桶(一個一維數組)
(2) 按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)
1.3.3 第3輪排序
數組的第2輪排序 arr = {3, 14, 214, 542, 748, 53}
(1) 將每個元素百位數取出，然后看這個數應該放在哪個對應的桶(一個一維數組)
(2) 按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)
數組的第3輪排序 arr = {3, 14, 53, 214, 542, 748}
1.4 原理圖
二：復雜度
2.1 時間復雜度
2.2 空間復雜度
LSD算法中，由于逐次清理 array 中數據，外層每一循環會開辟大小為 10 的桶，那么空間復雜度為：O ( k )，或者記為：O ( n + k )
三：代碼實現
3.1 基數排序代碼
/*** 基數排序*/
public class RadixSort {public static void main(String[] args) {//原始數組long start = System.currentTimeMillis();int[] array = new int[8000000];for (int i = 0; i < array.length; i++) {//Math.random() * 80000生成0到100的隨機數array[i] = (int) (Math.random() * 80000);}//System.out.println("排序前：" + Arrays.toString(array));radixSort(array);long end = System.currentTimeMillis();System.out.println("執行時間為：" + (end - start));}/*** 基數排序方法* <p>* 說明：* 1.二維數組包含了十個一維數組* 2.為了防止數據在插入數組時，數據溢出，則每個桶的大小定義為array.length* 3.基數排序就是空間換時間的最典型的算法** @param array 需要排序的數組*/public static void radixSort(int[] array) {//先得到數組中最大數的位數//首先假定第一位數就是最大數int max = array[0];for (int i = 1; i < array.length; i++) {if (array[i] > max) {max = array[i];}}//得到最大數是幾位數int maxLength = (max + "").length();//定義二維數組，表示十個桶，每個桶就是一個一維數組int[][] bucket = new int[10][array.length];//為了記錄每個桶中實際存放了多少個數據（每次存放的時候，數據是不一樣的），我們定義一個一維數組記錄每次存放的數據個數// [0]記錄的就是bucket[0]這個桶，每次放入數據的個數int[] bucketElementCounts = new int[10];//最大位數有maxLength，所以遍歷maxLength次for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {//第i輪排序：針對每個元素的位數進行排序,第一次是個位數，第二次是十位數，以此類推for (int j = 0; j < array.length; j++) {//取出每個元素的個位數的數值int digitOfElement = array[j] / n % 10;//放入到對應的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = array[j];//每添加一次，需要加一，保證每添加一次數據就會更新數量bucketElementCounts[digitOfElement]++;}//按照這個數組的順序（一維數組的下標依次取數據，放入原來的數組）int index = 0;//遍歷每一個桶，并且將同種的數據放入到原數組當中for (int k = 0; k < bucketElementCounts.length; k++) {//如果桶中有數據，我們才放入到原數組中if (bucketElementCounts[k] != 0) {//循環該桶，即第k個桶，也就是第k個一維數組for (int l = 0; l < bucketElementCounts[k]; l++) {//取出元素導入到arr中array[index] = bucket[k][l];index++;}}//第i+1輪處理后需要將每個bucketElementCounts[k]置為0bucketElementCounts[k] = 0;}//第一輪排序結束//System.out.println("第" + (i + 1) + "輪：對個位排序處理array=" + Arrays.toString(array));}//System.out.println("排序后：" + Arrays.toString(array));}
}3.2 八百萬條數據的執行時間
執行時間為：442毫秒
)
)
