鍵索引排序法

鍵索引排序法主要用來解決分組排序的問題。
例如：
一個(gè)班級(jí)有分為三個(gè)組，每個(gè)組編號(hào)1~3。

需要對(duì)以上學(xué)生按照分組來排序，預(yù)期結(jié)果如下。

Harry Draco Hermione Diamond Steve

這種場景之下可以使用鍵索引排序法來實(shí)現(xiàn)。

int N = a.length
String[] aux = new String[N];
int[] count = new int[R+1];

//對(duì)數(shù)據(jù)做頻率統(tǒng)計(jì),a[i].key()為組數(shù)，count是頻率統(tǒng)計(jì)的容器
for(int  i=0;i<N;i++)
  count[a[i].key()+1]++;
//頻率轉(zhuǎn)換為索引
for(int r = 0;r<R;r++)
count[r+1] += count[r]
//元素分類即排序
for(int i=0;i<N;i++)
aux[count[a[i].key]++] = a[i];

該算法的時(shí)間復(fù)雜度是O(N+R)，一般情況下N>>R，可以看做是O(N)的復(fù)雜度。頻率轉(zhuǎn)換為索引是理解該算法的關(guān)鍵之處，我們可以這樣來看待這個(gè)問題，假設(shè)有一個(gè)hashmap對(duì)于碰撞的處理是簡單插入到散列后的隊(duì)列之后，key為組別而value是姓名，那么我們讀取原始數(shù)據(jù)并根據(jù)組別插入hashmap，發(fā)生碰撞之后連接到尾部。最后從hashmap中按照組別順序?qū)?shù)據(jù)取出來，這就是一個(gè)索引排序?，F(xiàn)在我們統(tǒng)計(jì)每一個(gè)組別中數(shù)據(jù)的數(shù)量，并為此劃分了空間大小（其實(shí)這變相的指定了每個(gè)組別的存放位置），將同組別的直接插入到相應(yīng)位置，使用數(shù)組下標(biāo)作為一個(gè)“哈希散列值”，更方便并且更有效率，這其實(shí)是整個(gè)算法的核心：頻率轉(zhuǎn)換為索引。

低位優(yōu)先的字符串排序

索引排序的一個(gè)應(yīng)用是低位優(yōu)先的字符串排序。低位優(yōu)先字符串排序針對(duì)的是等長的字符串?dāng)?shù)據(jù)的排序，該算法的思路是將ASCII碼中一共256個(gè)值作為分組的依據(jù)，字符串從后向前對(duì)每一位做鍵索引排序。

public class TangLSD {
    public static void sort(String[] a, int W){
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
       //以下為對(duì)字符串從后向前每一個(gè)字符做索引排序
       for(int i=W-1;i>=0;i--){
           int[] count = new int[R+1];
           for(int j=0;j<N;j++){
               count[a[j].charAt(i)+1] ++;
           }
           //頻率轉(zhuǎn)換為索引
           for(int j=0;j<R;j++){
               count[j+1] += count[j];
           }
          //索引處填入字符串
           for(int j=0;j<N;j++){
               aux[count[a[j].charAt(i)]++]=a[j];
           }
          //沒做一次索引我們會(huì)重新賦值一次
           for(int j=0;j<N;j++){
               a[j] = aux[j];
           }
       }
    }

    public static void main(String[] args){
        String[] strs = new String[]{"aadf","dvcd","wdsf","sacd","hgin"};
        sort(strs,1);
        for (String str:strs) {
            System.out.println(str);
        }
    }
}

結(jié)果如下

aadf dvcd hgin sacd wdsf

理解了鍵索引排序，低位優(yōu)先的字符串排序理解起來就自然而然了。粗略的看時(shí)間復(fù)雜度是O(WR)+O(WN)，空間復(fù)雜度為R+N。

高位優(yōu)先字符串排序

高位優(yōu)先的排序方法其實(shí)可以看做“分治法”的一種具體實(shí)現(xiàn)，首先用鍵索引排序法對(duì)首字母做排序，按照首字母做劃分，對(duì)于首字母相同的字符串做遞歸排序。