高位優(yōu)先的字符串排序
要實(shí)現(xiàn)一個(gè)通用的字符串排序算法（字符串的長度不一定相同），我們應(yīng)當(dāng)考慮從左向右遍歷所有字符。顯然，以a開頭的字符串應(yīng)當(dāng)放在以b開頭的字符串之前。實(shí)現(xiàn)這種思想的一個(gè)很自然的方法就是遞歸算法，被稱為高位優(yōu)先的字符串排序。首先用鍵索引計(jì)數(shù)法將所有字符串按照首字母排序，然后遞歸的將所有首字母對(duì)應(yīng)的子數(shù)組排序。和快速排序一樣，高位優(yōu)先的字符串排序會(huì)將數(shù)組切分為能夠獨(dú)立排序的子數(shù)組來完成排序任務(wù)，但它的切分會(huì)為每個(gè)首字母得到一個(gè)子數(shù)組，而不是像快速排序那樣產(chǎn)生固定的兩個(gè)或三個(gè)切分。
在高位優(yōu)先的字符串排序算法中，要特別注意到達(dá)字符串末尾的情況。在排序中，合理的做法是將所有的字符都已被檢查過的字符串排在所有的子數(shù)組前面，這樣就不需要遞歸的將該子數(shù)組排序。我們使用一個(gè)接收兩個(gè)參數(shù)的私有方法toChar()來將字符串中的字符索引轉(zhuǎn)化為數(shù)組索引，當(dāng)指定的位置超過了字符串的末尾時(shí)該方法返回-1。然后將所有的返回值加1，得到一個(gè)非負(fù)的int值并用它作為count的索引。這種轉(zhuǎn)換意味著字符串中每個(gè)字符都可能產(chǎn)生R+1種不同的值：0表示字符串的結(jié)尾，1表示字符串的第一個(gè)字符，以此類推。因?yàn)殒I索引計(jì)數(shù)法本來就需要一個(gè)額外的位置，所以使用代碼int count[] = new int[R+2];創(chuàng)建記錄統(tǒng)計(jì)頻率的數(shù)組。

public class MSD{
    private static int R = 256;              //基數(shù)
    private static final int M = 15;        //小數(shù)組的切換閾值
    private static String[] aux;              //數(shù)組分類的輔助數(shù)組
    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);
    }
    private static void sort(String[] a, int lo, int hi, int d){
        if( hi <= lo+M)
            Insertion.sort(a, lo, hi, d);  return;
        int[] count = new int[R+2];            //計(jì)算頻率
        for(int i=lo; i<=hi; i++)
            count[charAt(a[i], d) +2]++;
        for(int r = 0; r<R; r++)              
            count[r+1] += count[r];              //將頻率轉(zhuǎn)換為索引
        for(int i = lo; i<=hi; i++){
            aux[count[charAt(a[i],d) +1]++] = a[i];      //數(shù)據(jù)分類
        for( int i=lo; i<=hi; i++){
            a[i] = aux[i-lo];                    //回寫
        for( int r =0; r<R; r++)
            sort(a, lo+count[r], lo+count+count[r+1]-1, d+1);
    }
}

三向字符串快速排序
我們也可以根據(jù)高位優(yōu)先的字符串排序算法改進(jìn)快速排序，根據(jù)鍵的首字母進(jìn)行三向切分，僅在中間子數(shù)組的下一個(gè)字符（因?yàn)殒I的首字母與切分字符相等）繼續(xù)遞歸排序。
三向字符串快速排序只會(huì)將數(shù)組分為三部分，因此當(dāng)相應(yīng)的高位優(yōu)先的字符串排序產(chǎn)生的非空切分較多時(shí)，它需要移動(dòng)的數(shù)據(jù)量就非常巨大，因?yàn)樗枰M(jìn)行一系列的三向切分才會(huì)獲得多向切分的效果。但是，高位優(yōu)先的字符串排序可能會(huì)產(chǎn)生大量（空）子數(shù)組，而三向字符串快速排序的切分總是三個(gè)。因此三項(xiàng)字符串快速排序能很好地處理等值鍵，有較長公共前綴的鍵和取值范圍較小的鍵和小數(shù)組。

puprivateblic 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;
        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++;
        }
        sort(a, lo, lt-1, d);
        if( v >= 0) sort(a, lt, gt, d+1);
        sort(a, gt+1, hi, d);
    }
}