引入

• 字符串方便比較嗎？不方便

• 怎么辦呢？把每一個字符對應(yīng)成一個數(shù)字 toIndex(

c)

• 一共有多少個字符？ R個

• 數(shù)字R需要幾個二進制位來表示？ lgR個
  如擴展ASCII碼共256個字符，需要8位二進數(shù)來表示。

• 區(qū)別
  Alphabet.toChar(index) 把數(shù)字對應(yīng)成字符。這個是字母表的第i位

  String.charAt(index) 字符串的第i位是什么字符。這個是字符串的第i位。 字符表API

  
  
  在這里插入圖片描述

標準字符表

在這里插入圖片描述

鍵索引計數(shù)

輸入字符串和字符串對應(yīng)的組別（組別也是字符串的鍵）
在滿足組別有小到大排序的情況下，將字符串按字母順序排序
[圖片上傳失敗...(image-24066d-1600017488526)]

算法步驟

第一步，記錄組別的頻率
（為了得到某個字符串在排序后的范圍，比如組別2肯定在組別1后面，在組別3前面，把每個組別有多少個人記錄下來，方便我們定位）

• 共 5 組，從第 0 組到第 4 組。 創(chuàng)建數(shù)組大小為 6（ = 5 + 1 ）。int[] count=new count[6];
• count[]記錄頻率
• 記錄的位置是鍵值+1，加1是方便后期更新鍵的位置起點
  [圖片上傳失敗...(image-70a43b-1600017488526)]
  第二步，轉(zhuǎn)化為索引
  （得到每個組別的位置起點）
  [圖片上傳失敗...(image-56fc38-1600017488526)]

第三步，分類

• 創(chuàng)建一個副本（因為在遍歷正本，正本當前不能被覆蓋）
• 按組別 丟進副本里，丟到該組別的位置起點處
  • 當前的數(shù)據(jù)是有序的
  • 下面是個人的小思考，可不用看
  • 如果原先的數(shù)據(jù)是有序的，那么在每個組別中的數(shù)據(jù)也將會是有序的
  • 如果原先的數(shù)據(jù)是無序的，那么先排序
  • 有種遞歸的思想
    • 外面先排好序，里面一層一層的去排序
    • 里面先排好序，外面一層一層的去排序
• 該組別的位置起點 向后挪一位 （因為當前位被用了）

第四步，復(fù)制

• 把副本的數(shù)據(jù)拷貝回正本

  
  
  在這里插入圖片描述

KeyIndexedCounting 代碼

• 復(fù)雜度
  • 訪問數(shù)組11N+4R+1次
• 索引計數(shù)法是穩(wěn)定的

int N = a.length;
String[] aux = new String[N]; //訪問數(shù)組N次
int[] count = new int[R+1]; //訪問數(shù)組R+1次
// Compute frequency counts.
for(int i = 0;i<N;i++) //訪問數(shù)組2N次
    count[a[i].key()+1]++;
// Transform counts to indices.
for(int r = 0;r<R;r++) //訪問數(shù)組2R次，進行R次加法
    count[r+1]+=count[r];
// Distribute the records.
for(int i = 0;i<N;i++) //訪問數(shù)組3N次，使計數(shù)器值增大N次并移動數(shù)據(jù)N次
    aux[count[a[i].key()]++]=a[i];
// Copy back.
for(int i = 0;i<N;i++) //訪問數(shù)組2N次，移動數(shù)據(jù)N次
    a[i]=aux[i];

低位優(yōu)先排序

結(jié)合索引排序，從字符串的低位（從右面開始），從右到左，每個字符都當一次該字符串的鍵，給整個字符串排序

以下代碼的局限性：每個字符串的長度是相等的。稍作修改可適應(yīng)不等長的字符串。

LSD 代碼

• 復(fù)雜度
  • 訪問數(shù)組
    • 最壞情況：~7WN + 3WR 次
    • 最好情況：8N+3R 次
  • 空間： R+N

public class LSD {
    public static void sort(String[] a, int W) { // Sort a[] on leading W characters.
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
        for (int d = W - 1; d >= 0; d--) { // Sort by key-indexed counting on dth char.
            int[] count = new int[R + 1];  // 創(chuàng)建數(shù)組大小為R+1
            for (int i = 0; i < N; i++) // Compute frequency counts. 頻率
                count[a[i].charAt(d) + 1]++;
            for (int r = 0; r < R; r++) // Transform counts to indices. 索引
                count[r + 1] += count[r];
            for (int i = 0; i < N; i++) // Distribute. 按組別丟到副本里去
                aux[count[a[i].charAt(d)]++] = a[i];
            for (int i = 0; i < N; i++) // Copy back. 賦回正本
                a[i] = aux[i];
        }
    }
}

