一蝶缀、字符串排序算法比較
本文介紹的排序算法與傳統(tǒng)的基于比較的通用排序算法不同，本文主要介紹LSD string sort、MSD string sort以及3-way string quicksort犀盟。
這些排序算法都利用了字母表（Alphabet）的概念，時(shí)間復(fù)雜度通常都是線性的（傳統(tǒng)的通用排序算法最佳性能只能達(dá)到線性對(duì)數(shù)級(jí)別NlgN）蝇狼，但通常需要額外的空間阅畴。
字母表（Alphabet）
本文中，字母表就是給定一個(gè)字符集合的字典迅耘，保存著字符和索引之間的唯一映射贱枣。
如ASCII字母表，每個(gè)ASCII字符都有唯一的數(shù)值颤专，且根據(jù)字符計(jì)算數(shù)值所需的時(shí)間通常是常數(shù)級(jí)別纽哥。
下圖是各類排序算法的性能比較：
1-1 各類字符串排序算法的性能
二、鍵索引計(jì)數(shù)法
鍵索引計(jì)數(shù)法（key-indexed counting sort）栖秕，是本文介紹的各類排序算法的基礎(chǔ)春塌。該算法僅針對(duì)鍵范圍已知的序列（鍵值需要大于等于0），效率高于通用排序算法。其另一特點(diǎn)是摔笤，該算法是穩(wěn)定的够滑。
2.1 基本思想
假設(shè)有一組待排序的鍵，其值范圍在O~R-1之間吕世。
那么通過計(jì)算每個(gè)鍵的頻率彰触，就可以知道每個(gè)鍵在排序結(jié)果中的起始位置：
每個(gè)鍵在排序結(jié)果中的起始索引=前一個(gè)鍵的起始索引+前一個(gè)鍵的頻次
具體步驟：
- 統(tǒng)計(jì)各個(gè)鍵出現(xiàn)的頻次，如count[i]表示鍵i出現(xiàn)的頻次命辖；
- 統(tǒng)計(jì)每個(gè)鍵k在排序結(jié)果中的起始索引
index[k]况毅；
index[k] = index[k-1] + count[k-1]; - 遍歷原序列的每個(gè)元素，按照鍵的起始索引復(fù)制到輔助數(shù)組尔艇；（由此可知尔许，該排序算法是穩(wěn)定的）
- 將輔助數(shù)組復(fù)制回原序列。
源碼：
/**
* 鍵索引計(jì)數(shù)法排序 假設(shè)array數(shù)組中鍵的范圍在0～R-1之間
* TODO:優(yōu)化點(diǎn),count和index數(shù)組可以合并
*/
private void sort(Student[] array, int R) {
int N = array.length;
Student[] aux = new Student[N]; // 輔助數(shù)組终娃，保存排序結(jié)果
// 1.統(tǒng)計(jì)每個(gè)鍵出現(xiàn)的頻次
// count[i]表示鍵i出現(xiàn)的頻次
int[] count = new int[R];
for (int i = 0; i < N; i++) {
count[aux[i].key]++;
}
// 2.統(tǒng)計(jì)每個(gè)鍵在排序結(jié)果中的起始索引
// index[i]表示鍵i所在的排序結(jié)果中的初始索引
int[] index = new int[R];
/**
* index[0] = 0;
* index[1] = index[0] + count[0];
* index[2] = index[1] + count[1];
* ...
* index[k] = index[k-1] + count[k-1];
*/
index[0] = 0;
for (int i = 1; i <= R; i++) {
index[i] = index[i - 1] + count[i - 1];
}
// 3.元素分類
// 遍歷原數(shù)組中的每一個(gè)元素味廊，進(jìn)行分類
for (int i = 0; i < N; i++) {
// 原數(shù)組中的元素array[i]所在排序結(jié)果中的位置
int idx = index[array[i].key];
aux[idx] = array[i];
index[array[i].key]++;
}
// 4.回寫
for (int i = 0; i < N; i++)
array[i] = aux[i];
}
注：上述代碼有很多可以優(yōu)化的點(diǎn)，但是具體步驟還是上述的4個(gè)步驟棠耕，具體優(yōu)化點(diǎn)就是通過復(fù)用數(shù)組來提供空間利用率余佛，具體可以參見MSD、LSD算法窍荧。
三辉巡、低位優(yōu)先法（LSD）
3.1 算法思想
低位優(yōu)先的字符串排序（Least-Signifcant-Digit First，LSD）蕊退，僅適用于鍵長度都相同的序列郊楣。
基本步驟：
首先，假設(shè)待排序的鍵長度均相同瓤荔，設(shè)為W净蚤。
- 排序時(shí)，從鍵的低位（最右側(cè)）開始茉贡，依次向左塞栅，先對(duì)鍵的最右一個(gè)字符采用鍵索引計(jì)數(shù)法進(jìn)行排序。
- 然后腔丧，從右向左以下一個(gè)字符作為關(guān)鍵字放椰，用鍵索引計(jì)數(shù)法排序，總共需要排序W次愉粤。
3-1 LSD算法示意圖
3.2 算法證明
首先砾医，LSD的正確性依賴于鍵索引計(jì)數(shù)法是穩(wěn)定的。
顯然衣厘，鍵索引計(jì)數(shù)法是穩(wěn)定的（見2.1）如蚜。
證明過程：
假設(shè)鍵一共n位（從左到右為0,1,..,k-1,k,…,n-1）压恒，在對(duì)第k位排序后，k位肯定有序了错邦。此時(shí)對(duì)進(jìn)行k-1位排序探赫，k-1位有兩種情況：
- k-1位待排序的兩個(gè)鍵值相同，此時(shí)由于鍵索引計(jì)數(shù)法是穩(wěn)定的撬呢，所以k-1位排完后伦吠，k位原來的順序不會(huì)改變，如果k是第0位魂拦，那整個(gè)鍵就已經(jīng)有序了毛仪；
- k-1位待排序的兩個(gè)鍵值不同，此時(shí)原來k位的有序性已經(jīng)沒有了意義芯勘，因?yàn)閗-1位排序后箱靴，會(huì)打亂k位的元素順序，最終結(jié)果以k-1位為準(zhǔn)荷愕，如果k是第0位衡怀，那整個(gè)鍵也已經(jīng)有序了（雖然此時(shí)k位可能是無序的）；
綜上：
LSD算法的目的就是：
1. 在較高位字符相同的情況下安疗，保持著較低位的順序狈癞；
2. 在較高位字符不同的情況下，保證較高位要有序茂契，此時(shí)低位的順序已經(jīng)沒有意義。
3.3 算法實(shí)現(xiàn)
public class LSD {
private LSD() {
}
/**
* LSD算法（每個(gè)待排序元素的鍵長度必須相同）
* @param array 待排序數(shù)組
* @param w 鍵長度
*/
public static void sort(String[] array, int w) {
int N = array.length;
int R = 256; // 鍵范圍
String[] aux = new String[N]; // 輔助數(shù)組
// 從右往左慨绳，對(duì)第k個(gè)字符掉冶，用鍵索引計(jì)數(shù)法排序
for (int k = w - 1; k >= 0; d--) {
// 計(jì)算鍵的頻率
int[] count = new int[R + 1];
for (int i = 0; i < n; i++)
count[array[i].charAt(k) + 1]++;
// 計(jì)算鍵排序后的初始索引
for (int r = 0; r < R; r++)
count[r + 1] += count[r];
// 元素分類
for (int i = 0; i < n; i++)
aux[count[array[i].charAt(k)]++] = array[i];
// 回寫
for (int i = 0; i < n; i++)
array[i] = aux[i];
}
}
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
int n = a.length;
// check that strings have fixed length
int w = a[0].length();
for (int i = 0; i < n; i++)
assert a[i].length() == w : "Strings must have fixed length";
sort(a, w);
for (int i = 0; i < n; i++)
StdOut.println(a[i]);
}
}
注意：上述代碼為了說明LSD的思想，未對(duì)鍵索引計(jì)數(shù)法優(yōu)化脐雪，優(yōu)化后的完整代碼如下：
public class LSD {
private static final int BITS_PER_BYTE = 8;
private LSD() {
}
/**
* Rearranges the array of W-character strings in ascending order.
*
* @param a the array to be sorted
* @param w the number of characters per string
*/
public static void sort(String[] a, int w) {
int n = a.length;
int R = 256; // extend ASCII alphabet size
String[] aux = new String[n];
for (int d = w - 1; d >= 0; d--) {
// sort by key-indexed counting on dth character
// compute frequency counts
int[] count = new int[R + 1];
for (int i = 0; i < n; i++)
count[a[i].charAt(d) + 1]++;
// compute cumulates
for (int r = 0; r < R; r++)
count[r + 1] += count[r];
// move data
for (int i = 0; i < n; i++)
aux[count[a[i].charAt(d)]++] = a[i];
// copy back
for (int i = 0; i < n; i++)
a[i] = aux[i];
}
}
/**
* Rearranges the array of 32-bit integers in ascending order. This is about
* 2-3x faster than Arrays.sort().
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
final int BITS = 32; // each int is 32 bits
final int R = 1 << BITS_PER_BYTE; // each bytes is between 0 and 255
final int MASK = R - 1; // 0xFF
final int w = BITS / BITS_PER_BYTE; // each int is 4 bytes
int n = a.length;
int[] aux = new int[n];
for (int d = 0; d < w; d++) {
// compute frequency counts
int[] count = new int[R + 1];
for (int i = 0; i < n; i++) {
int c = (a[i] >> BITS_PER_BYTE * d) & MASK;
count[c + 1]++;
}
// compute cumulates
for (int r = 0; r < R; r++)
count[r + 1] += count[r];
// for most significant byte, 0x80-0xFF comes before 0x00-0x7F
if (d == w - 1) {
int shift1 = count[R] - count[R / 2];
int shift2 = count[R / 2];
for (int r = 0; r < R / 2; r++)
count[r] += shift1;
for (int r = R / 2; r < R; r++)
count[r] -= shift2;
}
// move data
for (int i = 0; i < n; i++) {
int c = (a[i] >> BITS_PER_BYTE * d) & MASK;
aux[count[c]++] = a[i];
}
// copy back
for (int i = 0; i < n; i++)
a[i] = aux[i];
}
}
/**
* Reads in a sequence of fixed-length strings from standard input; LSD
* radix sorts them; and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
int n = a.length;
// check that strings have fixed length
int w = a[0].length();
for (int i = 0; i < n; i++)
assert a[i].length() == w : "Strings must have fixed length";
// sort the strings
sort(a, w);
// print results
for (int i = 0; i < n; i++)
StdOut.println(a[i]);
}
}
四厌小、高位優(yōu)先法（MSD）
4.1 算法思想
高位優(yōu)先的字符串排序（Most-Signifcant-Digit First，MSD）战秋，可以處理不等長的字符串璧亚。
基本步驟：
MSD算法從左向右檢查每個(gè)字符：
- 先對(duì)第一個(gè)字符進(jìn)行鍵索引計(jì)數(shù)排序，排序后將所有首字符相同的歸為一個(gè)子數(shù)組
- 然后對(duì)每個(gè)子數(shù)組分別按照步驟1進(jìn)行遞歸排序脂信。
4-1 MSD算法示意圖
注意：在對(duì)各個(gè)子數(shù)組進(jìn)行排序時(shí)癣蟋，需要特別注意到達(dá)字符串末尾的情況。
比如“RON”和“RONG”狰闪，顯然“RON”應(yīng)小于“RONG”疯搅，所以字符串末尾在字符集中對(duì)應(yīng)的整數(shù)應(yīng)該最小。
為此定義一個(gè)特殊方法charAt埋泵，用來映射鍵字符和整數(shù)值幔欧，當(dāng)索引達(dá)到字符串末尾時(shí)罪治，默認(rèn)為最小鍵0。
4.2 算法實(shí)現(xiàn)
public class MSD {
// 字符集大小礁蔗，即基數(shù)
private static final int R = 256;
// 切換為插入排序時(shí)觉义，子字符串?dāng)?shù)組大小
private static final int M = 15;
public static void sort(String[] array) {
int N = array.length;
String[] aux = new String[N];
sort(array, aux, 0, N - 1, 0);
}
/**
* MSD排序的遞歸方法. 即對(duì)array[start...end]中的每個(gè)字符串，按照第index個(gè)字符進(jìn)行鍵索引計(jì)數(shù)排序
*
* @param array 待排序子序列
* @param aux 輔助數(shù)組
* @param start 子序列起始索引
* @param end 子序列結(jié)束索引
* @param index 子序列中運(yùn)用鍵索引計(jì)數(shù)排序的字符索引位置浴井，從0開始計(jì)
*/
private static void sort(String[] array, String[] aux, int start, int end, int index) {
// 對(duì)于小型數(shù)組晒骇，切換到插入排序
if (start + M >= end) {
insertSort(array, start, end, index);
return;
}
// 1.頻數(shù)統(tǒng)計(jì)
int[] count = new int[R];
for (int i = start; i <= end; i++) {
count[charAt(array[i], index)]++;
}
// 2.轉(zhuǎn)換為鍵在排序結(jié)果中的起始索引
// 注意array數(shù)組的起始位置是start
int[] idx = new int[R];
idx[0] = start;
for (int i = 1; i < R; i++) {
idx[i] = idx[i - 1] + count[i - 1];
}
// 3.復(fù)制排序結(jié)果至輔助數(shù)組
for (int i = start; i <= end; i++) {
aux[idx[charAt(array[i], index)]++] = array[i];
}
// 4.回寫排序結(jié)果
for (int i = start; i <= end; i++) {
array[i] = aux[i];
}
// 遞歸處理首字符相同的子數(shù)組
// 此時(shí)idx保存的是每個(gè)鍵的結(jié)束索引+1
for (int i = 0; i < R; i++) {
sort(array, aux, idx[i] - count[i], idx[i] - 1, index + 1);
}
}
// 計(jì)算字符串在索引index的字符鍵值
private static int charAt(String s, int index) {
assert index >= 0;
if (index >= s.length())
return 0;
return s.charAt(index) + 1;
}
// 對(duì)array[start...end]中的字符串，進(jìn)行插入排序
private static void insertSort(String[] array, int start, int end, int index) {
for (int i = start + 1; i <= end; i++) {
for (int j = i; j > start && less(array[j], array[j - 1], index); j--) {
exchange(array, j, j - 1);
}
}
}
private static void exchange(String[] array, int i, int j) {
String temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static boolean less(String s1, String s2, int index) {
// assert s1.substring(0, index).equals(s2.substring(0, index));
for (int i = index; i < Math.min(s1.length(), s1.length()); i++) {
if (s1.charAt(i) < s2.charAt(i))
return true;
if (s1.charAt(i) > s2.charAt(i))
return false;
}
return s1.length() < s2.length();
}
}
注意：上述代碼為了說明LSD的思想滋饲，未對(duì)鍵索引計(jì)數(shù)法優(yōu)化厉碟，優(yōu)化后的完整代碼如下：
public class MSD {
private static final int BITS_PER_BYTE = 8;
private static final int BITS_PER_INT = 32; // each Java int is 32 bits
private static final int R = 256; // extended ASCII alphabet size
private static final int CUTOFF = 15; // cutoff to insertion sort
// do not instantiate
private MSD() { }
/**
* Rearranges the array of extended ASCII strings in ascending order.
*
* @param a the array to be sorted
*/
public static void sort(String[] a) {
int n = a.length;
String[] aux = new String[n];
sort(a, 0, n-1, 0, aux);
}
// return dth character of s, -1 if d = length of string
private static int charAt(String s, int d) {
assert d >= 0 && d <= s.length();
if (d == s.length()) return -1;
return s.charAt(d);
}
// sort from a[lo] to a[hi], starting at the dth character
private static void sort(String[] a, int lo, int hi, int d, String[] aux) {
// cutoff to insertion sort for small subarrays
if (hi <= lo + CUTOFF) {
insertion(a, lo, hi, d);
return;
}
// compute frequency counts
int[] count = new int[R+2];
for (int i = lo; i <= hi; i++) {
int c = charAt(a[i], d);
count[c+2]++;
}
// transform counts to indicies
for (int r = 0; r < R+1; r++)
count[r+1] += count[r];
// distribute
for (int i = lo; i <= hi; i++) {
int c = charAt(a[i], d);
aux[count[c+1]++] = a[i];
}
// copy back
for (int i = lo; i <= hi; i++)
a[i] = aux[i - lo];
// recursively sort for each character (excludes sentinel -1)
for (int r = 0; r < R; r++)
sort(a, lo + count[r], lo + count[r+1] - 1, d+1, aux);
}
// insertion sort a[lo..hi], starting at dth character
private static void insertion(String[] a, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
exch(a, j, j-1);
}
// exchange a[i] and a[j]
private static void exch(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// is v less than w, starting at character d
private static boolean less(String v, String w, int d) {
// assert v.substring(0, d).equals(w.substring(0, d));
for (int i = d; i < Math.min(v.length(), w.length()); i++) {
if (v.charAt(i) < w.charAt(i)) return true;
if (v.charAt(i) > w.charAt(i)) return false;
}
return v.length() < w.length();
}
/**
* Rearranges the array of 32-bit integers in ascending order.
* Currently assumes that the integers are nonnegative.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
int n = a.length;
int[] aux = new int[n];
sort(a, 0, n-1, 0, aux);
}
// MSD sort from a[lo] to a[hi], starting at the dth byte
private static void sort(int[] a, int lo, int hi, int d, int[] aux) {
// cutoff to insertion sort for small subarrays
if (hi <= lo + CUTOFF) {
insertion(a, lo, hi, d);
return;
}
// compute frequency counts (need R = 256)
int[] count = new int[R+1];
int mask = R - 1; // 0xFF;
int shift = BITS_PER_INT - BITS_PER_BYTE*d - BITS_PER_BYTE;
for (int i = lo; i <= hi; i++) {
int c = (a[i] >> shift) & mask;
count[c + 1]++;
}
// transform counts to indicies
for (int r = 0; r < R; r++)
count[r+1] += count[r];
// distribute
for (int i = lo; i <= hi; i++) {
int c = (a[i] >> shift) & mask;
aux[count[c]++] = a[i];
}
// copy back
for (int i = lo; i <= hi; i++)
a[i] = aux[i - lo];
// no more bits
if (d == 4) return;
// recursively sort for each character
if (count[0] > 0)
sort(a, lo, lo + count[0] - 1, d+1, aux);
for (int r = 0; r < R; r++)
if (count[r+1] > count[r])
sort(a, lo + count[r], lo + count[r+1] - 1, d+1, aux);
}
// TODO: insertion sort a[lo..hi], starting at dth character
private static void insertion(int[] a, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && a[j] < a[j-1]; j--)
exch(a, j, j-1);
}
// exchange a[i] and a[j]
private static void exch(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/**
* Reads in a sequence of extended ASCII strings from standard input;
* MSD radix sorts them;
* and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
int n = a.length;
sort(a);
for (int i = 0; i < n; i++)
StdOut.println(a[i]);
}
}
4.3 性能分析
高位優(yōu)先（LSD）的字符串排序，其性能取決于數(shù)據(jù)屠缭，即鍵對(duì)應(yīng)的值：
- 最壞情況
所有的鍵都相同箍鼓，其性能和低位優(yōu)先的字符串排序類似（大量含有相同前綴的鍵也會(huì)引起相同的問題）； - 最好情況
只需要遍歷數(shù)據(jù)一輪呵曹。
另外款咖，在子數(shù)組較小時(shí)，可以切換為其它排序方法（如插入排序）奄喂，以提升性能铐殃。
五、三向字符串快速排序
5.1 基本思想
三向字符串快速排序（3-way string quicksort）跨新，是對(duì)高位優(yōu)先（MSD）的字符串排序（Most-Signifcant-Digit First）的改進(jìn)富腊。
基本步驟：
該算法將字符串?dāng)?shù)組切分成三個(gè)子數(shù)組：
- 一個(gè)含有所有首字母小于切分字符的子數(shù)組汞扎；
- 一個(gè)含有所有首字母等于切分字符的子數(shù)組与涡；
- 一個(gè)含有所有首字母大于切分字符的子數(shù)組；
然后瞧剖，遞歸地對(duì)這三個(gè)數(shù)組排序肖揣，對(duì)于所有首字母等于切分字符的子數(shù)組民假，在遞歸排序時(shí)忽略首字母（就像MSD中那樣）。
5-1 三向字符串快速排序示意圖
5.2 算法實(shí)現(xiàn)
public static void sort(String[] a) {
StdRandom.shuffle(a); // 打亂數(shù)組
sort(a, 0, a.length - 1, 0);
}
// 3-way string quicksort a[lo..hi] starting at dth character
private static void sort(String[] a, int lo, int hi, int d) {
// 當(dāng)子字符串?dāng)?shù)組的量很小時(shí)龙优，切換為插入排序以提高性能
if (lo + M >= hi) {
insertion(a, lo, hi, d);
return;
}
int lt = lo, gt = hi, i = lo + 1;
// 查找字符表得到字符對(duì)應(yīng)的唯一鍵值羊异，并以此為基數(shù)
int v = charAt(a[lo], 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);
// a[lt..gt]之間都是d索引處等于v的鍵.
// 如果v<0，說明已經(jīng)達(dá)到字符串末尾彤断，不需要再進(jìn)行三向切分
if (v >= 0)
sort(a, lt, gt, d + 1);
sort(a, gt + 1, hi, d);
}
// return the dth character of s, -1 if d = length of s
private static int charAt(String s, int d) {
if (d == s.length())
return -1;
return s.charAt(d);
}
5-2 用例軌跡圖
完整源碼：
public class Quick3string {
private static final int CUTOFF = 15; // cutoff to insertion sort
private Quick3string() { }
/**
* Rearranges the array of strings in ascending order.
*
* @param a the array to be sorted
*/
public static void sort(String[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length-1, 0);
assert isSorted(a);
}
// return the dth character of s, -1 if d = length of s
private static int charAt(String s, int d) {
assert d >= 0 && d <= s.length();
if (d == s.length()) return -1;
return s.charAt(d);
}
// 3-way string quicksort a[lo..hi] starting at dth character
private static void sort(String[] a, int lo, int hi, int d) {
// cutoff to insertion sort for small subarrays
if (hi <= lo + CUTOFF) {
insertion(a, lo, hi, d);
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++;
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1, d);
if (v >= 0) sort(a, lt, gt, d+1);
sort(a, gt+1, hi, d);
}
// sort from a[lo] to a[hi], starting at the dth character
private static void insertion(String[] a, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
exch(a, j, j-1);
}
// exchange a[i] and a[j]
private static void exch(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// is v less than w, starting at character d
private static boolean less(String v, String w, int d) {
assert v.substring(0, d).equals(w.substring(0, d));
for (int i = d; i < Math.min(v.length(), w.length()); i++) {
if (v.charAt(i) < w.charAt(i)) return true;
if (v.charAt(i) > w.charAt(i)) return false;
}
return v.length() < w.length();
}
// is the array sorted
private static boolean isSorted(String[] a) {
for (int i = 1; i < a.length; i++)
if (a[i].compareTo(a[i-1]) < 0) return false;
return true;
}
/**
* Reads in a sequence of fixed-length strings from standard input;
* 3-way radix quicksorts them;
* and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
// read in the strings from standard input
String[] a = StdIn.readAllStrings();
int n = a.length;
// sort the strings
sort(a);
// print the results
for (int i = 0; i < n; i++)
StdOut.println(a[i]);
}
}
5.3 性能分析
優(yōu)點(diǎn)：
- 三向字符串快速排序野舶，能夠很好處理等值鍵、有效長公共前綴的鍵宰衙、取值范圍較小的鍵和小數(shù)組——所有MSD排序算法不擅長的各種情況筒愚。
- 三向字符串快速排序不需要額外的空間，它相當(dāng)與是三向快速排序和MSD的結(jié)合體菩浙。
缺點(diǎn)：
由于是基于快速排序巢掺，所以算法是不穩(wěn)定的句伶。
算法可優(yōu)化點(diǎn)：
- 隨機(jī)化
即在排序前，最好打亂數(shù)組或者將數(shù)組的第一個(gè)元素和一個(gè)隨機(jī)位置的元素交換陆淀，以得到一個(gè)隨機(jī)的切分元素考余，這樣可以預(yù)防數(shù)組已經(jīng)有序或者接近有序的最壞情況。 - 小型子數(shù)組
當(dāng)遞歸調(diào)用至待處理的子數(shù)組較小時(shí)轧苫，可以轉(zhuǎn)換為插入排序楚堤，以提高性能。
