字符串排序

一、背景与定义

字符串排序：针对键为字符串的排序问题，利用字符串特性设计比通用排序（如快速排序、归并排序）更高效的算法。
两类方法：
低位优先（LSD，Least-Significant-Digit First）：从右到左检查字符，适合定长字符串。
高位优先（MSD，Most-Significant-Digit First）：从左到右检查字符，适合变长字符串，能通过部分字符完成排序。
字母表大小（R）：
影响算法性能的关键因素。
示例：ASCII (R=256)、Unicode (R=65,536)、基因序列 (R=4)。

二、键索引计数法（Key-Indexed Counting）

1. 适用场景

键为小范围整数（如学生分组编号 0 到 R-1）。
示例：按组号排序学生名单。

2. 实现步骤

频率统计：
使用数组 count[]，对每个键 ( r )，count[r+1]++。
count[r] 表示键小于 ( r ) 的元素总数。
频率转索引：
累加 count[r+1] += count[r]，计算每个键的起始位置。
数据分类：
使用辅助数组 aux[]，根据 count[] 索引移动元素。
回写：
将 aux[] 复制回原数组。

3. 代码实现

public void sort(Item[] a, int R) {
    int N = a.length;
    Item[] aux = new Item[N];
    int[] count = new int[R+1];
    // 频率统计
    for (int i = 0; i < N; i++) count[a[i].key() + 1]++;
    // 频率转索引
    for (int r = 0; r < R; r++) count[r+1] += count[r];
    // 数据分类
    for (int i = 0; i < N; i++) aux[count[a[i].key()]++] = a[i];
    // 回写
    for (int i = 0; i < N; i++) a[i] = aux[i];
}

4. 性质与性能

稳定性：保持相同键元素的相对顺序。
时间复杂度：( O(N + R) )，访问数组 ( 11N + 4R + 1 ) 次（命题 A）。
空间复杂度：( O(N + R) )。

三、低位优先的字符串排序（LSD）

1. 适用场景

定长字符串（如车牌号、电话号码）。
示例：统计高速公路上不同车辆数。

2. 实现原理

对长度为 ( W ) 的字符串，从右到左（第 ( W-1 ) 到 0 位），每位用键索引计数法排序。
依赖键索引计数法的稳定性，确保前 ( i ) 位排序后顺序正确。

3. 代码实现

public class LSD {
    public static void sort(String[] a, int W) {
        int N = a.length;
        int R = 256; // ASCII
        String[] aux = new String[N];
        for (int d = W-1; d >= 0; d--) {
            int[] count = new int[R+1];
            for (int i = 0; i < N; i++) count[a[i].charAt(d) + 1]++;
            for (int r = 0; r < R; r++) count[r+1] += count[r];
            for (int i = 0; i < N; i++) aux[count[a[i].charAt(d)]++] = a[i];
            for (int i = 0; i < N; i++) a[i] = aux[i];
        }
    }
}

4. 性质与性能

稳定性：依赖键索引计数法的稳定性（命题 B）。
时间复杂度：( O(WN + WR) )，访问数组 ( \sim 7WN + 3WR ) 次。
空间复杂度：( O(N + R) )。
优势：线性时间，适合短定长字符串。

四、高位优先的字符串排序（MSD）

1. 适用场景

变长字符串（如单词列表）。
示例：排序“she sells seashells”。

2. 实现原理

用首字母（第 ( d ) 位）通过键索引计数法切分子数组，递归排序各子数组（忽略首字母）。
字符串末尾处理：charAt() 返回 -1 表示结束，计入 count[0]。
小数组优化：子数组小于阈值 ( M ) 时切换到插入排序。

3. 代码实现

public class MSD {
    private static final int R = 256;
    private static final int M = 15;
    private static String[] aux;

    private static int charAt(String s, int d) {
        return d < s.length() ? s.charAt(d) : -1;
    }