高位優(yōu)先排序

考慮不等長字符串的比較

• e.g. as 排在 aspect 前面。因此增加一個組別，記錄字符為空的頻次。
• 這個組別應(yīng)該在最前面，為count[0]
  - 怎么讓字符為空落到count[0]里呢？
  - 字符為空時，對應(yīng)數(shù)字為0（具體實現(xiàn)的時候為返回-1，再在-1的基礎(chǔ)上+1）
  - 其他字符對應(yīng)的數(shù)字在原來基礎(chǔ)上+1（就是給0騰個位置出來，不占用0，所有位次順移）
• int[] count=new int[R+2];
  - 原為R+1
  - 再在原來的基礎(chǔ)上+1，即為R+2
• 字符為空，也即搜尋的時候超出字符串的原來長度

MSD 代碼

public class MSD {
    private static int R = 256; // radix 256個字符
    private static final int M = 15; // cutoff for small subarrays 數(shù)組小到多少的時候用插入排序？
    private static String[] aux; // auxiliary array for distribution 副本
 
    private static int charAt(String s, int d) {
        if (d < s.length())
            return s.charAt(d);
        else
            return -1;
    }
 
    public static void sort(String[] a) {
        int N = a.length;
        aux = new String[N];
        sort(a, 0, N - 1, 0);
    }
 
    // Sort from a[lo] to a[hi], starting at the dth character.
    private static void sort(String[] a, int lo, int hi, int d) { 
        //如果數(shù)組較小，插入排序，具體實現(xiàn)略
        if (hi <= lo + M) {
            Insertion.sort(a, lo, hi, d);
            return;
        }
        
        int[] count = new int[R + 2]; // 數(shù)組大小R+2
        for (int i = lo; i <= hi; i++)// Compute frequency counts.頻次，只累計了hi-lo+1次
            count[charAt(a[i], d) + 2]++; // 每個對應(yīng)數(shù)字在原來基礎(chǔ)上+1
        for (int r = 0; r < R + 1; r++) // Transform counts to indices. 索引
            count[r + 1] += count[r];
        for (int i = lo; i <= hi; i++) // Distribute.丟到對應(yīng)組別里去
            aux[count[charAt(a[i], d) + 1]++] = a[i]; // 每個對應(yīng)數(shù)字在原來基礎(chǔ)上+1
                                                      // aux的賦值從aux[0]開始，到aux[hi-lo]結(jié)束
                                                      // 在這里count會發(fā)生變化。原來這里的count只是為了移動到下一位為下一個元素找位置用，現(xiàn)在這里的count[i]還可以通過是否到達count[i+1]來判斷是否可以結(jié)束遞歸
        for (int i = lo; i <= hi; i++) // Copy back. 注意aux的起終點和a的對應(yīng)關(guān)系
            a[i] = aux[i - lo];
        // Recursively sort for each character value.
        for (int r = 0; r < R; r++) //私認為初始化條件r=1更好，因為r=0都是字符為空的子字符串
            sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1); // 將當前相同字符的分為一組，每組以下一位字符為比較對象排序
    }
}

• LSD
  • 從右到左，每次都是N個字符作為一組，整體進行排序
• MSD
  • 從從到右，每次是第i位相同的字符串分成一組，按第i+1位排序

三向字符串快速排序

• 可以處理等值鍵，較長公共前綴，小數(shù)組，取值范圍較小的鍵
• 避免創(chuàng)建大量空數(shù)組，不需要額外空間

Quick3string 代碼

• 復(fù)雜度
  • 平均： 2NlnN

public class Quick3string {
    private static int charAt(String s, int d) {
        if (d < s.length())
            return s.charAt(d);
        else
            return -1;
    }
 
    public static void sort(String[] a) {
        sort(a, 0, a.length - 1, 0);
    }
 
    private static void sort(String[] a, int lo, int hi, int d) {
        if (hi <= lo)
            return;
        int lt = lo, gt = hi; // 低位指針，高位指針
        int v = charAt(a[lo], d); // 切分值
        int i = lo + 1; // 從第二個字符串的d位開始
        while (i <= gt) {
            int t = charAt(a[i], d);
            if (t < v) // 比切分值小，放到切分值前面去
                exch(a, lt++, i++);
            else if (t > v) // 比切分值大，放到最后去
                exch(a, i, gt--);
            else
                i++;
        }
 
        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]
        sort(a, lo, lt - 1, d);
        if (v >= 0) // d位字母相同且不為空，則這部分從下一位開始再比較
            sort(a, lt, gt, d + 1);
        sort(a, gt + 1, hi, d);
    }
}