不只是数字：C语言字符串排序与后缀数组入门

前五篇我们排的都是 int：

1. 《C语言常见排序算法详解》：比较排序的写法、复杂度、稳定性；
2. 《从会写到会用：C语言排序算法的实战选择与优化》：场景选型、qsort 泛型、快排优化；
3. 《突破 O(n log n)：C语言非比较排序实战》：计数/基数/桶排序；
4. 《数据放不进内存怎么办：C语言外部排序与海量数据排序实战》：分块、多路归并；
5. 《让多核一起干活：C语言并行排序与多线程实战》：pthread、OpenMP、并行粒度。

但现实里被排序的对象常常是字符串：字典、文件名、日志行、URL、基因序列。字符串排序不是"把 int 换成 char*"那么简单，它引出三个新问题：

• 比较成本不再是 O(1)：两个字符串比较要逐字符扫描，最坏 O(L)，L 为串长；
• 移动成本高：交换两个长字符串不如交换指针；
• 存在更强的结构：把所有后缀排好序，能得到后缀数组，支撑全文检索、最长重复子串等任务。

本篇从"怎么给字符串数组排序"讲到"怎么用排序构造后缀数组"，承接第 2 篇的 qsort 泛型思想，也呼应第 3 篇"利用数据额外信息"的主题。

一、字符串数组排序：先解决"比较"

1.1 用 qsort 排字符串指针数组

最常见的场景：char *words[]，每个元素是指向字符串的指针。排序交换的是指针（8 字节），不是字符串内容，这是性能关键。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 升序：strcmp 已满足 (a>b)-(a<b) 的语义，直接返回即可 */
static int cmpStr(const void *a, const void *b) {
    const char *sa = *(const char *const *)a;
    const char *sb = *(const char *const *)b;
    return strcmp(sa, sb);
}

int main(void) {
    const char *words[] = { "banana", "apple", "cherry", "date", "apple" };
    int n = sizeof(words) / sizeof(words[0]);
    qsort(words, n, sizeof(words[0]), cmpStr);
    for (int i = 0; i < n; i++) puts(words[i]);
    return 0;
}

要点：

• 比较函数收到的是"指向数组元素的指针"，元素类型是 char *，所以强转成 const char *const *，再解引用得到 const char *；
• strcmp 返回值恰好满足 qsort 对"负/零/正"的要求，直接返回即可，不要再写 strcmp(a,b) - strcmp(...) 之类的画蛇添足；
• 数组元素若声明为 const char *words[]，比较函数参数用 const void * 强转时注意 const 层级，避免编译警告。

1.2 忽略大小写 / 按 locale 排序

strcasecmp（POSIX）做大小写无关比较；strcoll 按当前 locale 的字典序比较（处理重音、特殊字符）：

#include <strings.h>   /* strcasecmp */
#include <locale.h>    /* strcoll */

static int cmpStrCase(const void *a, const void *b) {
    return strcasecmp(*(const char *const *)a, *(const char *const *)b);
}

static int cmpStrLocale(const void *a, const void *b) {
    return strcoll(*(const char *const *)a, *(const char *const *)b);
}

/* 使用 strcoll 前需 setlocale(LC_COLLATE, ""); */

注意：strcasecmp 是 POSIX 而非 C 标准，Windows 下对应 _stricmp。跨平台代码需条件编译。

1.3 按长度排序、多关键字排序

比较函数里可以组合任意规则。例如"先按长度升序，长度相同按字典序"：

static int cmpStrLenThenLex(const void *a, const void *b) {
    const char *sa = *(const char *const *)a;
    const char *sb = *(const char *const *)b;
    size_t la = strlen(sa), lb = strlen(sb);
    if (la != lb) return (la > lb) - (la < lb);
    return strcmp(sa, sb);
}

这与第 2 篇结构体多关键字排序是同一套思路：把决胜规则按优先级写进比较函数。

1.4 性能提醒：strcmp 是 O(L)

