第25章字符串的排序

课程目录第25章字符串的排序

第25章字符串的排序：对字符串数组按字典序排序（冒泡/快排）

字符串排序，说白了就是给一堆字符串排排队。按什么排？按字典序。什么是字典序？就是你在字典里查单词的顺序——先比第一个字符，再比第二个，以此类推。这个需求在实际开发中太常见了，我几乎每个项目都会遇到。

我记得刚入行那会儿，有个同事写了个通讯录程序，排序结果总是不对。他查了半天，最后发现是直接用 strcmp 的返回值当布尔值用了。嗯，这里面的坑，咱们今天一并说清楚。

25.1 字符串排序的本质

字符串排序和整数排序有什么不同？

整数排序，你直接比大小就行：if (a < b)。但字符串不行。你不能写 if (str1 < str2)，因为那比较的是指针地址，不是字符串内容。你得用 strcmp。

strcmp 的返回值规则：

返回负数：第一个字符串 < 第二个
返回0：相等
返回正数：第一个字符串 > 第二个

所以字符串排序的核心，就是把比较操作从 a < b 换成 strcmp(a, b) < 0。其他逻辑和整数排序一模一样。

关键点：字符串排序比较的是内容，不是地址。永远用 strcmp，别用 == 或 <。

25.2 冒泡排序实现字符串排序

冒泡排序的原理很简单：从头到尾，两两比较，把大的往后"冒"。重复 n-1 轮。

我当年第一次写字符串冒泡排序时，犯了个低级错误——直接交换字符串本身。字符串是字符数组，不能直接赋值。你得交换指针，或者用 strcpy 交换内容。交换指针更快，也更安全。

来看代码：

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

// 冒泡排序：对字符串数组按字典序排序
void bubble_sort_strings(char *arr[], int n) {
    int i, j;
    char *temp;

    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            // 比较相邻两个字符串
            if (strcmp(arr[j], arr[j + 1]) > 0) {
                // 交换指针
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    char *fruits[] = {"banana", "apple", "cherry", "date", "elderberry"};
    int n = sizeof(fruits) / sizeof(fruits[0]);
    int i;

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

    bubble_sort_strings(fruits, n);

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

    return 0;
}

输出结果：

排序前：
  banana
  apple
  cherry
  date
  elderberry

排序后：
  apple
  banana
  cherry
  date
  elderberry

小提示：交换指针比交换字符串内容快得多。如果字符串很长，用 strcpy 交换会非常慢。我建议你养成交换指针的习惯。

25.3 快速排序实现字符串排序

冒泡排序虽然简单，但效率低——O(n²)。数据量一大，你就等着卡死吧。我有个项目要排序几万个文件名，用冒泡排了快10秒，换成快排后不到0.1秒。差距就这么大。

C标准库提供了 qsort，可以直接用。你只需要写一个比较函数。

来看代码：

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

// 比较函数：用于 qsort
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() {
    char *fruits[] = {"banana", "apple", "cherry", "date", "elderberry"};
    int n = sizeof(fruits) / sizeof(fruits[0]);
    int i;

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

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

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

    return 0;
}

输出结果和冒泡一样。但效率天差地别。

注意：qsort 的比较函数参数是 const void *，你需要先转换成正确的指针类型。对于字符串数组，每个元素是 char *，所以参数是 char **。一定要解引用两次，否则你比较的是指针地址，不是字符串内容。

25.4 两种方法的对比

特性	冒泡排序	快速排序（qsort）
时间复杂度	O(n²)	O(n log n)
空间复杂度	O(1)	O(log n)（递归栈）
代码量	较多	较少（用库函数）
稳定性	稳定	不稳定
适用场景	小数据量（n < 100）	大数据量（n > 100）

我个人习惯：数据量小的时候用冒泡，图个简单；数据量大直接用 qsort，省心又高效。但如果你面试，面试官可能会让你手写快排，那就得自己实现了。

25.5 手写快速排序（进阶）

如果你想深入理解快排，可以自己实现一个。核心思想：选一个基准值，把小于基准的放左边，大于基准的放右边，然后递归处理左右两部分。

来看代码：

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

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

// 分区函数
int partition(char *arr[], int low, int high) {
    // 选最后一个元素作为基准
    char *pivot = arr[high];
    int i = low - 1;  // 小于基准的区域的右边界

    for (int j = low; j < high; j++) {
        // 如果当前元素小于等于基准
        if (strcmp(arr[j], pivot) <= 0) {
            i++;
            swap_strings(&arr[i], &arr[j]);
        }
    }
    // 把基准放到正确位置
    swap_strings(&arr[i + 1], &arr[high]);
    return i + 1;
}

// 快速排序
void quick_sort_strings(char *arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort_strings(arr, low, pi - 1);
        quick_sort_strings(arr, pi + 1, high);
    }
}

int main() {
    char *fruits[] = {"banana", "apple", "cherry", "date", "elderberry"};
    int n = sizeof(fruits) / sizeof(fruits[0]);
    int i;

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

    quick_sort_strings(fruits, 0, n - 1);

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

    return 0;
}

避坑指南：我曾经在分区函数里直接用 strcmp(arr[j], pivot) < 0，结果遇到重复字符串时死循环了。后来改成 <= 0 才解决。记住：快排的稳定性取决于你怎么处理相等的情况。

25.6 知识体系图

下面这张图展示了字符串排序的核心逻辑和两种实现路径：

25.7 避坑指南与经验总结

我做了这么多年C语言开发，在字符串排序上踩过的坑，今天全告诉你：

别直接比较字符串：if (str1 < str2) 比较的是指针地址，不是内容。永远用 strcmp。
交换指针，别交换内容：字符串可能很长，用 strcpy 交换效率极低。交换指针是 O(1) 操作。
注意 qsort 的比较函数签名：参数是 const void *，需要转换成 const char **，然后解引用两次。
处理大小写问题：字典序默认区分大小写。如果你需要不区分大小写的排序，用 strcasecmp（POSIX）或自己实现。
空字符串和 NULL 指针：排序前要检查。我曾经因为数组里有 NULL 指针，导致 strcmp 直接崩溃。血的教训。

警告：如果你用 qsort 排序一个很大的字符串数组（比如几十万个），递归深度可能很大，有栈溢出的风险。这时候可以考虑用迭代版本的快排，或者改用堆排序。

好了，字符串排序就讲到这里。记住核心：比较用 strcmp，交换用指针。这两种方法你都得会，面试常考。下次见。

📚 课程目录