「數據結構」字符串排序算法最全總結

我目前是一名後端開發工程師。主要關注後端開發,數據安全,網絡爬蟲,物聯網,邊緣計算等方向。

  • Java知識點複習全手冊
  • Leetcode算法題解析
  • 劍指offer算法題解析
  • SpringCloud菜鳥入門實戰系列
  • SpringBoot菜鳥入門實戰系列
  • Python爬蟲相關技術文章
  • 後端開發相關技術文章
「數據結構」字符串排序算法最全總結

前言

本專題旨在快速瞭解常見的數據結構和算法。

在需要使用到相應算法時,能夠幫助你回憶出常用的實現方案並且知曉其優缺點和適用環境。並不涉及十分具體的實現細節考究。

字符串排序算法簡介

對於許多排序應用,決定順序的鍵都是字符串。

其主要思想是利用比較,根據字符的有限性通過計數的方式來劃分字符串的排名位置。

主要介紹以下幾種方式:

  • 預備知識:鍵索引計數法
  • 低位優先的字符串排序 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. 頻率統計

統計各個數字出現的次數,

1出現了2次
2出現了4次
3出現了4次
4出現了4次

需要用一個5位的數組記錄(比所需數字多一位),原因留給各位看官思考。

  1. 將頻率轉化為索引

前面我們記錄了各自數字的次數,並用數組保存

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……

多一個位置的原因:好處已經體現出來了,第一個就是用來標記最開始的起始位置的

  1. 數據分類

得到各個數字的起始索引,接下來就是將原數組進行歸類,將相同的數字放在一起,這裡我們用一個臨時的數組進行記錄

  1. 回寫回原數組

最後將臨時數組中的值寫會原數組

代碼實現:

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.html
  • http://lixinzhang.github.io/string-sorts-zi-fu-chuan-pai-xu.html
  • https://www.jianshu.com/p/be5b67139396
  • https://blog.csdn.net/weixin_41427400/article/details/79851043
  • https://blog.csdn.net/acmdream/article/details/74687035
  • https://www.jianshu.com/p/0966f989974d
  • https://www.jianshu.com/p/5beb3e73361d

關注我

我是蠻三刀把刀,後端開發。主要關注後端開發,數據安全,爬蟲等方向。微信:yangzd1102

Github:@qqxx6661

個人博客:

  • CSDN:@qqxx6661
  • 知乎:@Zhendong
  • 簡書:@蠻三刀把刀
  • 掘金:@蠻三刀把刀
  • Java知識點複習全手冊
  • Leetcode算法題解析
  • 劍指offer算法題解析
  • SpringCloud菜鳥入門實戰系列
  • SpringBoot菜鳥入門實戰系列
  • Python爬蟲相關技術文章
  • 後端開發相關技術文章

如果文章對你有幫助,不妨收藏起來並轉發給您的朋友們~


分享到:


相關文章: