數(shù)據(jù)結(jié)構(gòu)與算法——字符串排序
對于許多排序應(yīng)用，決定順序的鍵都是字符串拆讯。下面將學(xué)習(xí)專門針對字符串類型的排序方法脂男，這些方法比之前學(xué)習(xí)的通用排序方法（如冒泡、插入种呐、歸并等）更高效宰翅。
第一類方法是低位優(yōu)先（Least-Signifcant-Digit First，LSD）的字符串排序方法爽室。這個算法要求被排序的每個字符串長度都相等汁讼。它會把字符串當(dāng)成數(shù)字，從字符串的右邊開始向左檢查字符（相當(dāng)于從數(shù)字的最低位到高位）阔墩。
第二類方法是高位優(yōu)先（MSD）的字符串排序嘿架。它不要求被排序的字符串等長，而且不一定需要檢查所有的輸入就能完成排序啸箫。該算法將從左開始向右檢查字符（就像通常我們比較字符串那樣）耸彪，使用和快速排序類似的方法將字符串排序。
在學(xué)習(xí)低位優(yōu)先的字符串排序時忘苛，最好先了解下計數(shù)排序和基數(shù)排序蝉娜。上一篇文章中已經(jīng)有詳細(xì)介紹了唱较，這里不再贅述。
低位優(yōu)先的字符串排序LSD
首先待排序的字符串長度均相同召川，設(shè)為W南缓，從右向左以每個字符作為關(guān)鍵字，用計數(shù)排序法將字符串排序W次荧呐。由于計數(shù)排序法是穩(wěn)定的汉形，所以低位優(yōu)先的字符串排序能夠穩(wěn)定地將字符串排序。
假設(shè)你對計數(shù)排序和基數(shù)排序都有一定的了解了坛增，這里直接給出代碼获雕。
package Chap5;
import java.util.Arrays;
public class LSD {
public static void sort(String[] a, int W) {
// 每位數(shù)字范圍0~9，基為10
int R = 256;
int N = a.length;
String[] aux = new String[N];
int[] count = new int[R+1];
// 共需要d輪計數(shù)排序, 從最后一位開始收捣，符合從右到左的順序
for (int d = W - 1; d >= 0; d--) {
// 1. 計算頻率届案，在需要的數(shù)組長度上額外加1
for (int i = 0; i < N; i++) {
// 使用加1后的索引，有重復(fù)的該位置就自增
count[a[i].charAt(d) + 1]++;
}
// 2. 頻率 -> 元素的開始索引
for (int r = 0; r < R; r++) {
count[r + 1] += count[r];
}
// 3. 元素按照開始索引分類罢艾，用到一個和待排數(shù)組一樣大臨時數(shù)組存放數(shù)據(jù)
for (int i = 0; i < N; i++) {
// 填充一個數(shù)據(jù)后楣颠，自增，以便相同的數(shù)據(jù)可以填到下一個空位
aux[count[a[i].charAt(d)]++] = a[i];
}
// 4. 數(shù)據(jù)回寫
for (int i = 0; i < N; i++) {
a[i] = aux[i];
}
// 重置count[]咐蚯，以便下一輪統(tǒng)計使用
for (int i = 0; i < count.length; i++) {
count[i] = 0;
}
}
}
public static void main(String[] args) {
String[] a = {"4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720",
"1OHV845", "1OHV845","2RLA629", "2RLA629", "3ATW723"};
LSD.sort(a, 7);
System.out.println(Arrays.toString(a));
}
}
上面程序?qū)⒋蛴∪缦聝?nèi)容
[1ICK750, 1ICK750, 1OHV845, 1OHV845, 1OHV845, 2IYE230, 2RLA629, 2RLA629, 3ATW723, 3CIO720, 3CIO720, 4JZY524, 4PGC938]
我們來看下對這些字符串排序的LSD軌跡童漩。
為什么從右往左以每一位字符為鍵排序W次就能對字符串排序了呢？試想一種簡單情況：如果有兩個鍵春锋，它們的第0位還沒有被排序且它們相同矫膨，那么字符串中不同的地方就在于已經(jīng)排序的第1位，出于計數(shù)排序的穩(wěn)定性期奔，它們將一直保持有序侧馅；除非未被排序的第1位字符不同，那么已經(jīng)排序過的字符對于兩者的最終順序是沒有意義的呐萌，之后的某輪處理會根據(jù)更高字符的不同修正這對鍵的順序馁痴。比如["SC", "SB", "AD"]，以第1位字符為鍵排序后是["SB", "SC", "AD"]對于"SB"和"SC"它們的第0位還沒有排序且相同肺孤，由于計數(shù)排序的穩(wěn)定罗晕，在這種情況下，它們以第0位排序時會保持有序赠堵；而對于"SB"和"AD"它們的第0位還沒有排序且不同小渊，那么第1位排序的結(jié)果就沒有意義了，因為對第0位排序后變成["AD", "SB", "SC"]茫叭，可以看到原來字符串第1位是BD的順序酬屉，排序后變成DB的順序了。綜上：我們的目的是在較高位字符相同的情況下杂靶，保持著較低位的順序梆惯；在較高位字符不同的情況下，保證較高位要有序吗垮，低位的順序已經(jīng)沒有意義垛吗。
標(biāo)準(zhǔn)的LSD只能處理等長字符串，下面將要學(xué)習(xí)的是通用的字符串排序方法（字符串的長度不一定相同）烁登。首先來看高位優(yōu)先的字符串排序MSD怯屉。
高位優(yōu)先的字符串排序MSD
高位優(yōu)先的字符串排序MSD可以處理不等長的字符串，它是從左向右檢查每個字符饵沧，統(tǒng)計字符串首字母的頻率锨络，并按其來進(jìn)行歸類、排序狼牺，然后對歸類后的字符串：將所有首字母相同的歸為一個子數(shù)組羡儿，遞歸地分別對這些子數(shù)組排序。精煉點說就是：
- 以首字母來排序是钥，將數(shù)組切分成首字母相同的子數(shù)組
- 忽略都相同的首字母掠归，遞歸地排序子數(shù)組
在高位優(yōu)先的字符串排序算法中，要特別注意字符串末尾的情況悄泥。我們需要一個標(biāo)記來判斷是否到達(dá)字符串末尾虏冻，因此在字符集中需要給字符串末尾定義一個位置，而且字符串的末尾應(yīng)該比任何字符都要小弹囚，比如“other”就小于“others”厨相，所以字符串末尾在字符集中對應(yīng)的整數(shù)應(yīng)該最小。于是我們可以改寫String的charAt方法鸥鹉，當(dāng)索引達(dá)到字符串末尾時蛮穿，返回-1。但是我們的count[]數(shù)組索引自然不能是負(fù)數(shù)宋舷，為此绪撵，對每個返回的索引都進(jìn)行加1處理。即1表示第一個字符祝蝠，2表示第二個字符...0表示字符串末尾音诈。charAt方法如下
private static int charAt(String s, int d) {
if (d < s.length()) {
return s.charAt(d);
} else {
return -1;
}
}
我們將看到，下面的程序中绎狭，所有調(diào)用charAt方法的地方细溅，后面都會加1，像這樣charAt(a[i], d) + 1
由于字符串末尾占用了字符集的一個位置儡嘶，所以count[]數(shù)組也應(yīng)該多一個額外的位置喇聊，數(shù)組長度由原來的R+1要變成R+2。
有了這些預(yù)備基礎(chǔ)蹦狂，實現(xiàn)MSD就不難了誓篱。
package Chap9;
import java.util.Arrays;
public class MSD {
// 基數(shù)
private static int R = 256;
// 切換為插入排序的閾值
private static int M = 15;
public static void sort(String[] a) {
int N = a.length;
String[] aux = new String[N];
sort(a, aux, 0, a.length - 1, 0);
}
private static void sort(String[] a, String[] aux, int low, int high, int d) {
// 對于小型數(shù)組朋贬，切換到插入排序
if (high <= low + M) {
insertSort(a, low, high, d);
return;
}
// 在原來R+1的基礎(chǔ)上多加1是因為要將字符串末尾存放到count[1]中， count[0]依然始終為0
int[] count = new int[R + 2];
// 統(tǒng)計頻率
for (int i = low; i <= high; i++) {
count[charAt(a[i], d) + 2]++;
}
// 轉(zhuǎn)換成開始索引
for (int r = 0; r < R + 1; r++) {
count[r+1] += count[r];
}
// 數(shù)據(jù)分類
for (int i = low; i <= high; i++) {
aux[count[charAt(a[i], d) + 1]++] = a[i];
}
// 寫回原數(shù)組
for (int i = low; i <= high ; i++) {
a[i] = aux[i-low];
}
// 遞歸的以每個字符為鍵進(jìn)行排序
// 實際上每次遞歸處理的都是首字母相同的子數(shù)組窜骄，
// [low + count[r], low + count[r+ 1] -1]是首字母都相同的子數(shù)組區(qū)間
// d+1表示忽略都相同的首字母锦募，從下一個字符開始統(tǒng)計頻率 -> 計數(shù)排序
for (int r = 0; r < R; r++) {
sort(a, aux, low + count[r], low + count[r+ 1] -1, d + 1);
}
}
private static int charAt(String s, int d) {
if (d < s.length()) {
return s.charAt(d);
} else {
return -1;
}
}
private static void insertSort(String[] a, int low, int high, int d) {
for (int i = low + 1; i <= high; i++) {
// 當(dāng)前索引如果比它前一個元素要大，不用插入;否則需要插入
if (less(a[i], a[i - 1], d)) {
// 待插入的元素先保存
String temp = a[i];
// 元素右移
int j;
for (j = i; j > low && less(temp, a[j - 1], d); j--) {
a[j] = a[j - 1];
}
// 插入
a[j] = temp;
}
}
}
private static boolean less(String v, String w, int d) {
return v.substring(d).compareTo(w.substring(d)) < 0;
}
public static void main(String[] args) {
String[] a = {"she", "sells", "seashells", "by", "the", "sea", "shore", "the",
"shells", "she", "sells", "are", "surely", "seashells"};
MSD.sort(a);
System.out.println(Arrays.toString(a));
/* Output:
[are, by, sea, seashells, seashells, sells, sells, she, she, shells, shore, surely, the, the]
*/
}
}
可以看到邻遏，核心的sort方法其實只是在計數(shù)排序的基礎(chǔ)上糠亩，多加了最后一個for循環(huán)而已∽佳椋看參數(shù)列表赎线，count[r]~count[r+1] - 1這個區(qū)間表示索引為r的全部字符（它們都相同），區(qū)間兩端都加上low表示索引為r的字符的開始索引和結(jié)束索引（閉區(qū)間）糊饱。接著d + 1是因為在對子數(shù)組排序時垂寥，由于首字母都是相同的，所以忽略它對下一個字符統(tǒng)計頻率济似、排序等矫废。
下面的排序過程（假設(shè)M=0，不切換排序方法）砰蠢，能幫助你更好地理解這個算法蓖扑。可以看到low和high之間首字母都是相同的台舱，加黑的字符正是第d+1位正在被排序的字符律杠。
上面的實現(xiàn)中，有一個專為字符串準(zhǔn)備的插入排序竞惋，當(dāng)被切分的數(shù)組長度很小時（比如只有十幾個元素）柜去，會切換到插入排序直接對字符串進(jìn)行排序。同時為了避免重復(fù)檢查已知相同的字符拆宛，也改寫了less方法嗓奢，對于前d個字符都相同的字符串，將直接從索引d處開始比較浑厚。
對小型數(shù)組的特殊處理是必須的股耽。和快速排序一樣，這種遞歸地切分子數(shù)組的方法會產(chǎn)生大量微型數(shù)組钳幅。而對于每個子數(shù)組都需要創(chuàng)建一個有258個元素的count[]并將頻率轉(zhuǎn)換為索引物蝙。這種代價比其他排序方法要高很多，如果使用的是16位的Unicode字符集（R=65535）敢艰，排序過程可能會減慢上千倍诬乞。因此將小數(shù)組切換成插入排序?qū)τ诟呶粌?yōu)先的字符串排序是必須的。
MSD對于含有大量等值鍵的子數(shù)組排序會很慢，如果相同的字符串太多震嫉，切換排序方法將不會被調(diào)用森瘪。最壞情況是待排序的所有字符串全都相等，此時low和high一直保持原來的值（low=0, hgih=a.length - 1）票堵，不會切換到插入排序柜砾，而且對于相同的字符串，遞歸排序?qū)z查所有的字符换衬。
MSD基于計數(shù)排序，在切換排序方法時使用插入排序证芭，所以總的來說高位優(yōu)先的字符串排序是穩(wěn)定的瞳浦。
三向字符串快速排序
還記得三向切分的快速排序嗎？我們可以利用其思想废士，將字符串?dāng)?shù)組切分成三個子數(shù)組：一個含有所有首字母小于切分字符的子數(shù)組叫潦，一個含有所有首字母等于切分字符的子數(shù)組，一個含有所有首字母大于切分字符的子數(shù)組官硝。然后遞歸地對這三個數(shù)組排序矗蕊，要注意對于所有首字母等于切分字符的子數(shù)組，在遞歸排序時應(yīng)該忽略首字母（就像MSD中那樣）氢架。
對照三向切分的快速排序代碼傻咖，只需稍作修改就能實現(xiàn)三向字符串快速排序。
package Chap5;
import java.util.Arrays;
public class Quick3String {
// 切換為插入排序的閾值
private static int M = 15;
public static void sort(String[] a) {
sort(a, 0, a.length - 1, 0);
}
private static void sort(String[] a, int low, int high, int d) {
if (high <= low + M) {
insertSort(a, low, high, d);
return;
}
int lt = low;
int gt = high;
int i = low + 1;
// 切分字符v是a[low]的第d個字符
int v = charAt(a[low], d);
while (i <= gt) {
int t = charAt(a[i], d);
if (t < v) {
swap(a, lt++, i++);
} else if (t > v) {
swap(a, i, gt--);
} else {
i++;
}
}
// 現(xiàn)在a[lo..lt-1] < v=a[lt..gt] < a[gt+1..high]成立
// 切分元素相同的數(shù)組不會被遞歸算法訪問到岖研，對其左右的子數(shù)組遞歸排序
sort(a, low, lt - 1, d);
// 所有首字母與切分字符相等的子數(shù)組卿操，遞歸排序，像MSD那樣要忽略都相同的首字母
if (v >= 0) {
sort(a, lt, gt, d+ 1);
}
sort(a, gt + 1, high, d);
}
private static void swap(String[] a, int p, int q) {
String temp = a[p];
a[p] = a[q];
a[q] = temp;
}
private static int charAt(String s, int d) {
if (d < s.length()) {
return s.charAt(d);
} else {
return -1;
}
}
private static void insertSort(String[] a, int low, int high, int d) {
for (int i = low + 1; i <= high; i++) {
// 當(dāng)前索引如果比它前一個元素要大孙援，不用插入;否則需要插入
if (less(a[i], a[i - 1], d)) {
// 待插入的元素先保存
String temp = a[i];
// 元素右移
int j;
for (j = i; j > low && less(temp, a[j - 1], d); j--) {
a[j] = a[j - 1];
}
// 插入
a[j] = temp;
}
}
}
private static boolean less(String v, String w, int d) {
return v.substring(d).compareTo(w.substring(d)) < 0;
}
public static void main(String[] args) {
String[] a = {"she", "sells", "seashells", "by", "the", "sea", "shore", "the",
"shells", "she", "sells", "are", "surely", "seashells"};
Quick3String.sort(a);
System.out.println(Arrays.toString(a));
}
}
三向字符串快速排序的遞歸調(diào)用軌跡如下圖所示害淤。
和MSD一樣，在處理小數(shù)組時切換到了插入排序拓售，盡管它在三向切分的字符串快速排序的重要性遠(yuǎn)不及在MSD中的重要性高窥摄。三向切分的快速排序使用子數(shù)組的第一個元素作為切分點，三向切分的字符串快速排序使用子數(shù)組的第一個字符串的第d個字符作為切分字符础淤。然后在遞歸對子數(shù)組排序時崭放，相比三向切分的快速排序，三向切分的字符串快速排序多了這么一個判斷值骇，這句的意思是只要還沒到字符串的末尾（v = -1說明到達(dá)莹菱，其余均未到達(dá)），所有首字母與切分字符相等的子數(shù)組也需要遞歸排序吱瘩，不過要像MSD那樣道伟，忽略掉相同的首字母，處理下一個字符。
if (v >= 0) {
sort(a, lt, gt, d+ 1);
}
MSD可能會創(chuàng)建大量（空）子數(shù)組蜜徽，而三向字符串快速排序只將數(shù)組切分為三部分祝懂。因此三向字符串快速排序能很好處理等值鍵、有較長公共前綴的鍵拘鞋、取值范圍較小的鍵和小數(shù)組砚蓬。而且三向字符串快速排序不需要額外的空間，MSD就需要count[]和aux[]盆色，這些都是它優(yōu)于MSD的地方灰蛙。
下表總結(jié)了各種字符串排序算法的性能特點。
by @sunhaiyu
2017.11.22
