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

剛才本沙茶在看后綴數組（還木有看完）的時候，里面的那個基數排序寫法各種看不懂……

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

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

設立數組S，S[i]表示值為i的元素的個數。求S[i]可在O(N)時間內求出（一般地，還要用O(SZ)的時間進行初始化）。再設立數組S0（在實現的時候，可以直接用S來存儲S0的值），S0[i]=∑S[0..i]（也就是值不大于i的元素的個數），求S0只需要在S的基礎上用O(SZ)時間即可。然后可以得到一個重要的性質：對于任意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)時間內求出ord（當然，根據ord[rank[i]]=i這一性質，可以在掃描過程中不求rank而直接求ord）。不過，在掃描這一步，更好的方法是倒序掃描，這樣在掃描到一個值為i的元素之后，可以不動用S[i-1]（這個當i=0時還要特判，比較麻煩），直接調用S[i]的值（當然要先將S[i]減1），就是該元素的名次了。
很明顯，該算法的時間復雜度為O(2SZ+2N)（如果不求rank直接求ord的話）=O(N)，且唯一用到的輔助空間就是S（前面已經說過了，直接在S上存儲S0，不單獨設S0），故空間復雜度也是線性的，沒有用到鏈式或類鏈式結構。

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

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

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

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