24. 字符串的字典序：字符串排序，寻找字典序的下一个排列

字典序，说白了就是「按字母表顺序排」。你查英文字典的时候，apple 排在 banana 前面，这就是字典序。在 C 语言里处理字符串排序，本质上就是比较字符的 ASCII 码值。

我记得刚入行那会儿，有个需求是要对一批用户名做排序。我心想这还不简单？直接冒泡排序，strcmp 一比较就完事了。结果上线后，用户反馈说排序结果不对——大小写混在一起，'Z' 排在了 'a' 前面。嗯，这就是典型的字典序陷阱。

24.1 字典序的基本规则

两个字符串比较时，从左到右逐个字符比较。遇到第一个不同的字符，谁的 ASCII 码小，谁就排在前面。如果一个字符串是另一个的前缀，短的排前面。

核心规则：

  • 字符按 ASCII 码值比较：'A'(65) < 'B'(66) < ... < 'Z'(90) < 'a'(97) < 'b'(98)
  • 空字符 '\0' 的 ASCII 码是 0，比任何可见字符都小
  • 数字字符 '0'(48) 排在字母前面

举个例子：

"abc" < "abd"    // 第三个字符 'c'(99) < 'd'(100)
"ab"  < "abc"    // "ab" 是 "abc" 的前缀
"ABC" < "abc"    // 'A'(65) < 'a'(97)
"123" < "abc"    // '1'(49) < 'a'(97)

24.2 字符串排序：用 qsort 实现

我建议你直接用标准库的 qsort，别自己手写排序算法。为什么？因为 qsort 是经过高度优化的，而且不容易写错。我自己在项目中踩过坑——手写冒泡排序处理几千个字符串，性能惨不忍睹。

来看一个完整的排序示例：

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

// 比较函数：按字典序升序
int compare_strings(const void *a, const void *b) {
    // a 和 b 是 char** 类型，需要先解引用
    const char **str1 = (const char **)a;
    const char **str2 = (const char **)b;
    return strcmp(*str1, *str2);
}

int main() {
    // 字符串数组
    const char *fruits[] = {
        "banana", "apple", "Cherry", "date", "Apple"
    };
    int n = sizeof(fruits) / sizeof(fruits[0]);

    printf("排序前：\n");
    for (int i = 0; i < n; i++) {
        printf("  %s\n", fruits[i]);
    }

    // 调用 qsort 排序
    qsort(fruits, n, sizeof(char *), compare_strings);

    printf("\n排序后（字典序）：\n");
    for (int i = 0; i < n; i++) {
        printf("  %s\n", fruits[i]);
    }

    return 0;
}

输出结果：

排序前：
  banana
  apple
  Cherry
  date
  Apple

排序后（字典序）：
  Apple
  Cherry
  apple
  banana
  date

注意：大写字母 'A'(65) 比小写 'a'(97) 小，所以 "Apple" 排在了 "apple" 前面。如果你想要忽略大小写的排序，可以用 strcasecmp()（POSIX 标准）或者自己写一个忽略大小写的比较函数。

24.3 忽略大小写的字典序排序

实际项目中，大部分场景需要忽略大小写。我曾经做过一个通讯录应用，用户输入 "张三" 和 "zhangsan" 应该排在一起，而不是按 ASCII 码分开。

自己实现一个忽略大小写的比较函数：

#include <ctype.h>

int compare_ignore_case(const void *a, const void *b) {
    const char **str1 = (const char **)a;
    const char **str2 = (const char **)b;
    
    const char *s1 = *str1;
    const char *s2 = *str2;
    
    while (*s1 && *s2) {
        char c1 = tolower((unsigned char)*s1);
        char c2 = tolower((unsigned char)*s2);
        
        if (c1 != c2) {
            return c1 - c2;
        }
        s1++;
        s2++;
    }
    
    // 处理前缀情况
    if (*s1 == '\0' && *s2 == '\0') return 0;
    if (*s1 == '\0') return -1;
    return 1;
}

注意：tolower() 的参数要转为 unsigned char，否则在扩展 ASCII 字符上可能产生未定义行为。这是我在一次处理中文环境时踩过的坑。

24.4 寻找字典序的下一个排列

这个题目很有意思。给你一个字符串，比如 "abc"，它的下一个字典序排列是 "acb"。再下一个是 "bac"，然后是 "bca"，"cab"，最后是 "cba"。