对 n 个长度 L 的字符串排序，比较排序的复杂度是 O(n log n × L)，不是 O(n log n)。当 L 很大（如长日志行）时，逐字符比较成为瓶颈。缓解手段：

• 前缀比较缓存：先比较前若干字节（如 8 字节按 uint64_t 读），不同则立即返回，相同再退化为 strcmp；
• LCP 数组：若同时排大量共享前缀的串（如 URL），预先算相邻串的最长公共前缀，可跳过重复比较。这正是后缀数组构造中"LCP 加速"的思想。

二、从"排字符串"到"排后缀"：后缀数组

字符串排序最有价值的延伸是后缀数组（Suffix Array, SA）。给定字符串 S，把所有后缀 S[i…] 按字典序排序，得到的下标数组就是后缀数组。

例：S = “banana”，后缀为：

0: banana
1: anana
2: nana
3: ana
4: na
5: a

排序后：a(5), ana(3), anana(1), banana(0), na(4), nana(2)，所以 SA = [5, 3, 1, 0, 4, 2]。

后缀数组是全文检索、最长重复子串、Burrows-Wheeler 变换等的基础，是"排序算法在字符串上的高阶应用"。

2.1 朴素构造：直接排序后缀（O(n² log n)）

最直观的做法：把每个后缀当字符串，用 qsort 排序。但每次比较 O(n)，排序 O(n log n) 次比较，总 O(n² log n)。只适合小串或教学。

typedef struct { const char *s; int idx; } Suffix;

static int cmpSuffix(const void *a, const void *b) {
    const Suffix *x = (const Suffix *)a;
    const Suffix *y = (const Suffix *)b;
    return strcmp(x->s, y->s);   /* 比较从各自起点到串尾 */
}

/* 返回 SA 数组，调用者 free */
int *buildSASimple(const char *s, int n) {
    Suffix *arr = (Suffix *)malloc(n * sizeof(Suffix));
    int *sa = (int *)malloc(n * sizeof(int));
    if (!arr || !sa) { free(arr); free(sa); return NULL; }

    for (int i = 0; i < n; i++) { arr[i].s = s + i; arr[i].idx = i; }
    qsort(arr, n, sizeof(Suffix), cmpSuffix);
    for (int i = 0; i < n; i++) sa[i] = arr[i].idx;

    free(arr);
    return sa;
}

2.2 倍增法 + 基数排序：O(n log n)

倍增法（Doubling）把每个后缀的"前 2^k 个字符"当作排序键，k 从 0 开始翻倍。关键技巧：已知长度 2^k 的排名，长度 2^(k+1) 的排名可由两个 2^k 排名拼成二元组 (rank[i], rank[i+2^k])，再对这个二元组排序。

因为排名是 [0, n) 的整数，二元组排序可以用两轮基数排序（第 3 篇的 LSD 思想）做到 O(n)，于是每轮 O(n)，共 log n 轮，总 O(n log n)。

#include <stdlib.h>
#include <string.h>

/* 对 sa 按 (rank[i], rank[i+k]) 做稳定基数排序，k 为当前步长 */
static void radixSortPairs(int sa[], int rank[], int tmp[], int n, int k) {
    /* 第一关键字：rank[i+k]（不存在视为 -1，整体 +1 映射到 0） */
    int maxv = n + 1;
    int *cnt = (int *)calloc(maxv + 1, sizeof(int));
    if (!cnt) return;

    /* ---- 先按第二关键字 rank[i+k] 排 ---- */
    for (int i = 0; i < n; i++) {
        int key = (sa[i] + k < n) ? rank[sa[i] + k] + 1 : 0;
        cnt[key]++;
    }
    for (int v = 1; v <= maxv; v++) cnt[v] += cnt[v - 1];
    for (int i = n - 1; i >= 0; i--) {
        int key = (sa[i] + k < n) ? rank[sa[i] + k] + 1 : 0;
        tmp[--cnt[key]] = sa[i];
    }
    memcpy(sa, tmp, n * sizeof(int));

    /* ---- 再按第一关键字 rank[i] 排 ---- */
    memset(cnt, 0, (maxv + 1) * sizeof(int));
    for (int i = 0; i < n; i++) cnt[rank[sa[i]] + 1]++;
    for (int v = 1; v <= maxv; v++) cnt[v] += cnt[v - 1];
    for (int i = n - 1; i >= 0; i--) {
        int key = rank[sa[i]] + 1;
        tmp[--cnt[key]] = sa[i];
    }
    memcpy(sa, tmp, n * sizeof(int));

    free(cnt);
}

