引入

字符串方便比較嗎任柜？不方便
怎么辦呢？把每一個字符對應成一個數(shù)字 toIndex(

一共有多少個字符？ R個

數(shù)字R需要幾個二進制位來表示？ lgR個
如擴展ASCII碼共256個字符板壮，需要8位二進數(shù)來表示。
區(qū)別
Alphabet.toChar(index) 把數(shù)字對應成字符合住。這個是字母表的第i位

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

在這里插入圖片描述

標準字符表

在這里插入圖片描述

鍵索引計數(shù)

輸入字符串和字符串對應的組別（組別也是字符串的鍵）
在滿足組別有小到大排序的情況下透葛，將字符串按字母順序排序
[圖片上傳失敗...(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)]
第二步爱致，轉化為索引
（得到每個組別的位置起點）
[圖片上傳失敗...(image-56fc38-1600017488526)]

第三步，分類

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

第四步纫普，復制

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

在這里插入圖片描述

KeyIndexedCounting 代碼

復雜度
- 訪問數(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)先排序

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

以下代碼的局限性：每個字符串的長度是相等的霍掺。稍作修改可適應不等長的字符串匾荆。

LSD 代碼

復雜度
- 訪問數(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 前面。因此增加一個組別杆烁，記錄字符為空的頻次牙丽。
這個組別應該在最前面，為count[0]
- 怎么讓字符為空落到count[0]里呢兔魂？
- 字符為空時烤芦，對應數(shù)字為0（具體實現(xiàn)的時候為返回-1，再在-1的基礎上+1）
- 其他字符對應的數(shù)字在原來基礎上+1（就是給0騰個位置出來析校，不占用0拍棕，所有位次順移）
int[] count=new int[R+2];
- 原為R+1
- 再在原來的基礎上+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]++; // 每個對應數(shù)字在原來基礎上+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.丟到對應組別里去
            aux[count[charAt(a[i], d) + 1]++] = a[i]; // 每個對應數(shù)字在原來基礎上+1
                                                      // aux的賦值從aux[0]開始，到aux[hi-lo]結束
                                                      // 在這里count會發(fā)生變化事甜。原來這里的count只是為了移動到下一位為下一個元素找位置用谬泌，現(xiàn)在這里的count[i]還可以通過是否到達count[i+1]來判斷是否可以結束遞歸
        for (int i = lo; i <= hi; i++) // Copy back. 注意aux的起終點和a的對應關系
            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 代碼

復雜度
- 平均： 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);
    }
}

《算法》-字符串[字符串排序]