好程序員Java學(xué)習(xí)路線分享5分鐘了解基數(shù)排序，前言：基數(shù)排序無需進(jìn)行比較和交換，而是利用分配和收集兩種基本操作實(shí)現(xiàn)排序?；鶖?shù)排序分為兩種：第一種是LSD ，從最低位開始排序；第二種是 MSD， 從最高位開始排序。
基數(shù)排序思想介紹
分配：對(duì)于數(shù)字，每位的取值范圍是0-9，因此需要10個(gè)容器（我們可以將其稱為桶），這10個(gè)桶標(biāo)號(hào)為0-9。每趟排序時(shí)，我們?nèi)∶恳粋€(gè)元素在該位的數(shù)值依次放入桶中。
收集：在一趟排序完成后，我們按順序從0-9的桶中依次取元素。
算法說明：
待排序數(shù)據(jù)：12, 34, 2, 123, 25, 59, 37
采用LSD，從低位開始排序
第一輪：取個(gè)位數(shù)，放入對(duì)應(yīng)的桶，比如12的個(gè)位數(shù)是2，放到2號(hào)桶；34的個(gè)位數(shù)是4，放到4號(hào)桶
第一輪后，得到數(shù)據(jù)：12, 2, 123, 34, 25, 37, 59
第二輪：取十位數(shù)，放入桶中。比如2，十位數(shù)是0，放到0號(hào)桶
第二輪后，得到數(shù)據(jù)：2, 12, 123, 25, 34, 37, 59
第三輪：取百位數(shù)，放入桶
最后，得到有序數(shù)據(jù) 2, 12, 25, 34, 37, 59, 123
基數(shù)排序的代碼實(shí)現(xiàn)
private static void radixSort(int[] arr) {
//存儲(chǔ)大值，暫時(shí)記錄為第一個(gè)元素
int max = arr[0];
//獲取待排序數(shù)組中的大值
for (int v : arr) {
if (v > max) {
max = v;
}
}
// 用列表表示桶，一共10個(gè)桶，每個(gè)桶對(duì)應(yīng)的元素也是列表
List
for(int i = 0; i < 10; i ++) {
list.add(new ArrayList
}
// 確定循環(huán)輪數(shù)
for(int i = 0, factor = 1; i < max; factor *= 10, i ++) {
for(int j = 0; j < arr.length; j ++) {
// 根據(jù)相應(yīng)的位（個(gè)位/十位...）取通號(hào)，然后將數(shù)據(jù)放入桶中
list.get((arr[j] / factor) % 10).add(arr[j]);
}
// 遍歷桶，將其中數(shù)據(jù)放入arr數(shù)組中
for(int j = 0, k = 0; j < list.size(); j ++) {
while(!list.get(j).isEmpty()) {
arr[k] = list.get(j).get(0);
list.get(j).remove(0);
k++;
}
}
}
}
總結(jié)
基數(shù)排序是一種按記錄關(guān)鍵字的各位值逐步進(jìn)行排序的方法。一般適用于記錄的關(guān)鍵字為整數(shù)類型的情況，對(duì)于字符串和文字排序不適合。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
