C 语言实例 – 字符串排序（千字长文）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

字符串在 C 语言中的存储与特性

在 C 语言中，字符串本质上是字符数组的特殊形式。每个字符以 char 类型存储，末尾用空字符 \0 标记结束。这种设计如同一条项链：每个珠子（字符）按顺序排列，而最后一个珠子是“结束标记”，表示项链的终点。例如，字符串 "hello" 在内存中实际占用 6 个字节，包括 'h', 'e', 'l', 'l', 'o', '\0'。

理解这一特性对排序至关重要。当操作字符串时，必须确保：

1. 数组空间足够容纳字符串及结束符；
2. 操作不会越界修改内存；
3. 排序时需比较完整字符串而非单个字符。

字符串排序的核心问题与挑战

指针与内存操作的复杂性

C 语言的字符串操作依赖指针和数组下标，这要求开发者对内存布局有清晰认知。例如，比较两个字符串时，不能直接比较它们的地址（指针值），而需逐个字符对比，直到找到不同处或遇到结束符。

排序算法的选择

排序算法需兼顾时间复杂度与实现难度。常见的选择包括：

• 冒泡排序：简单易懂，但效率较低（O(n²))，适合小型数据集；
• 快速排序：高效（平均 O(n log n))，但实现较复杂，需递归或栈支持；
• 标准库函数 qsort：利用库函数简化代码，但需自定义比较函数。

实战案例：实现字符串数组排序

案例背景

假设需要对学生成绩记录进行排序，数据结构如下：

struct Student {  
    char name[50];  
    int score;  
};  

目标是按学生成绩从高到低排序，或按姓名字母顺序排列。

方法一：冒泡排序实现

冒泡排序通过相邻元素比较逐步“冒泡”最大值到数组末端。以下是按字符串长度排序的示例：

代码实现

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

void bubble_sort(char *arr[], int n) {  
    for (int i = 0; i < n-1; i++) {  
        for (int j = 0; j < n-i-1; j++) {  
            // 比较两个字符串的长度  
            if (strlen(arr[j]) > strlen(arr[j+1])) {  
                // 交换指针引用的字符串  
                char *temp = arr[j];  
                arr[j] = arr[j+1];  
                arr[j+1] = temp;  
            }  
        }  
    }  
}  

int main() {  
    char *words[] = {"apple", "banana", "cherry", "date"};  
    int size = sizeof(words)/sizeof(words[0]);  
    bubble_sort(words, size);  

    printf("Sorted by length:\n");  
    for (int i = 0; i < size; i++) {  
        printf("%s\n", words[i]);  
    }  
    return 0;  
}  

关键点解析

1. 指针数组：char *arr[] 存储字符串的指针，而非直接存储字符串内容；
2. 长度比较：strlen() 返回字符串长度，但需注意多次调用可能影响效率；
3. 交换逻辑：仅需交换指针引用，而非复制整个字符串，节省内存。

方法二：快速排序优化

快速排序通过分治策略提升效率。以下实现按字符串字典序排序：

代码实现

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

void quick_sort(char *arr[], int low, int high) {  
    if (low < high) {  
        int pivot = partition(arr, low, high);  
        quick_sort(arr, low, pivot - 1);  
        quick_sort(arr, pivot + 1, high);  
    }  
}  

int partition(char *arr[], int low, int high) {  
    char *pivot = arr[high];  
    int i = low - 1;  

    for (int j = low; j < high; j++) {  
        // 使用 strcmp() 比较字典序  
        if (strcmp(arr[j], pivot) <= 0) {  
            i++;  
            char *temp = arr[i];  
            arr[i] = arr[j];  
            arr[j] = temp;  
        }  
    }  
    char *temp = arr[i+1];  
    arr[i+1] = arr[high];  
    arr[high] = temp;  
    return i + 1;  
}  

int main() {  
    char *words[] = {"banana", "apple", "cherry", "date"};  
    int size = sizeof(words)/sizeof(words[0]);  
    quick_sort(words, 0, size - 1);  

    printf("Sorted alphabetically:\n");  
    for (int i = 0; i < size; i++) {  
        printf("%s\n", words[i]);  
    }  
    return 0;  
}  

关键点解析

1. strcmp() 函数：返回负数表示第一个字符串“小于”第二个，适合字典序比较；
2. 递归分治：通过基准值划分区间，减少重复比较次数；
3. 空间复杂度：递归可能导致栈溢出，需注意数据规模。

方法三：使用标准库 qsort

C 标准库提供 qsort 函数，通过回调函数实现灵活排序：

代码实现

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

// 自定义比较函数：按字符串长度升序  
int compare_length(const void *a, const void *b) {  
    const char *str_a = *(const char *const *)a;  
    const char *str_b = *(const char *const *)b;  
    return strlen(str_a) - strlen(str_b);  
}  

int main() {  
    char *words[] = {"cherry", "date", "apple", "banana"};  
    int size = sizeof(words)/sizeof(words[0]);  

    // 使用 qsort 排序  
    qsort(words, size, sizeof(char *), compare_length);  

    printf("Sorted by length:\n");  
    for (int i = 0; i < size; i++) {  
        printf("%s\n", words[i]);  
    }  
    return 0;  
}  

关键点解析

1. 回调函数设计：compare_length 必须符合 int (*)(const void*, const void*) 签名；
2. 类型转换：const void * 需强制转换为 char ** 以访问字符串指针；
3. 效率优势：qsort 内部优化，适合大规模数据。

实际应用场景与扩展

场景一：学生成绩排序

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

#define MAX_STUDENTS 100  

typedef struct {  
    char name[50];  
    int score;  
} Student;  

// 按成绩降序比较  
int compare_score(const void *a, const void *b) {  
    Student *s1 = (Student *)a;  
    Student *s2 = (Student *)b;  
    return s2->score - s1->score;  
}  

int main() {  
    Student students[MAX_STUDENTS];  
    int count = 0;  

    // 假设已输入学生数据  
    // ...  

    qsort(students, count, sizeof(Student), compare_score);  
    // 输出排序后的结果  
    return 0;  
}  

场景二：动态字符串数组排序

#include <stdlib.h>  

void sort_dynamic_array(char **arr, int size) {  
    qsort(arr, size, sizeof(char *), compare_length);  
}  

常见错误与调试技巧

1. 未分配足够内存：字符串操作时需预留 \0 的空间；
2. 指针越界：避免访问超出数组范围的字符；
3. 比较函数逻辑错误：例如混淆 a 和 b 的顺序，导致排序方向反向。

总结与进阶方向

通过本文，读者掌握了：

• 字符串在 C 语言中的存储与操作特点；
• 三种排序算法的实现与适用场景；
• 标准库 qsort 的高效使用方法；
• 实际案例中的复杂数据结构排序技巧。

进阶学习可探索：

• 更高效的排序算法（如归并排序）；
• 多条件排序（如先按分数排序，再按姓名排序）；
• 内存优化技巧（如避免重复计算字符串长度）。

掌握字符串排序不仅是算法能力的体现，更是解决实际问题（如数据管理、文本处理）的基础。通过实践不同场景的案例，开发者能逐步提升 C 语言编程的综合能力。