基于《算法（第四版）》的cpp实现，介绍两种字符串排序方法LSD和MSD。

键索引计数法

两种字符串排序方法都以此为基石。周记中提到过的颜色排序题目，就用到了该方法的一半功力。键索引计数法最大的意义在于保证了字符串排序的稳定性，后面会看到。

假设有如下表格需要排序。

Name	Group
Anderson	2
Brown	3
Davis	0
Garcia	4
Harris	1
Jackson	3
Johnson	4

按照组别从小到大排列但保持稳定性。写个map然后sort时间复杂度大约是$O(n \cdot \log n)$，但我们可以利用一些性质来更快地实现。首先利用一个count数组，记录每个组别出现的次数，然后利用一个索引数组，记录排好序后每个组别出现的索引位置。

int R {5};
std::vector<int> count(R + 1, 0); // R为组别范围，该表格有5组，所以R为5
for (int i = 0; i < N; i++) {
    count[getGroup(name[i]) + 1]++;
}

// 计算索引数组，即排序后每个组别第一次出现的索引位置
for (int r = 0; r < R; r++) {
    count[r + 1] += count[r];
}

排序，找到其第一次出现的位置后，记录进去，该值下一次出现的位置即为当前索引+1。

for (int i = 0; i < N; i++) {
    aux[count[getGroup(name[i])]++] = v[i];
}

aux存储排序后的结果，v为原始数组。

LSD

LSD智能对长度相同的字符串进行排序。只要理解了键索引计数法，LSD原理就变得十分简单，其本质就是键索引计数法的循环。

如果我们有一组长度为w的字符串数组，LSD只需要对所有字符串，从最后一位开始往前扫描，将每个字符的ASCII码作为索引，使用键索引计数法。

void LSD_sort(std::vector<std::string> &v, int w) {
    int R = 256;
    int N = v.size();
    std::vector<std::string> aux(N);

    for (int d = w - 1; d >= 0; d--) {
        std::vector<int> count(R + 1, 0);
        for (int i = 0; i < N; i++) {
            count[v[i][d] + 1]++;
        }
        for (int r = 0; r < R; r++) {
            count[r + 1] += count[r];
        }
        for (int i = 0; i < N; i++) {
            aux[count[v[i][d]]++] = v[i];
        }
        // 将排序好的结果复制到原数组中。这里使用了swap即为交换两个数组，避免了不必要复制。
        v.swap(aux);
    }
}

LSD的算法复杂度是$O(wN)$，其中$w$是字符串的长度，$N$是待排序数组中字符串的个数。

MSD

相比LSD更适合用循环实现，MSD更适合用递归实现。MSD不局限于同长度字符串数组，任何长度的字符串数组都可以用MSD排序。

其思路与LSD相反，从左到右使用键索引计数法，将字符串数组分为多个子数组，再对每个子数组进行排序，不断递归执行下去。函数签名如下：

// aux为辅助数组，lo, hi为上下界，d为当前排序的位数（从左至右）
void MSDsort(std::vector<std::string>& v, std::vector<std::string>& aux, int lo, int hi, int d);

递归终止方式很简单，当hi <= lo时，说明已经排序完成，直接返回。

老样子先建立count数组然后进行键索引计数法。

int R = 256;
std::vector<int> count(256 + 1, 0);

for (int i = lo; i <= hi; i++) {
    // 这里多一步是为了判断访问索引是否越界。
    int char_val = d < v[i].size() ? v[i][d] : 0;
    count[char_val + 1]++;
}
for (int r = 0; r < R; r++) {
    count[r + 1] += count[r];
}
for (int i = lo; i <= hi; i++) {
    int char_val = (d < v[i].size()) ? v[i][d] : 0;
    aux[count[char_val]++] = v[i];
}
// 复制回到原数组。
for (int i = lo; i <= hi; i++) {
    v[i] = aux[i - lo];
}

之后对每一个子数组递归进行排序。

for (int r = 0; r < R; r++) {
    MSDsort(v, aux, lo, lo + count[r] - 1, d + 1);
}

MSD平均时间复杂度是$O(N \cdot \log_R N)$，其中$R$为字符集大小。