字符串排序算法

如果單個(gè)字符 可以使用計(jì)數(shù)排序。因?yàn)樽址姆秶邢蕖?br> 如果是多個(gè)字符的字符串 且長(zhǎng)度相同，可以使用基數(shù)排序 LSD 低位優(yōu)先排序。
如果是多個(gè)字符的字符串 且長(zhǎng)度不同，可以使用基數(shù)排序 MSD 高位優(yōu)先排序。

JDK中字符串?dāng)?shù)組排序使用的是歸并排序 ComparableTimSort 和 LegacyMergeSort（傳統(tǒng)歸并） 兩種。具體使用的是String類的重寫的compareTo方法進(jìn)行比較。

比對(duì)每一位，如果相同比較長(zhǎng)度

以上排序算法都在數(shù)字排序算法中說(shuō)明，這里不再贅述。
這里詳細(xì)說(shuō)明一下，后綴排序法。

后綴排序法

當(dāng)我們面對(duì)搜索、尋找文章中最長(zhǎng)的重復(fù)詞等需求時(shí)，可以用后綴排序法來(lái)高效解決。
從例子入手，假設(shè)有一段語(yǔ)句
itisabigappleitisa
我們把這段語(yǔ)句看成一個(gè)字符數(shù)組S[] 則S[0]=i,S[1]=t,S[2]=i,S[4]=s ......
然后把這段語(yǔ)句變成一個(gè)字符串?dāng)?shù)組。具體轉(zhuǎn)換規(guī)則為：
A[0] = S[0]~S[16]組成，A[1] = S[1]~S[16]組成，A[2] = S[2]~S[16]組成。

A數(shù)組

然后使用MSD給這個(gè)字符串?dāng)?shù)組排序（其他算法也可以，只要排序了就ok），排序完成后，后綴排序法就結(jié)束了。

排序后的A數(shù)組

下面根據(jù)不同場(chǎng)景，進(jìn)行不同操作。

尋找關(guān)鍵字

假設(shè)我們檢索itis這個(gè)詞，首先檢索i A[6]~A[10] (下標(biāo)從0開始)都符合，然后繼續(xù)檢索第二個(gè)t，然后檢索第三個(gè)，第四個(gè)。全部檢索完畢后，A[9]和A[10]滿足條件。那么就有兩個(gè)。并且A[9]字符串長(zhǎng)度為5 那么在原字符數(shù)組中，開始的下標(biāo)是倒數(shù)第五個(gè)。

尋找文章中最長(zhǎng)的重復(fù)詞

其實(shí)當(dāng)我們后綴排序完后，重復(fù)詞已經(jīng)緊挨在一起了。
遍歷排好序的A數(shù)組
A[0]和A[1] 找出重復(fù)詞a,長(zhǎng)度為1
A[1]和A[2] 同樣是a
A[2]和A[3]，沒(méi)有重復(fù)詞；
直到A[9]和A[10] ，找到重復(fù)詞為itisa 長(zhǎng)度為5
對(duì)比方法也很簡(jiǎn)單：把兩個(gè)詞相同的位置進(jìn)行逐一對(duì)比，一旦出現(xiàn)不相同。則對(duì)比結(jié)束。返回相同的字符串。