我目前是一名後端開發工程師。主要關注後端開發，數據安全，網絡爬蟲，物聯網，邊緣計算等方向。
前言
本專題旨在快速瞭解常見的數據結構和算法。
在需要使用到相應算法時，能夠幫助你回憶出常用的實現方案並且知曉其優缺點和適用環境。並不涉及十分具體的實現細節考究。
字符串排序算法簡介
對於許多排序應用，決定順序的鍵都是字符串。
其主要思想是利用比較，根據字符的有限性通過計數的方式來劃分字符串的排名位置。
主要介紹以下幾種方式：
預備知識：鍵索引計數法低位優先的字符串排序 LSD string sort高位優先的字符串排序 MSD string Sort三向字符串快速排序 Three-way string quicksort字符串排序算法要求大家先理解：基數排序和計數排序
排序算法最強總結及其代碼實現
常用方法
預備知識：鍵索引計數法
首先我們需要了解一個預備知識：鍵索引計數法
鍵索引計數法作為三種字符串排序算法中兩種的基礎，本身也很適用於小整數鍵的簡單排序。
鍵索引計數法主要分為四步：統計頻率，將頻率轉換為索引，數據分類，回寫。
原理圖：
舉例說明：
比如數組a={1,2,3,4,2,3,4,2,1,3,4,2,3,4}，它裡面重複的數字比較多，不重複的只有1，2，3，4，這時就可以用此方法。
（例子來源：https://www.jianshu.com/p/be5b67139396）
頻率統計統計各個數字出現的次數，
1出現了2次
2出現了4次
3出現了4次
4出現了4次
需要用一個5位的數組記錄（比所需數字多一位），原因留給各位看官思考。
將頻率轉化為索引前面我們記錄了各自數字的次數，並用數組保存
a[0]=0，
a[1]=2,
a[2]=4，
a[3]=4，
a[4]=4
這裡從1開始計數，而不是從0，並不是為了與排序的數字對應，而是為了計算索引的方便，任意鍵的起始索引均為所有較小鍵的頻率之和，我們就可以a[i+1]+=a[i]遞推得到，這樣a[0]=0，a[1]=2，a[2]=6，a[3]=10，a[4]=14，這樣第一個數字（即1）的起始位置為 0，第2個數字（即 2）的起始位置為2……
多一個位置的原因：好處已經體現出來了，第一個就是用來標記最開始的起始位置的
數據分類得到各個數字的起始索引，接下來就是將原數組進行歸類，將相同的數字放在一起，這裡我們用一個臨時的數組進行記錄
最後將臨時數組中的值寫會原數組
代碼實現：
public class countSort {
public static void main(String[] args){
int[] nums={2,3,4,1,2,4,3,1,2,2,1};
countSort sort=new countSort();
sort.indecCountIndex(nums);
}
public void indecCountIndex(int[] nums){
int[] count=new int[6];
//計算頻率
for(int i=0;i<nums.length> count[nums[i]+1]++;
}
//將頻率轉化為索引
for(int i=1;i<count.length> count[i]=count[i]+count[i-1];
}
//數據分類
int[] aux=new int[nums.length];
for(int i=0;i<nums.length> aux[count[nums[i]]++]=nums[i];
}
//回寫數據（我這裡是打印）
for(int i=0;i<nums.length> System.out.print(aux[i]+" ");
}
}
}
/<nums.length>/<nums.length>/<count.length>/<nums.length>
低位優先的字符串排序 LSD string sort
定義：
待排序的字符串長度：W適用範圍：
低位優先排序在我們的生活中經常見到，比如銀行卡號的排序、車牌的排序以及電話號碼的排序等
原理：
從右向左以每個字符作為關鍵字，用鍵索引計數法將字符串排序W次。由於計數排序法是穩定的，所以低位優先的字符串排序能夠穩定地將字符串排序。
軌跡圖：
代碼實現：JAVA
摘自：https://www.cnblogs.com/sun-haiyu/p/7877651.html
算法（第四版）也有實現
import java.util.Arrays;
public class LSD {
public static void sort(String[] a, int W) {
// 每位數字範圍0~9，基為10
int R = 256;
int N = a.length;
String[] aux = new String[N];
int[] count = new int[R+1];
// 共需要d輪計數排序, 從最後一位開始，符合從右到左的順序
for (int d = W - 1; d >= 0; d--) {
// 1. 計算頻率，在需要的數組長度上額外加1
for (int i = 0; i < N; i++) {
// 使用加1後的索引，有重複的該位置就自增
count[a[i].charAt(d) + 1]++;
}
// 2. 頻率 -> 元素的開始索引
for (int r = 0; r < R; r++) {
count[r + 1] += count[r];
}
// 3. 元素按照開始索引分類，用到一個和待排數組一樣大臨時數組存放數據
for (int i = 0; i < N; i++) {
// 填充一個數據後，自增，以便相同的數據可以填到下一個空位
aux[count[a[i].charAt(d)]++] = a[i];
}
// 4. 數據回寫
for (int i = 0; i < N; i++) {
a[i] = aux[i];
}
// 重置count[]，以便下一輪統計使用
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));
}
}
上面程序將打印如下內容
[1ICK750, 1ICK750, 1OHV845, 1OHV845, 1OHV845, 2IYE230, 2RLA629, 2RLA629, 3ATW723, 3CIO720, 3CIO720, 4JZY524, 4PGC938]
高位優先的字符串排序 MSD string Sort
參考：
https://blog.csdn.net/weixin_41427400/article/details/79851043
適用範圍：
MSD與LSD比較起來，擁有更強的普適性，它不需要字符串的長度相同即可對字符串數組進行排序；
在生活中的使用也比LSD更多一些，比如字典裡的排序就是MSD的情況，當然還有很多，這裡就不再舉例了。
原理：
MSD的核心思想是分治算法，即將大問題分為小問題來解決，其思想與快速排序類似。
先對最高位的字符進行排序，將排序後的字符串進行分組——最高位相同的在一組；在對同一組的進行MSD排序，不過此時以第二位字符進行排序，直到排完最低位，算法結束。(如圖3所示)
image.png
思想講起來總是很簡單，不過當中的一些細節確實我們需要注意的。一個顯而易見的問題是怎麼處理結尾字符的問題，因為MSD運行字符的長度不同，那麼總會有字符串先結束，這是我們就需要對這些字符串進行處理。如果我們每個字符都去判斷顯然會很麻煩，因此我們選擇一種巧妙的方式使用一個CharAt(string, int)函數來返回字符串對應下標的字符，當對應下標不存在的時候我們返回-1；
/* 轉換函數:返回字符串中對於索引的字符
* 參數:s:想要進行轉換的字符串，i:字符索引
* 返回值:對應索引的字符，若超出字符串長度返回-1
*/
char CharAt(string s, int i) {
if (i < s.length())
return s[i];
else
return -1;
}
這樣我們就可以把字符串結尾的情況同其餘情況一起處理，同時保證了已結尾的字符串會在未結尾的字符串之前！
代碼實現：
詳見算法（第四版）第五章或者如下網址C++實現：
https://blog.csdn.net/weixin_41427400/article/details/79851043
提升性能：
在數值排序中提到過一次優化排序效率的方法：當待排序數組的長度較小時，使用插入排序。同樣的，該方法也適應與高位優先字符串排序，而且這種優化一般情況下也是必須的，有專家做過實驗，在數據量巨大時，將長度小於10的子數組排序切換到插入排序，可以將排序的效率提升十倍左右。
三向字符串快速排序 Three-way string quicksort
MSD對包含大量重複鍵的字符串進行排序時，效率十分低下。三向字符串快速排序可以很好的解決這個問題，其是MSD和快速排序的結合版。
適用範圍：
非常適用於有共同前綴的字符串
預備知識：三向切分的快速排序（數字快速排序的改進算法）
參考：
https://www.jianshu.com/p/0966f989974d
要理解三向字符串快速排序，需要先理解好三向切分的快速排序。
傳統快速排序中，可能出現大量重複元素，最特殊的情況：一個數組中所有元素都相同，此時無需繼續排序了，但是普通的快速排序算法還是會對數組進行切分。基於此可以將數組切分成三部分，分別對應小於、等於、大於切分元素的數組元素。
我們來看這種被稱為三向切分的快速排序。它從左到右遍歷數組一次，維護一個指針lt使得a[low…lt-1]中的元素都小於v，一個指針gt使得a[gt + 1…high]中的元素都大於v，一個指針i使得a[lt..i-1]中的元素都等於v，a[i..gt]中的元素暫定。一開始i和low相等。隨著循環，a[i…gt]越來越小，即gt-i不斷減小，當i > gt時循環結束。循環中進行下面的操作：
如果a[i]小於v，將a[i]和a[lt]交換，lt和i都加1；如果a[i]大於v，將a[i]和a[gt]交換，gt減1；如果a[i]等於v，將i加1上面的這些操作保證了最後i > gt可以推出循環。
下面是三向切分快速排序的實現代碼：
public class Quick3way {
public static void sort(Comparable[] a) {
shuffle(a);
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int low, int high) {
if (high <= low) {
return;
}
int lt = low;
int gt = high;
int i = low + 1;
// 切分元素
Comparable v = a[low];
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) {
swap(a, lt++, i++);
} else if (cmp > 0) {
swap(a, i, gt--);
} else {
i++;
}
}
// 現在a[lo..lt-1] < v=a[lt..gt] < a[gt+1..high]成立
// 切分元素相同的數組不會被遞歸算法訪問到，對其左右的子數組遞歸排序
sort(a, low, lt - 1);
sort(a, gt + 1, high);
}
}
對於存在大量重複元素的數組，這種方法比標準的快速排序要快。三向切分的最壞情況是所有元素各不相同，這時會比標準的快速排序要慢，因為比起標準的快速排序使用了更多的比較。
對於包含大量重複元素的數組，三向切分的快速排序算法將排序時間從線性對數級降低到線性級別，因此時間複雜度介於O(N)和O(Nlg N)之間，這依賴於輸入數組中重複元素的數量。
三向字符串快速排序
我們可以利用上面學習的三向切分的數字快速排序思想，將字符串數組切分成三個子數組：
一個含有所有首字母小於切分字符的子數組一個含有所有首字母等於切分字符的子數組一個含有所有首字母大於切分字符的子數組。然後遞歸地對這三個數組排序，要注意對於所有首字母等於切分字符的子數組，在遞歸排序時應該忽略首字母（就像MSD中那樣）。
遞歸調用軌跡:
image.png
代碼實現：
在三向切分的數字快速排序的基礎上稍加修改
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++;
}
}
// 現在a[lo..lt-1] < v=a[lt..gt] < a[gt+1..high]成立
// 切分元素相同的數組不會被遞歸算法訪問到，對其左右的子數組遞歸排序
sort(a, low, lt - 1, d);
// 所有首字母與切分字符相等的子數組，遞歸排序，像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++) {
// 當前索引如果比它前一個元素要大，不用插入;否則需要插入
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));
}
}
三向切分的快速排序使用子數組的第一個元素作為切分點，三向切分的字符串快速排序使用子數組的第一個字符串的第d個字符作為切分字符。
在遞歸對子數組排序時，相比三向切分的快速排序，三向切分的字符串快速排序多了這麼一個判斷，這句的意思是隻要還沒到字符串的末尾（v = -1說明到達，其餘均未到達），所有首字母與切分字符相等的子數組也需要遞歸排序，不過要像MSD那樣，忽略掉相同的首字母，處理下一個字符。
總結
字符串排序算法選擇：
參考
算法（第四版）:第五章第一節https://www.cnblogs.com/sun-haiyu/p/7877651.htmlhttp://lixinzhang.github.io/string-sorts-zi-fu-chuan-pai-xu.htmlhttps://www.jianshu.com/p/be5b67139396https://blog.csdn.net/weixin_41427400/article/details/79851043https://blog.csdn.net/acmdream/article/details/74687035https://www.jianshu.com/p/0966f989974dhttps://www.jianshu.com/p/5beb3e73361d關注我
我是蠻三刀把刀，後端開發。主要關注後端開發，數據安全，爬蟲等方向。微信：yangzd1102
Github：@qqxx6661
個人博客：
CSDN：@qqxx6661知乎：@Zhendong簡書：@蠻三刀把刀掘金：@蠻三刀把刀Java知識點複習全手冊Leetcode算法題解析劍指offer算法題解析SpringCloud菜鳥入門實戰系列SpringBoot菜鳥入門實戰系列Python爬蟲相關技術文章後端開發相關技術文章如果文章對你有幫助，不妨收藏起來並轉發給您的朋友們~