（神犇看到這個不要鄙視啊啊……饒了本沙茶啊啊……）
剛才本沙茶在看后綴數(shù)組（還木有看完）的時候，里面的那個基數(shù)排序?qū)懛ǜ鞣N看不懂……
后來到網(wǎng)上一看才發(fā)現(xiàn)這是一種極其神犇的基數(shù)排序算法，它不需要任何鏈?zhǔn)交蝾愭準(zhǔn)浇Y(jié)構(gòu)，也不需要在每次排序后都把所有元素按照本次排序的結(jié)果重新?lián)Q位置（其實這樣是相當(dāng)耗時間的，尤其是字符串排序的時候，因為復(fù)制一個字符串的時間復(fù)雜度取決于它的長度），只需要存儲每個元素在每次排序之后的“相對下標(biāo)”即可。
【1】先考慮這樣一個問題：對一個含N個元素，每個元素值的范圍為[0..SZ-1]的整數(shù)序列進(jìn)行計數(shù)排序（第一關(guān)鍵字為字符，第二關(guān)鍵字為下標(biāo)），并且在排序后求出ord[0..N-1]數(shù)組：ord[i]表示排在第i位的元素在排序前的下標(biāo)。要求這個算法中不能使用任何鏈?zhǔn)交蝾愭準(zhǔn)浇Y(jié)構(gòu)（鏈表、Dancing Links、vector等）。
設(shè)立數(shù)組S，S[i]表示值為i的元素的個數(shù)。求S[i]可在O(N)時間內(nèi)求出（一般地，還要用O(SZ)的時間進(jìn)行初始化）。再設(shè)立數(shù)組S0（在實現(xiàn)的時候，可以直接用S來存儲S0的值），S0[i]=∑S[0..i]（也就是值不大于i的元素的個數(shù)），求S0只需要在S的基礎(chǔ)上用O(SZ)時間即可。然后可以得到一個重要的性質(zhì)：
對于任意i（0<=i<SZ），原序列中的所有值為i的元素，按照其下標(biāo)從小到大，其名次（或者說是序號，排序前下標(biāo)為i的元素的名次記為rank[i]，下同）依次為S0[i-1]..S0[i]-1（i=0時，為0..S0[i]-1，這里認(rèn)為名次從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（當(dāng)然，根據(jù)ord[rank[i]]=i這一性質(zhì)，可以在掃描過程中不求rank而直接求ord）。不過，在掃描這一步，更好的方法是倒序掃描，這樣在掃描到一個值為i的元素之后，可以不動用S[i-1]（這個當(dāng)i=0時還要特判，比較麻煩），直接調(diào)用S[i]的值（當(dāng)然要先將S[i]減1），就是該元素的名次了。
很明顯，該算法的時間復(fù)雜度為O(2SZ+2N)（如果不求rank直接求ord的話）=O(N)，且唯一用到的輔助空間就是S（前面已經(jīng)說過了，直接在S上存儲S0，不單獨設(shè)S0），故空間復(fù)雜度也是線性的，沒有用到鏈?zhǔn)交蝾愭準(zhǔn)浇Y(jié)構(gòu)。
【2】然后來解決基數(shù)排序的問題。假設(shè)這里是對字符串進(jìn)行基數(shù)排序（注意，各元素的長度可能不相等，此時排序的總位數(shù)L應(yīng)取所有元素長度的最大值，且排序過程中遇到不足位數(shù)的元素要特判：對該元素的該位記為@，@是一個比字符集中的所有字符都小的字符，其在字符集中名次為0，所有實際在字符集中的元素的名次為1..SZ，
這樣總的字符個數(shù)就是SZ+1，在寫代碼的時候要注意），從最后一位（第L-1位）開始一位一位排序，直至第0位，中間每次排序的過程實質(zhì)上就是像【1】這樣的計數(shù)排序。
按照本沙茶以前的方法，每進(jìn)行一位的排序后就要將所有元素重新調(diào)換位置（也就是構(gòu)造一個新的序列代替原來的序列，原序列的下標(biāo)為i的元素在新序列中下標(biāo)為rank[i]），但這樣的時間開銷很大（前面已經(jīng)說過了）。更好的方法是在整個排序過程中，序列的各個元素的下標(biāo)都不變，但每位排序后，序列有一個“相對下標(biāo)”，相對下標(biāo)為i的元素就是此次排序中排在第i位的元素（即ord[i]），這樣在每次排序時，只要操縱各元素的上一位相對下標(biāo)即可（在求S的時候不用相對下標(biāo)，因為S的值是由個數(shù)決定的，與順序無關(guān)，但是在求本位的ord的時候，倒序掃描序列其實是倒序掃描相對下標(biāo)的序列，即掃描到下標(biāo)為i，實際指的是相對下標(biāo)為i，即ord[i]），注意一開始所有元素的相對下標(biāo)與下標(biāo)相等，即ord[i]=i。這樣就不需要調(diào)換位置了，只需要ord就行了。
最后總時間復(fù)雜度顯然是O(NL)的。
代碼（對于字符串進(jìn)行基數(shù)排序，這里假設(shè)字符串只含小寫字母，注意這里的SZ是27而不是26，因為有@的存在）：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
const int MAXN = 100000, MAXLEN = 101, SZ = 27;
int n, L0[MAXN], ord[MAXN], tmp[MAXN], S[SZ];
char A[MAXN][MAXLEN];
void init()
{
scanf("%d", &n);
re(i, n) scanf("%s", A[i]);
}
void solve()
{
int L = 0;
re(i, n) {
L0[i] = strlen(A[i]); ord[i] = i;
if (L0[i] > L) L = L0[i];
}
rre(j, L) {
re(i, SZ) S[i] = 0;
re(i, n) S[L0[i] > j ? A[i][j] - 96 : 0]++;
re2(i, 1, SZ) S[i] += S[i - 1];
rre(i, n) tmp[--S[L0[ord[i]] > j ? A[ord[i]][j] - 96 : 0]] = ord[i];
re(i, n) ord[i] = tmp[i];
}
}
void pri()
{
re(i, n) puts(A[ord[i]]);
}
int main()
{
init();
solve();
pri();
return 0;
}
最后，Orz一下這個無比神犇的算法！??！