/* 倍增法构造后缀数组，返回 SA（长度 n），失败返回 NULL */
int *buildSA(const char *s, int n) {
    if (n <= 0) return NULL;
    int *sa   = (int *)malloc(n * sizeof(int));
    int *rank = (int *)malloc(n * sizeof(int));
    int *tmp  = (int *)malloc(n * sizeof(int));
    int *newRank = (int *)malloc(n * sizeof(int));
    if (!sa || !rank || !tmp || !newRank) { /* 清理略 */ return NULL; }

    /* 初始：按单字符排序（字符值即初始排名，做一次计数排序） */
    for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = (unsigned char)s[i]; }
    /* 用一次简单排序得到初始 SA（字符集 256，计数排序 O(n)） */
    {
        int cnt[256] = {0};
        for (int i = 0; i < n; i++) cnt[rank[i]]++;
        for (int v = 1; v < 256; v++) cnt[v] += cnt[v - 1];
        for (int i = n - 1; i >= 0; i--) tmp[--cnt[rank[i]]] = i;
        memcpy(sa, tmp, n * sizeof(int));
    }

    for (int k = 1; k < n; k <<= 1) {
        radixSortPairs(sa, rank, tmp, n, k);

        /* 根据新 sa 重算 rank：二元组相同则排名相同 */
        newRank[sa[0]] = 0;
        int r = 0;
        for (int i = 1; i < n; i++) {
            int a1 = sa[i - 1], a2 = sa[i];
            int k1 = (a1 + k < n) ? rank[a1 + k] : -1;
            int k2 = (a2 + k < n) ? rank[a2 + k] : -1;
            if (rank[a1] != rank[a2] || k1 != k2) r++;
            newRank[a2] = r;
        }
        memcpy(rank, newRank, n * sizeof(int));
        if (r == n - 1) break;   /* 所有后缀排名已唯一，提前结束 */
    }

    free(rank); free(tmp); free(newRank);
    return sa;
}

要点：

• 每轮用两轮稳定计数排序代替比较排序，把 O(n log n) 降到 O(n)，总 O(n log n)；
• 排名相同（二元组相等）时 r 不递增，保证相同前缀的后缀排名一致；
• r == n - 1 表示所有后缀已可区分，提前退出；
• 这是后缀数组的经典入门实现，工业级实现（SA-IS）可做到 O(n)，但复杂得多。

2.3 LCP 数组：后缀数组的搭档

后缀数组常与 LCP（Longest Common Prefix）数组 一起用。lcp[i] 表示 SA 中第 i 与第 i-1 个后缀的最长公共前缀长度。利用性质 lcp[rank[i]] ≥ lcp[rank[i-1]] - 1，可在 O(n) 内算出（Kasai 算法）：

/* 计算 LCP，rank 为 SA 的逆，lcp[i] = LCP(sa[i-1], sa[i])，lcp[0]=0 */
void buildLCP(const char *s, int n, const int sa[], int lcp[]) {
    int *rank = (int *)malloc(n * sizeof(int));
    if (!rank) return;
    for (int i = 0; i < n; i++) rank[sa[i]] = i;

    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] > 0) {
            int j = sa[rank[i] - 1];
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
            lcp[rank[i]] = h;
            if (h > 0) h--;
        } else {
            h = 0;
        }
    }
    free(rank);
}

