基本思想
基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。基數(shù)排序可以采用兩種方式：
LSD（Least Significant Digital）：從待排序元素的最右邊開始計(jì)算（如果是數(shù)字類型，即從最低位個(gè)位開始）。MSD（Most Significant Digital）：從待排序元素的最左邊開始計(jì)算（如果是數(shù)字類型，即從最高位開始）。我們以LSD方式為例，從數(shù)組R[1..n]中每個(gè)元素的最低位開始處理，假設(shè)基數(shù)為radix，如果是十進(jìn)制，則radix=10。基本過程如下所示：
計(jì)算R中最大的元素，求得位數(shù)最大的元素，最大位數(shù)記為distance；對(duì)每一位round<=distance，計(jì)算R[i] % radix即可得到；將上面計(jì)算得到的余數(shù)作為bucket編號(hào)，每個(gè)bucket中可能存放多個(gè)數(shù)組R的元素；按照bucket編號(hào)的順序，收集bucket中元素，就地替換數(shù)組R中元素；重復(fù)2~4，最終數(shù)組R中的元素為有序。算法實(shí)現(xiàn)
基數(shù)排序算法，java實(shí)現(xiàn)，代碼如下所示：
public abstract class Sorter { public abstract void sort(int[] array); } public class RadixSorter extends Sorter { PRivate int radix; public RadixSorter() { radix = 10; } @Override public void sort(int[] array) { // 數(shù)組的第一維表示可能的余數(shù)0-radix，第二維表示array中的等于該余數(shù)的元素 // 如：十進(jìn)制123的個(gè)位為3，則bucket[3][] = {123} int[][] bucket = new int[radix][array.length]; int distance = getDistance(array); // 表示最大的數(shù)有多少位 int temp = 1; int round = 1; // 控制鍵值排序依據(jù)在哪一位 while (round <= distance) { // 用來計(jì)數(shù)：數(shù)組counter[i]用來表示該位是i的數(shù)的個(gè)數(shù) int[] counter = new int[radix]; // 將array中元素分布填充到bucket中，并進(jìn)行計(jì)數(shù) for (int i = 0; i < array.length; i++) { int which = (array[i] / temp) % radix; bucket[which][counter[which]] = array[i]; counter[which]++; } int index = 0; // 根據(jù)bucket中收集到的array中的元素，根據(jù)統(tǒng)計(jì)計(jì)數(shù)，在array中重新排列 for (int i = 0; i < radix; i++) { if (counter[i] != 0) for (int j = 0; j < counter[i]; j++) { array[index] = bucket[i][j]; index++; } counter[i] = 0; } temp *= radix; round++; } } private int getDistance(int[] array) { int max = computeMax(array); int digits = 0; int temp = max / radix; while(temp != 0) { digits++; temp = temp / radix; } return digits + 1; } private int computeMax(int[] array) { int max = array[0]; for(int i=1; i<array.length; i++) { if(array[i]>max) { max = array[i]; } } return max; } }排序過程
假設(shè)待排序數(shù)組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數(shù)組大小為20，我們以該數(shù)組為例，最大的數(shù)組元素的位數(shù)為2，所以需要進(jìn)行2輪映射（映射到對(duì)應(yīng)的桶中），執(zhí)行基數(shù)排序的具體過程，如下所示：
數(shù)組原始順序數(shù)組的原始順序，如下圖所示：
數(shù)組中存在的相同的元素（同一個(gè)待排序的數(shù)字出現(xiàn)大于1次），我們使用不同的背景顏色來區(qū)分（紅色背景表示第二次出現(xiàn)，靛青色表示第三次出現(xiàn)），如果一個(gè)元素只出現(xiàn)過一次，則我們就使用一種固定的顏色（淺綠色）表示。
根據(jù)數(shù)組元素個(gè)位數(shù)字將數(shù)組中元素映射到對(duì)應(yīng)的桶中（bucket）
我們使用的是十進(jìn)制，基數(shù)（Radix）自然是10，根據(jù)數(shù)組元素個(gè)位數(shù)的，應(yīng)該映射到10個(gè)桶中，映射后的結(jié)果，如圖所示：
在映射到桶的過程中，從左到右掃描原始數(shù)組。因?yàn)橛成涞酵粋€(gè)桶中的元素可能存在多個(gè)，最多為整個(gè)數(shù)組的長度，所以在同一個(gè)桶中，要保持進(jìn)入桶中的元素的先后順序（先進(jìn)的排在左側(cè)，后進(jìn)的排在右側(cè)）。
掃面前面已經(jīng)映射到各個(gè)桶中的元素，滿足這樣的順序：先掃描編號(hào)最小的桶，桶中如果存在多個(gè)元素，必須按照從左到右的順序。這樣，將得到的數(shù)組元素重新分布，得到一個(gè)元素位置重新分布的數(shù)組，如圖所示：
這時(shí)，可以看到元素實(shí)際上是按照個(gè)位的數(shù)字進(jìn)行了排序，但是基于整個(gè)元素來說并不是有序的。
這次映射的原則和過程，與前面類似，不同的是，這次掃描的數(shù)組是經(jīng)過個(gè)位數(shù)字處理重新分布后的新數(shù)組，映射后桶內(nèi)的狀態(tài)，如圖所示：
和前面收集方法類似，得到的數(shù)組及其順序，如圖所示：
我們可以看到，經(jīng)過兩輪映射和收集過程，數(shù)組已經(jīng)變成有序了，排序結(jié)束。
算法分析
時(shí)間復(fù)雜度設(shè)待排序的數(shù)組R[1..n]，數(shù)組中最大的數(shù)是d位數(shù)，基數(shù)為r（如基數(shù)為10，即10進(jìn)制，最大有10種可能，即最多需要10個(gè)桶來映射數(shù)組元素）。處理一位數(shù)，需要將數(shù)組元素映射到r個(gè)桶中，映射完成后還需要收集，相當(dāng)于遍歷數(shù)組一遍，最多元素書為n，則時(shí)間復(fù)雜度為O(n+r)。所以，總的時(shí)間復(fù)雜度為O(d*(n+r))。
空間復(fù)雜度設(shè)待排序的數(shù)組R[1..n]，數(shù)組中最大的數(shù)是d位數(shù)，基數(shù)為r。基數(shù)排序過程中，用到一個(gè)計(jì)數(shù)器數(shù)組，長度為r，還用到一個(gè)r*n的二位數(shù)組來做為桶，所以空間復(fù)雜度為O(r*n)。
排序穩(wěn)定性通過上面的排序過程，我們可以看到，每一輪映射和收集操作，都保持從左到右的順序進(jìn)行，如果出現(xiàn)相同的元素，則保持他們在原始數(shù)組中的順序。
可見，基數(shù)排序是一種穩(wěn)定的排序。
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
