摘要：區(qū)別把數(shù)字對(duì)應(yīng)成字符。這個(gè)是字符串的第位。稍作修改可適應(yīng)不等長(zhǎng)的字符串。因此增加一個(gè)組別，記錄字符為空的頻次。

Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin Wayne
Translated By 謝路云
Chapter 5 Section 1 字符串排序

參考資料
http://blog.csdn.net/guanhang...

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

怎么辦呢？把每一個(gè)字符對(duì)應(yīng)成一個(gè)數(shù)字 toIndex(c)

一共有多少個(gè)字符？ R個(gè)

數(shù)字R需要幾個(gè)二進(jìn)制位來表示？ lgR個(gè)

如擴(kuò)展ASCII碼共256個(gè)字符，需要8位二進(jìn)數(shù)來表示。

區(qū)別

Alphabet.toChar(index) 把數(shù)字對(duì)應(yīng)成字符。這個(gè)是字母表的第i位

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

輸入字符串和字符串對(duì)應(yīng)的組別（組別也是字符串的鍵）
在滿足組別有小到大排序的情況下，將字符串按字母順序排序

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

共 5 組，從第 0 組到第 4 組。 創(chuàng)建數(shù)組大小為 6（ = 5 + 1 ）。int[] count=new count[6];

count[]記錄頻率

記錄的位置是鍵值+1，加1是方便后期更新鍵的位置起點(diǎn)

第二步，轉(zhuǎn)化為索引
（得到每個(gè)組別的位置起點(diǎn)）

第三步，分類

創(chuàng)建一個(gè)副本（因?yàn)樵诒闅v正本，正本當(dāng)前不能被覆蓋）

按組別 丟進(jìn)副本里，丟到該組別的位置起點(diǎn)處

當(dāng)前的數(shù)據(jù)是有序的

下面是個(gè)人的小思考，可不用看

如果原先的數(shù)據(jù)是有序的，那么在每個(gè)組別中的數(shù)據(jù)也將會(huì)是有序的

如果原先的數(shù)據(jù)是無序的，那么先排序

有種遞歸的思想

外面先排好序，里面一層一層的去排序

里面先排好序，外面一層一層的去排序

該組別的位置起點(diǎn) 向后挪一位 （因?yàn)楫?dāng)前位被用了）

第四步，復(fù)制

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

復(fù)雜度

訪問數(shù)組11N+4R+1次

索引計(jì)數(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
低位優(yōu)先排序

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

以下代碼的局限性：每個(gè)字符串的長(zhǎng)度是相等的。稍作修改可適應(yīng)不等長(zhǎ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)先排序
考慮不等長(zhǎng)字符串的比較

e.g. as 排在 aspect 前面。因此增加一個(gè)組別，記錄字符為空的頻次。


這個(gè)組別應(yīng)該在最前面，為count[0]

怎么讓字符為空落到count[0]里呢？

字符為空時(shí)，對(duì)應(yīng)數(shù)字為0（具體實(shí)現(xiàn)的時(shí)候?yàn)榉祷?1，再在-1的基礎(chǔ)上+1）

其他字符對(duì)應(yīng)的數(shù)字在原來基礎(chǔ)上+1（就是給0騰個(gè)位置出來，不占用0，所有位次順移）




int[] count=new int[R+2];

原為R+1

再在原來的基礎(chǔ)上+1，即為R+2



字符為空，也即搜尋的時(shí)候超出字符串的原來長(zhǎng)度


MSD 代碼
public class MSD {
    private static int R = 256; // radix 256個(gè)字符
    private static final int M = 15; // cutoff for small subarrays 數(shù)組小到多少的時(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ù)組較小，插入排序，具體實(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.頻次，只累計(jì)了hi-lo+1次
            count[charAt(a[i], d) + 2]++; // 每個(gè)對(duì)應(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.丟到對(duì)應(yīng)組別里去
            aux[count[charAt(a[i], d) + 1]++] = a[i]; // 每個(gè)對(duì)應(yīng)數(shù)字在原來基礎(chǔ)上+1
                                                      // aux的賦值從aux[0]開始，到aux[hi-lo]結(jié)束
                                                      // 在這里count會(huì)發(fā)生變化。原來這里的count只是為了移動(dòng)到下一位為下一個(gè)元素找位置用，現(xiàn)在這里的count[i]還可以通過是否到達(dá)count[i+1]來判斷是否可以結(jié)束遞歸
        for (int i = lo; i <= hi; i++) // Copy back. 注意aux的起終點(diǎn)和a的對(duì)應(yīng)關(guān)系
            a[i] = aux[i - lo];
        // Recursively sort for each character value.
        for (int r = 0; r < R; r++) //私認(rèn)為初始化條件r=1更好，因?yàn)閞=0都是字符為空的子字符串
            sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1); // 將當(dāng)前相同字符的分為一組，每組以下一位字符為比較對(duì)象排序
    }
}


LSD
從右到左，每次都是N個(gè)字符作為一組，整體進(jìn)行排序



MSD
從從到右，每次是第i位相同的字符串分成一組，按第i+1位排序



三向字符串快速排序

可以處理等值鍵，較長(zhǎng)公共前綴，小數(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; // 從第二個(gè)字符串的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);
    }
}