好程序員Java學(xué)習(xí)路線分享5分鐘了解基數(shù)排序

　　好程序員Java學(xué)習(xí)路線分享5分鐘了解基數(shù)排序，前言：基數(shù)排序無需進(jìn)行比較和交換，而是利用分配和收集兩種基本操作實現(xiàn)排序?；鶖?shù)排序分為兩種：第一種是LSD ，從最低位開始排序；第二種是 MSD， 從最高位開始排序。

基數(shù)排序思想介紹

分配：對于數(shù)字，每位的取值范圍是0-9，因此需要10個容器（我們可以將其稱為桶），這10個桶標(biāo)號為0-9。每趟排序時，我們?nèi)∶恳粋€元素在該位的數(shù)值依次放入桶中。

2. 收集：在一趟排序完成后，我們按順序從0-9的桶中依次取元素。

3. 繼續(xù)進(jìn)行分配和收集，直到最大位數(shù)排序完成。

算法說明：

待排序數(shù)據(jù)：12, 34, 2, 123, 25, 59, 37

采用LSD，從低位開始排序

第一輪：取個位數(shù)，放入對應(yīng)的桶，比如12的個位數(shù)是2，放到2號桶；34的個位數(shù)是4，放到4號桶

第一輪后，得到數(shù)據(jù)：12, 2, 123, 34, 25, 37, 59

第二輪：取十位數(shù)，放入桶中。比如2，十位數(shù)是0，放到0號桶

第二輪后，得到數(shù)據(jù)：2, 12, 123, 25, 34, 37, 59

第三輪：取百位數(shù)，放入桶

最后，得到有序數(shù)據(jù) 2, 12, 25, 34, 37, 59, 123

基數(shù)排序的代碼實現(xiàn)

private static void radixSort(int[] arr) {
//存儲最大值，暫時記錄為第一個元素
int max = arr[0];
//獲取待排序數(shù)組中的最大值
for (int v : arr) {
if (v > max) {
max = v;
}
}
// 用列表表示桶，一共10個桶，每個桶對應(yīng)的元素也是列表
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0; i < 10; i ++) {
list.add(new ArrayList<Integer>());
}
// 確定循環(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)的位（個位/十位...）取通號，然后將數(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ù)類型的情況，對于字符串和文字排序不適合。