Java排序算法總結(jié)（八）：基數(shù)排序
基數(shù)排序(radix sort）則是屬于“分配式排序”（distribution sort），基數(shù)排序法又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過(guò)鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的比較性排序法。
效率分析：
時(shí)間效率：設(shè)待排序列為n個(gè)記錄，d個(gè)關(guān)鍵碼，關(guān)鍵碼的取值范圍為radix，則進(jìn)行鏈?zhǔn)交鶖?shù)排序的時(shí)間復(fù)雜度為O(d(n+radix))，其中，一趟分配時(shí)間復(fù)雜度為O(n)，一趟收集時(shí)間復(fù)雜度為O(n)，共進(jìn)行d趟分配和收集。 空間效率：需要2*radix個(gè)指向隊(duì)列的輔助空間，以及用于靜態(tài)鏈表的n個(gè)指針。
實(shí)現(xiàn)方法：
最高位優(yōu)先(Most Significant Digit first)法，簡(jiǎn)稱MSD法：先按k1排序分組，同一組中記錄，關(guān)鍵碼k1相等，再對(duì)各組按k2排序分成子組，之后，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對(duì)各子組排序后。再將各組連接起來(lái)，便得到一個(gè)有序序列。 最低位優(yōu)先(Least Significant Digit first)法，簡(jiǎn)稱LSD法：先從kd開(kāi)始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到對(duì)k1排序后便得到一個(gè)有序序列。
代碼實(shí)現(xiàn)：
- public class RadixSort {
- public static void sort(int[] number, int d) {
- int k=0;
- int n=1;
- int m=1;
- int[][] temp = new int[number.length][number.length];
- int[] order = new int[number.length];
- while(m <= d) {
- for(int i = 0; i < number.length; i++) {
- int lsd = ((number[i] / n) % 10);
- temp[lsd][order[lsd]] = number[i];
- order[lsd]++;
- }
- for(int i = 0; i < d; i++) {
- if(order[i] != 0)
- for(int j = 0; j < order[i]; j++) {
- number[k] = temp[i][j];
- k++;
- }
- order[i] = 0;
- }
- n *= 10;
- k = 0;
- m++;
- }
- }
- public static void main(String[] args) {
- int[] data =
- {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
- RadixSort.sort(data, 10);
- for(int i = 0; i < data.length; i++) {
- System.out.print(data[i] + " ");
- }
- }
基數(shù)排序一般僅是用于記錄的關(guān)鍵字為整數(shù)類型的情況。
在已介紹的各種內(nèi)部排序方法中，就所需要的計(jì)算時(shí)間來(lái)看，快速排序、歸并排序、堆排序是很好的方法。但是，歸并排序需要大小為n的輔助空間，快速排序需要一個(gè)棧。除了快速排序、堆排序、選擇排序、希爾排序不穩(wěn)定外，其它排序方法都是穩(wěn)定的。
評(píng)價(jià)一個(gè)排序算法性能好壞的主要標(biāo)準(zhǔn)是它所需的計(jì)算時(shí)間和存儲(chǔ)空間。影響計(jì)算時(shí)間的兩個(gè)重要因素是比較關(guān)鍵字的次數(shù)和記錄的移動(dòng)次數(shù)。在實(shí)際應(yīng)用中，究竟應(yīng)該選用何種排序方法，取決于具體的應(yīng)用和機(jī)器條件。
【編輯推薦】
