（神犇看到這個不要鄙視啊啊……饒了本沙茶啊啊……）

剛才本沙茶在看后綴數(shù)組（還木有看完）的時候，里面的那個基數(shù)排序?qū)懛ǜ鞣N看不懂……

后來到網(wǎng)上一看才發(fā)現(xiàn)這是一種極其神犇的基數(shù)排序算法，它不需要任何鏈式或類鏈式結構，也不需要在每次排序后都把所有元素按照本次排序的結果重新?lián)Q位置（其實這樣是相當耗時間的，尤其是字符串排序的時候，因為復制一個字符串的時間復雜度取決于它的長度），只需要存儲每個元素在每次排序之后的“相對下標”即可。

【1】先考慮這樣一個問題：對一個含N個元素，每個元素值的范圍為[0..SZ-1]的整數(shù)序列進行計數(shù)排序（第一關鍵字為字符，第二關鍵字為下標），并且在排序后求出ord[0..N-1]數(shù)組：ord[i]表示排在第i位的元素在排序前的下標。要求這個算法中不能使用任何鏈式或類鏈式結構（鏈表、Dancing Links、vector等）。

設立數(shù)組S，S[i]表示值為i的元素的個數(shù)。求S[i]可在O(N)時間內(nèi)求出（一般地，還要用O(SZ)的時間進行初始化）。再設立數(shù)組S0（在實現(xiàn)的時候，可以直接用S來存儲S0的值），S0[i]=∑S[0..i]（也就是值不大于i的元素的個數(shù)），求S0只需要在S的基礎上用O(SZ)時間即可。然后可以得到一個重要的性質(zhì)：對于任意i（0<=i<SZ），原序列中的所有值為i的元素，按照其下標從小到大，其名次（或者說是序號，排序前下標為i的元素的名次記為rank[i]，下同）依次為S0[i-1]..S0[i]-1（i=0時，為0..S0[i]-1，這里認為名次從0開始），這樣，只要在求出S0以后用O(N)時間掃描一遍原序列，每掃描到一個值為i的元素，立刻可以從S0中獲得其名次，同時將S0[i]的值加1，掃描完后所有的元素以后即得出了rank[0..N-1]。然后，ord與rank其實是互逆的（因為ord[i]=j等價于rank[j]=i），因此求出了rank以后可以在O(N)時間內(nèi)求出ord（當然，根據(jù)ord[rank[i]]=i這一性質(zhì)，可以在掃描過程中不求rank而直接求ord）。不過，在掃描這一步，更好的方法是倒序掃描，這樣在掃描到一個值為i的元素之后，可以不動用S[i-1]（這個當i=0時還要特判，比較麻煩），直接調(diào)用S[i]的值（當然要先將S[i]減1），就是該元素的名次了。
很明顯，該算法的時間復雜度為O(2SZ+2N)（如果不求rank直接求ord的話）=O(N)，且唯一用到的輔助空間就是S（前面已經(jīng)說過了，直接在S上存儲S0，不單獨設S0），故空間復雜度也是線性的，沒有用到鏈式或類鏈式結構。

【2】然后來解決基數(shù)排序的問題。假設這里是對字符串進行基數(shù)排序（注意，各元素的長度可能不相等，此時排序的總位數(shù)L應取所有元素長度的最大值，且排序過程中遇到不足位數(shù)的元素要特判：對該元素的該位記為@，@是一個比字符集中的所有字符都小的字符，其在字符集中名次為0，所有實際在字符集中的元素的名次為1..SZ，這樣總的字符個數(shù)就是SZ+1，在寫代碼的時候要注意），從最后一位（第L-1位）開始一位一位排序，直至第0位，中間每次排序的過程實質(zhì)上就是像【1】這樣的計數(shù)排序。

按照本沙茶以前的方法，每進行一位的排序后就要將所有元素重新調(diào)換位置（也就是構造一個新的序列代替原來的序列，原序列的下標為i的元素在新序列中下標為rank[i]），但這樣的時間開銷很大（前面已經(jīng)說過了）。更好的方法是在整個排序過程中，序列的各個元素的下標都不變，但每位排序后，序列有一個“相對下標”，相對下標為i的元素就是此次排序中排在第i位的元素（即ord[i]），這樣在每次排序時，只要操縱各元素的上一位相對下標即可（在求S的時候不用相對下標，因為S的值是由個數(shù)決定的，與順序無關，但是在求本位的ord的時候，倒序掃描序列其實是倒序掃描相對下標的序列，即掃描到下標為i，實際指的是相對下標為i，即ord[i]），注意一開始所有元素的相對下標與下標相等，即ord[i]=i。這樣就不需要調(diào)換位置了，只需要ord就行了。

最后總時間復雜度顯然是O(NL)的。

代碼（對于字符串進行基數(shù)排序，這里假設字符串只含小寫字母，注意這里的SZ是27而不是26，因為有@的存在）： 最后，Orz一下這個無比神犇的算法！！！