    public static void sort(String[] a) {
        int N = a.length;
        aux = new String[N];
        sort(a, 0, N-1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d) {
        if (hi <= lo + M) { Insertion.sort(a, lo, hi, d); return; }
        int[] count = new int[R+2];
        for (int i = lo; i <= hi; i++) count[charAt(a[i], d) + 2]++;
        for (int r = 0; r < R+1; r++) count[r+1] += count[r];
        for (int i = lo; i <= hi; i++) aux[count[charAt(a[i], d) + 1]++] = a[i];
        for (int i = lo; i <= hi; i++) a[i] = aux[i - lo];
        for (int r = 0; r < R; r++) sort(a, lo + count[r], lo + count[r+1] - 1, d+1);
    }
}

4. 性质与性能

时间复杂度：
平均：检查 ( N \log_R N ) 个字符（命题 C）。
最好：( O(N + R) )，最坏：( O(WN + WR) )，访问数组 ( 8N + 3R \sim 7WN + 3WR )（命题 D）。
空间复杂度：( O(N + WR) )，( W ) 为最长字符串长度。
优势：亚线性时间，适合随机字符串。
劣势：对等值键或长公共前缀敏感，空间随 ( R ) 和 ( W ) 增长。

五、三向字符串快速排序（Quick3string）

1. 适用场景

变长字符串，尤其是含重复键或长公共前缀。
示例：网站日志域名排序。

2. 实现原理

以首字母（第 ( d ) 位）进行三向切分（小于、等于、大于），仅对“等于”子数组递归下一字符。
结合快速排序和高位优先思想，避免多余切分。

3. 代码实现

public class Quick3string {
    private static int charAt(String s, int d) {
        return d < s.length() ? s.charAt(d) : -1;
    }

    public static void sort(String[] a) {
        sort(a, 0, a.length - 1, 0);
    }

    private static void sort(String[] a, int lo, int hi, int d) {
        if (hi <= lo) return;
        int lt = lo, gt = hi, v = charAt(a[lo], d), i = lo + 1;
        while (i <= gt) {
            int t = charAt(a[i], d);
            if (t < v) exch(a, lt++, i++);
            else if (t > v) exch(a, i, gt--);
            else i++;
        }
        sort(a, lo, lt-1, d);
        if (v >= 0) sort(a, lt, gt, d+1);
        sort(a, gt+1, hi, d);
    }
}

4. 性质与性能

时间复杂度：
平均：比较 ( \sim 2N \ln N ) 个字符（命题 E）。
范围：( O(N) \sim O(WN) )。
空间复杂度：( O(W + \log N) )（递归栈）。
优势：原地排序，适应重复键和长公共前缀，不受 ( R ) 影响。
优化：随机化、小数组切换到插入排序。

六、性能比较

算法	稳定	原地	时间复杂度（字符比较）	额外空间	优势场景
插入排序	是	是	( N \sim N^2 )	( O(1) )	小数组、有序数组
快速排序	否	是	( N \log N )	( O(\log N) )	通用，空间受限
归并排序	是	否	( N \log N )	( O(N) )	稳定通用排序
三向快速排序	否	是	( N \sim N \log N )	( O(\log N) )	大量重复键
LSD	是	否	( WN )	( O(N + R) )	短定长字符串
MSD	是	否	( N \sim WN )	( O(N + WR) )	随机字符串
Quick3string	否	是	( N \sim WN )	( O(W + \log N) )	长公共前缀、通用

七、应用与选择

LSD：定长短字符串（如车牌号），线性时间。
MSD：变长随机字符串，亚线性时间，但对 ( R ) 和等值键敏感。
Quick3string：通用场景，尤其含重复键或长前缀，原地高效。
通用排序：Java 的 compareTo() 已优化，适用于简单需求；大数据需基数排序。

八、总结

核心思想：利用字符串特性（定长/变长、字母表）优化排序。
算法选择：根据字符串长度、重复性、前缀特性及空间限制选择。
理论意义：突破 ( N \log N ) 下限，展示基数排序的强大潜力。