一、算法概述
1.1 算法分類
十種常見排序算法可以分為兩大類：
比較類排序：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破O(nlogn)，因此也稱為非線性時間比較類排序。
非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此也稱為線性時間非比較類排序。
1.2 算法復雜度
1.3 相關(guān)概念
- 穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后 a 可能會出現(xiàn)在 b 的后面。
- 時間復雜度：對排序數(shù)據(jù)的總的操作次數(shù)。反映當n變化時，操作次數(shù)呈現(xiàn)什么規(guī)律。
- 空間復雜度：是指算法在計算機內(nèi)執(zhí)行時所需存儲空間的度量，它也是數(shù)據(jù)規(guī)模n的函數(shù)。
二、基數(shù)排序（Radix Sort）
基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序。最后的次序就是高優(yōu)先級高的在前，高優(yōu)先級相同的低優(yōu)先級高的在前。
原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較?；鶖?shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
- MSD：先從高位開始進行排序，在每個關(guān)鍵字上，可采用計數(shù)排序。
- LSD：先從低位開始進行排序，在每個關(guān)鍵字上，可采用桶排序。
2.1 算法描述
- 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
- arr為原始數(shù)組，從最低位開始取每個位組成radix數(shù)組；
- 對radix進行計數(shù)排序（利用計數(shù)排序適用于小范圍數(shù)的特點）；
2.2 動圖演示
分步圖示說明：設(shè)有數(shù)組 array = {53, 3, 542, 748, 14, 214, 154, 63, 616}，對其進行基數(shù)排序：
在上圖中，首先將所有待比較數(shù)字統(tǒng)一為統(tǒng)一位數(shù)長度，接著從最低位開始，依次進行排序。
- 按照個位數(shù)進行排序。
- 按照十位數(shù)進行排序。
- 按照百位數(shù)進行排序。
排序后，數(shù)列就變成了一個有序序列。
2.3 拓展
Radix Sort 基數(shù)排序是對計數(shù)排序的改進，該算法可以支持針對浮點、字符串等類型元素進行排序。其主要思想是將排序元素按數(shù)位分割依次排序，從而實現(xiàn)整體有序。其同樣可以具有線性時間的性能
在對非負整數(shù)進行基數(shù)排序時，需要首先將排序元素統(tǒng)一為相同的數(shù)位長度，數(shù)位不足的排序元素可以添加前導零的方式實現(xiàn)數(shù)位長度統(tǒng)一對齊；然后從排序元素的最低位（個位）開始進行排序，直到完成對最高位的排序，此時即實現(xiàn)了對排序元素的整體排序。而對每個數(shù)位進行排序的過程則是通過（穩(wěn)定的）計數(shù)排序完成的，故基數(shù)排序同樣是穩(wěn)定的。由于我們是從排序元素的最低位向最高位依次排序的，故這種方式被稱為最低位（LSD，Least Significant Digit）法；反之，如果是從排序元素的最高位向最低位依次排序的，則被稱之為最高位（MSD，Most Significant Digit）法
實際上，基數(shù)排序算法對排序元素的類型不要求一定是非負整數(shù)才可以進行，其對于字符串、浮點數(shù)等類型均可適用。其關(guān)鍵在于要求排序元素的數(shù)位長度統(tǒng)一。例如對整數(shù)排序時，如果排序元素中含有負數(shù)，則可以對排序元素均加上一個數(shù)使其全部為非負整數(shù)；如果元素類型是字符串的話，在計數(shù)排序過程中，可以直接使用該位字符對應(yīng)ASCII碼值進行計數(shù)，對于長度不足的字符串，可直接在其后面補0實現(xiàn)長度對齊。即在計數(shù)排序過程中，如果發(fā)現(xiàn)某位字符是為對齊所填充的0的話，則可認為其對應(yīng)的ASCII碼值為0進行計數(shù)，因為字符'A'所對應(yīng)的ASCII碼值是65，字符'0'所對應(yīng)的ASCII碼值是48，均比0大。這樣即可保證基數(shù)排序的結(jié)果是符合字典序的
三、代碼實現(xiàn)
/**
* @Author: huangyibo
* @Date: 2022/3/14 12:48
* @Description: 基數(shù)排序
*/
public class RadixSort {
public static void main(String[] args) {
int[] arr = {220, 134, 0, 153, 2, 1314, 87, 2022};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
// 找出數(shù)組arr中的最大值
int max = Arrays.stream(arr).max().getAsInt();
//基于計算排序?qū)υ氐拿總€位進行排序
//最多循環(huán)最大元素的位數(shù)，位數(shù)不夠的用0進行排序
for (int i = 10; i < max; i *= 10) {
countSort(arr, i);
}
}
/**
* 基于計算排序?qū)υ氐拿總€位進行排序
* 最多循環(huán)最大元素的位數(shù)，位數(shù)不夠的用0進行排序
* @param arr
* @param divider
*/
private static void countSort(int[] arr, int divider) {
// 基數(shù)（數(shù)位的取值范圍為[0,9]）
int radix = 10;
// 初始化計數(shù)數(shù)組count, 存儲每個數(shù)位出現(xiàn)的次數(shù)
int[] count = new int[radix];
// 對計數(shù)數(shù)組各元素賦值
for (int num : arr) {
// arr中的元素要減去最小值，再作為新索引
count[num / divider % radix]++;
}
// 計數(shù)數(shù)組變形，新元素的值是前面元素累加之和的值
for (int i = 1; i < count.length; i++) {
count[i] += count[i-1];
}
//從后往前遍歷元素，將其放在有序數(shù)組中的合適位置
// 創(chuàng)建結(jié)果數(shù)組
int[] newArray = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
newArray[--count[arr[i] / divider % radix]] = arr[i];
}
//將有序數(shù)組賦值給原數(shù)組
for (int i = 0; i < arr.length; i++) {
arr[i] = newArray[i];
}
}
}
四、算法分析
基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。但基數(shù)排序的性能比桶排序要略差，每一次關(guān)鍵字的桶分配都需要O(n)的時間復雜度，而且分配之后得到新的關(guān)鍵字序列又需要O(n)的時間復雜度。假如待排數(shù)據(jù)可以分為d個關(guān)鍵字，則基數(shù)排序的時間復雜度將是O(d*2n) ，當然d要遠遠小于n，因此基本上還是線性級別的。
基數(shù)排序的空間復雜度為O(n+k)，其中k為桶的數(shù)量。一般來說n>>k，因此額外空間需要大概n個左右。
參考：
https://www.cnblogs.com/onepixel/articles/7674659.html
