鍵索引計(jì)數(shù)法
鍵索引計(jì)數(shù)法是一種適用于整數(shù)鍵的簡(jiǎn)單排序方法。為了說明這種方法，假設(shè)數(shù)組a[]中的每個(gè)元素都保存了一個(gè)名字和一個(gè)鍵值，其中鍵值在0~R-1之間，代碼a[i].key()會(huì)返回指定的鍵值。方法可簡(jiǎn)單分為4個(gè)步驟：
1.頻率統(tǒng)計(jì)
第一步通過int數(shù)組count[]計(jì)算每個(gè)鍵出現(xiàn)的頻率。對(duì)于數(shù)組中的每個(gè)元素，都使用它的鍵訪問count[]中的相應(yīng)元素并將其加1.如果鍵為r，則將count[r+1]加1.

for(i=0; i<N; i++)
    count[a[i].key() + 1]++;

2.將頻率轉(zhuǎn)換為索引
使用count[]來計(jì)算每個(gè)鍵在排序結(jié)果中的起始索引位置。一般來說，任意給定的鍵的起始索引均為所有較小的鍵的對(duì)應(yīng)的頻率之和。對(duì)于每個(gè)鍵值r，小于r+1的鍵的頻率之和為小于r的頻率之和再加上count[r]。

for(int r=0; r<R; r++)
    count[r+1] += count[r];

3.在將count[]數(shù)組轉(zhuǎn)換為一張索引表之后，將所有的元素移動(dòng)到一個(gè)輔助數(shù)組aux[]中以進(jìn)行排序。每個(gè)元素在aux[]中的位置由它的鍵的count[]值決定，在移動(dòng)之和將count中對(duì)應(yīng)的元素加1，以保證count[r]總是下一個(gè)鍵r的元素在aux中的索引。

for( int i=0; i<N; i++)
    aux[count[a[i].key()]++] = a[i];

4.回寫
我們?cè)趯⒃匾苿?dòng)到輔助數(shù)組的過程中完成了排序，所以最后一步就是將排序的結(jié)果復(fù)制回原數(shù)組中。

鍵值索引法排序N個(gè)鍵為0到R-1之間的整數(shù)的元素需要訪問數(shù)組11N+4R+1次。

低位優(yōu)先的字符串排序
如果字符串的長(zhǎng)度均為W，那就從右向左以每個(gè)位置的字符作為鍵，用建索引計(jì)數(shù)的方法將字符串排序W遍。

public class LSD{
    public static void sort(String[] a, int w){
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
        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];
        }
    }
}

對(duì)于基于R個(gè)字符的字母表的N個(gè)以長(zhǎng)為W的字符串為鍵的元素，低位優(yōu)先的字符串排序需要訪問~7WN+3WR次數(shù)組，使用的e'a