桶排序

对于待排序的数组a，在排序时逐个遍历数组a，将数组a的值作为”桶数组r”的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。

void bucket_sort(int a[], int n) {
    int i, j;
    int bucket[maxn]; // maxn是a[]的最大值
    memset(bucket, 0, sizeof(bucket));
    // 计数
    for(i = 0; i < n; i++)
        bucket[a[i]]++;
    // 排序
    for(i = 0, j = 0; i < maxn; i++) {
        while((bucket[i]--) > 0)
            a[j++] = i;
    }
}

基数排序

桶排序的扩展。它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

int base(int i) {
    if(i == 0) return 10;
    else return 10 * base(i - 1);
}

void bucket_sort(int bit) {
    int bucket[maxn];
    int tmp[n];
    memset(bucket, 0, sizeof(bucket));
    for(int i = 0; i < n; i++)
        bucket[(a[i] / base(bit)) % 10]++;
    for(int i = 1; i < maxn; i++)
        bucket[i] += bucket[i - 1];
    for(int i = n - 1; i >= 0; i--) {
        tmp[bucket[(a[i] / base(bit)) % 10] - 1] = a[i];
        bucket[(a[i] / base(bit)) % 10]--;
    }
    for(int i = 0; i < n; i++)
        a[i] = tmp[i];
}

void radix_sort() {
    int bit = getbit();  //获取数组a的位数
    for(int i = 0; i < bit; i++)
        bucket_sort(i);
    print();  //已排好序
}

后缀数组

Str: 需要处理的字符串(长度为Len)
Suffix[i]: Str下标为i~Len的连续子串(例如Str="abcdef", Suffix[3]="def")
Rank[i]: Suffix[i]在所有后缀中的排名
SA[i]: 排名为i的后缀的起始下标，即排名为i的后缀为Suffix[SA[i]]，与Rank是互逆运算

后缀数组指的就是这个SA[i],有了它，我们就可以实现一些很强大的功能(如不相同子串个数、连续重复子串等)。如何快速的到它，便成为了这个算法的关键。而SA和Rank是互逆的，只要求出任意一个，另一个就可以O(Len)得到。
现在比较主流的算法有两种，倍增和DC3，在这里，就主要讲一下稍微慢一些，但比较好实现以及理解的倍增算法(虽说慢，但也是O(Len logLen))的。

倍增算法

Height数组

1 2	Height[i]: 表示Suffix[SA[i]]和Suffix[SA[i-1]]的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀 H[i]: 等于Height[Rank[i]]，即Height[i]=H[SA[i]]

H[i] >= H[i-1] - 1

证明：设Suffix[k]是排在Suffix[i - 1]前一名的后缀，则它们的最长公共前缀是H[i - 1]。都去掉第一个字符，就变成Suffix[k + 1]和Suffix[i]。如果H[i - 1] = 0或1,那么H[i] ≥ 0显然成立。否则，H[i] ≥ H[i - 1] - 1(去掉了原来的第一个,其他前缀一样相等)，所以Suffix[i]和在它前一名的后缀的最长公共前缀至少是H[i - 1] - 1。