算法小記：低位優先(LSD)

一、思想

此類字符串排序可以通過鍵索引計數法來完成；如果字符串長度均為W，那就從右向左以每個位置的字符作為鍵，用鍵索引方法將字符串排序W遍；

二、代碼

/** 
 * 低位優先的字符串排序 
 *  
 * @author pengcx 
 *  
 */ 
public class LSD { 
    /** 
    * 將字符串數組a中的字符串，按低W位優先字符串排序 
    *  
    * @param a 
    *            字符串數組a 
    * @param W 
    *            第W位 
    */ 
    public static void sort(String[] a, int W) { 
        // 通過前W個字符將a[]排序 
        int N = a.length; 
        int R = 256; 
        String aux[] = new String[N]; 
 
        // 根據從右到左，第d個字符用鍵索引計數法排序W遍 
        for (int d = W - 1; d >= 0; d--) {  
            // 第一步，計算出現的頻率 
            int[] count = new int[R + 1]; 
            for (int i = 0; i < N; i++) { 
                count[a[i].charAt(d) + 1]++; 
            } 
 
            // 第二步，將頻率轉換成索引 
            for (int r = 0; r < R; r++) { 
                count[r + 1] += count[r]; 
            } 
 
             // 第三步，將元素匪類 
            for (int i = 0; i < N; i++) { 
                aux[count[a[i].charAt(d)]++] = a[i]; 
            } 
 
            // 第四步，回寫 
            for (int i = 0; i < N; i++) { 
                a[i] = aux[i]; 
            } 
        } 
    } 
 
    public static void main(String[] args) { 
        String[] a = { "abda", "sdfa", "qweg", "ndpl", "lkiu", "sdud" }; 
        int N = a.length; 
        int W = a[0].length(); 
 
        sort(a, W); 
 
        for (int i = 0; i < N; i++) { 
            System.out.println(a[i]); 
        } 
    } 
}