程式扎記: [ Algorithm in Java ] 排序 : 基數排序法

標籤

2011年10月26日 星期三

[ Algorithm in Java ] 排序 : 基數排序法


轉載自 這裡
前言 :
在之前所介紹過的排序方法,都是屬於「比較性」的排序法,也就是每次排序時 ,都是比較整個鍵值的大小以進行排序. 這邊所要介紹的「基數排序法」(radix sort)則是屬於「分配式排序」(distribution sort),基數排序法會使用到「桶子」(bucket),顧名思義,它是透過鍵值的部份資訊,將要排序的元素分配至某些「桶」中,藉以達到排序的作用,基數排序法是屬於穩定性的排序,其時間複雜度為 O(nlog(r)m),其中r為所採取的基數,而m為堆數,在某些時候,基數排序法的效率高於其它的比較性排序法!

解法 :
基數排序的方式可以採用LSD(Least sgnificant digital)或MSD(Most sgnificant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始. 以LSD為例,假設原來有一串數值如下所示 :
73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根據個位數的數值,在走訪數值時將它們分配至編號0到9的桶子中 :


接下來將這些桶子中的數值重新串接起來,成為以下的數列 :
81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接著再進行一次分配,這次是根據十位數來分配 :


接下來將這些桶子中的數值重新串接起來,成為以下的數列 :
14, 22, 28, 39, 43, 55, 65, 73, 81, 93

這時候整個數列已經排序完畢;如果排序的對象有三位數以上,則持續進行以上的動作直至最高位數為止. LSD的基數排序適用於位數小的數列,如果位數多的話,使用MSD的效率會比較好,MSD的方式恰與LSD相反,是由高位數為基底開始進行分配,其他的演 算方式則都相同.

實作 :
- RadixSort.java :
  1. package alg.sort;  
  2.   
  3. public class RadixSort {  
  4.     private static int[][] bucks;  
  5.     private static int[] index = new int[10];  
  6.       
  7.     /** 
  8.      * BD : Sort number with radix sort algorithm. 
  9.      * @param number  
  10.      *      The matrix to be sorted 
  11.      * @param n 
  12.      *      The max figure of all elements in matrix number.  
  13.      */  
  14.     public static void sort(int[] number, int n)  
  15.     {  
  16.         bucks = new int[10][number.length];  
  17.           
  18.         int rdx = 0;  
  19.         int rst = 0;  
  20.         for(int i=0; i
  21.         {  
  22.             /*Put into bucks*/  
  23.             for(int j=0; j
  24.             {  
  25.                 if(i==0) rst = number[j]%10;  
  26.                 else  
  27.                 {  
  28.                     rdx = (int)Math.pow(10, i);  
  29.                     rst = (number[j]/rdx)%10;  
  30.                 }  
  31.                 bucks[rst][index[rst]++] = number[j];  
  32.             }  
  33.             /*Restore from bucks*/  
  34.             int p=0;  
  35.             for(int j=0; j<10; j++)  
  36.             {  
  37.                 for(int k=0; k
  38.                 {  
  39.                     System.out.printf("\t[Restore from bucks] number[%d]=%d...\n", p, bucks[j][k]);  
  40.                     number[p++]=bucks[j][k];  
  41.                 }  
  42.                 index[j]=0;  
  43.             }  
  44.             System.out.println();  
  45.         }  
  46.     }  
  47.       
  48.     public static void main(String args[])  
  49.     {  
  50.         int numbers[] = {73229343551428653981};  
  51.         RadixSort.sort(numbers, 2);  
  52.         for(int i=0; i" ");  
  53.     }  
  54. }  

補充說明 :
[ Data Structures with Java ] Section 15.2 : The Radix Sort
The method, called the radix sort, is a linear algorithm that uses successive digits in the elements to partially sort the array. The technique is two-stage process refereed to as transform-and-conquer...
This message was edited 6 times. Last update was at 27/10/2011 10:27:31

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!