基數排序

基數排序（radix sort）屬於“分配式排序”（distribution sort），又稱為“桶子法”（bucket sort）或bin sort，顧明思議，它是透過鍵值的各個位的值，將要排序的元素分配至某些桶中，達到排序的作用。

基數排序屬於穩定性的排序，基數排序法是效率高的穩定性排序法。

基數排序是桶排序的擴充套件。

基數排序是1887年赫爾曼·何樂禮發明的。它是這樣實現的：將整數按位數切割成不同的數字，然後按每個位數分別比較。

排序的基本思想

將所有待比較的值統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。

程式碼案例

package com。xie。sort；public class RadixSort { public static void main（String［］ args） { int［］ arr = new int［8000000］； for （int i = 0； i < 8000000； i++） { arr［i］ = （int）（Math。random（）*800000000）； } long start = System。currentTimeMillis（）； radixSort（arr）； long end = System。currentTimeMillis（）； System。out。println（“耗時：”+（end-start）+“ms”）； /* 800萬資料，耗時：939ms */ } //基數排序 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（）； //第1輪（針對每個元素的個位進行排序處理） //定義一個二維陣列，表示10個桶，每個桶就是一個一維陣列 //1。二維陣列包含10個一維陣列 //2。為了防止在放入數的時候，資料溢位，則每個一維陣列（桶），大小定為arr。length //3。基數排序是使用空間換時間的經典演算法 int［］［］ bucket = new int［10］［arr。length］； //為了記錄每個桶中，實際存放了多少資料，我們定義一個一維陣列來記錄各個桶的每次放入的資料的個數。 //bucketElementCounts［0］，記錄的就是bucket［0］桶的放入資料的個數。 int［］ bucketElementCounts = new int［10］； //按照桶的順序（一維陣列的下標依次取出資料，放入原來陣列） int index = 0； for （int i = 0， n = 10； 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］++； } 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 arr［index］ = bucket［k］［l］； index++； } } bucketElementCounts［k］ = 0； } } }}

基數排序說明

基數排序是拿空間換時間的，對海量資料進行排序時，容易造成OutOfMemoryError。

基數排序時穩定的。【注：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中r［i］=r［j］，且r［i］在r［j］之前，而在排序後的序列中，r［i］仍在r［j］之前，則稱這種演算法是穩定的，否則不穩定】。

對於有負數的陣列進行基數排序，參考：

https：//code。i-harness。com/zh-CN/q/e98fa9