高位優(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);
}
}