算法思路其实不复杂，我总结为三步：

  1. 从右向左找第一个降序对：找到第一个位置 i，使得 s[i] < s[i+1]
  2. 从右向左找第一个比 s[i] 大的字符：找到位置 j，使得 s[j] > s[i]
  3. 交换并反转：交换 s[i] 和 s[j]，然后将 i+1 到末尾的部分反转

为什么会这样？你想想看，我们要找「下一个」更大的排列，就要尽量不动高位，只调整低位。找到降序对，说明这里可以变大；找到比 s[i] 大的最小字符，保证变大的幅度最小；反转后面的部分，是因为后面原本是降序，反转后变成升序，就是最小的排列。

来看代码实现：

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

// 交换两个字符
void swap(char *a, char *b) {
    char temp = *a;
    *a = *b;
    *b = temp;
}

// 反转字符串从 start 到 end 的部分
void reverse(char *s, int start, int end) {
    while (start < end) {
        swap(&s[start], &s[end]);
        start++;
        end--;
    }
}

// 寻找下一个字典序排列
// 如果存在下一个排列，返回 true；否则返回 false
bool next_permutation(char *s) {
    int len = strlen(s);
    if (len <= 1) return false;
    
    // 第一步：从右向左找第一个降序对
    int i = len - 2;
    while (i >= 0 && s[i] >= s[i + 1]) {
        i--;
    }
    
    // 如果没找到，说明已经是最大排列
    if (i < 0) {
        return false;
    }
    
    // 第二步：从右向左找第一个比 s[i] 大的字符
    int j = len - 1;
    while (s[j] <= s[i]) {
        j--;
    }
    
    // 第三步：交换并反转
    swap(&s[i], &s[j]);
    reverse(s, i + 1, len - 1);
    
    return true;
}

int main() {
    char str[] = "abc";
    
    printf("字符串 \"%s\" 的所有字典序排列：\n", str);
    
    // 先排序，确保从最小排列开始
    // 这里假设输入已经是升序排列
    
    do {
        printf("  %s\n", str);
    } while (next_permutation(str));
    
    return 0;
}

输出结果：

字符串 "abc" 的所有字典序排列：
  abc
  acb
  bac
  bca
  cab
  cba

关键点：

  • 输入字符串必须是升序排列的，才能得到所有排列
  • 如果返回 false，说明已经是最大排列（完全降序）
  • 时间复杂度 O(n)，空间复杂度 O(1)

24.5 处理重复字符的情况

如果字符串里有重复字符，比如 "aab"，上面的算法依然有效。它会自动跳过重复的排列。

输入 "aab" 的排列：
  aab
  aba
  baa

为什么不会出现重复？因为算法在找「第一个比 s[i] 大的字符」时，用的是 s[j] <= s[i] 这个条件。遇到相等的字符会跳过，这样就保证了不会产生重复的排列。

小技巧：如果你需要生成所有排列，可以先对字符串排序（用 qsort），然后不断调用 next_permutation 直到返回 false。这样保证从最小排列开始，到最大排列结束。

24.6 实际项目中的应用

我在做电商后台的时候，遇到过这样一个需求：商品 SKU 有多种属性组合，需要按字典序列出所有可能的组合。比如颜色有红、蓝，尺寸有 S、M、L，需要生成 "红S"、"红M"、"红L"、"蓝S"、"蓝M"、"蓝L" 这样的顺序。

当时就是用 next_permutation 的思路，只不过把字符换成了属性值数组。嗯，这个算法在组合数学和密码学里也很常见。

24.7 本章小结

字典序排序和下一个排列，这两个知识点是字符串处理的基石。我建议你记住以下几点：

  • 排序用 qsort + strcmp，别自己写排序
  • 注意大小写问题，根据需求选择是否忽略大小写
  • next_permutation 的三步法：找降序对、找交换位、反转
  • 处理重复字符时，条件判断要用 <= 而不是 <

这些技巧我在多个项目里反复用过，每次都能派上用场。你可以在自己的代码库里封装一个通用的 next_permutation 函数，以后遇到类似需求直接拿来用。

字典序处理核心知识体系 字符串输入 字符串排序 qsort + strcmp / strcasecmp 下一个排列 next_permutation 算法 升序 / 降序 ASCII 码比较 忽略大小写 tolower / toupper 三步法：找→找→交换反转 O(n) 时间复杂度 输出：有序字符串序列 / 下一个排列结果

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →