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

創(chuàng)新互聯(lián)建站堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的東鄉(xiāng)網(wǎng)站設(shè)計(jì)、移動媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

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

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

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

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

算法說明：

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

采用LSD，從低位開始排序

第一輪：取個(gè)位數(shù)，放入對應(yīng)的桶，比如12的個(gè)位數(shù)是2，放到2號桶；34的個(gè)位數(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ù)排序的代碼實(shí)現(xiàn)

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

網(wǎng)頁名稱：好程序員Java學(xué)習(xí)路線分享5分鐘了解基數(shù)排序
網(wǎng)頁路徑：http://jinyejixie.com/article20/gggcco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、網(wǎng)站內(nèi)鏈、用戶體驗(yàn)、微信小程序、靜態(tài)網(wǎng)站、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)