有了 SA + LCP，就能 O(n) 或 O(log n) 解决很多字符串问题：

• 最长重复子串：max(lcp) 对应的子串；
• 两个后缀的最长公共前缀：min(lcp[rank[i]+1 .. rank[j]])，配合 RMQ；
• 模式匹配：在 SA 上二分查找，O(|P| log n)。

三、字符串排序的工程技巧

3.1 排序"索引"而不是"数据"

字符串很长时，直接 qsort 字符串指针数组仍要比较内容。更彻底的做法是先排下标数组，再按下标重排原数据——这样排序阶段只移动 4/8 字节的整数，缓存友好。

这与第 2 篇"结构体排序先排索引数组"是同一思想。

3.2 前缀树（Trie）排序

若字符串集合很大且共享大量前缀，可先建 Trie，再对 Trie 做先序遍历，天然得到字典序输出。复杂度 O(总字符数)，与第 3 篇"利用数据额外信息"一脉相承。适合静态词表的一次性排序。

3.3 基数排序排定长字符串

若所有字符串等长（如定长 ID、哈希值），可把每个字符当一位，从最后一列往前做稳定计数排序（LSD 基数排序），O(L × (n + 字符集))。这正是第 3 篇基数排序在字符串上的直接应用。

3.4 大文件字符串外部排序

日志行排序常遇到"文件放不进内存"。此时沿用第 4 篇的外部排序框架：分块读入 → 块内 qsort（比较函数用 strcmp）→ 多路归并（归并时比较字符串）。唯一变化是比较函数，框架不变——这正是把算法抽象成"比较器 + 框架"的价值。

四、常见坑与检查清单

1. 比较函数强转层级错：char * 数组的元素是 char *，比较函数收到 char **，要用 const char *const * 再解引用。
2. 返回 strcmp 结果即可：不要画蛇添足做减法，strcmp 已满足符号要求。
3. strcasecmp 非标准：跨平台需条件编译，或自己写大小写归一化。
4. strcoll 需先 setlocale：否则行为等同 strcmp。
5. 后缀数组下标从 0 开始，注意 i+k < n 边界：越界判断漏掉会导致错误排名。
6. 倍增法初始排名：用 unsigned char 读字符，避免负值字符（如中文 UTF-8 字节）参与比较时出错。
7. LCP 的 h 递减：Kasai 算法依赖 h--，漏掉会退化为 O(n²)。
8. 稳定性：字符串排序若要求"相等串保持原始顺序"，需在比较函数里加原始下标决胜（同第 2 篇技巧）。

五、小结与系列脉络

字符串排序把前五篇的思想又推进了一层：

• 第 2 篇的 qsort 泛型：比较函数从"比较 int"换成"比较字符串"，框架不变；
• 第 2 篇的多关键字：字符串比较可组合长度、大小写、locale 等规则；
• 第 3 篇的基数排序：倍增法后缀数组的核心，就是用两轮稳定计数排序替代比较排序；
• 第 3 篇的"利用数据信息"：Trie、LCP 都是利用字符串的前缀结构；
• 第 4 篇的外部排序：大文件字符串排序，换比较函数即可复用框架。

一句话心法：字符串排序的瓶颈在"比较"，突破口在"避免重复比较"——预比较前缀、LCP 缓存、基数排序、Trie，都是在减少字符扫描次数。

至此系列六篇：

1. 原理：七种比较排序的写法与复杂度；
2. 实战：场景选型、泛型 qsort、快排优化、性能测试；
3. 突破：计数/基数/桶排序，突破 Ω(n log n)；
4. 规模：外部排序与多路归并，矛盾转向 I/O；
5. 并发：并行排序与多线程，榨干多核；
6. 对象：字符串排序与后缀数组，从"排数字"到"排结构"。

从数字到字符串，从内存到磁盘，从单核到多核，从"排元素"到"排后缀"——排序这条线，已经把算法工程化的主要维度走了一遍。