Lesson 44: qsort 泛型排序

练习任务

难度：中

调用 C 标准库的 qsort 完成两种类型的排序任务，掌握 void* 泛型机制与 comparator 函数指针的核心用法：

int 数组排序：使用已提供的 cmp_int 比较器（一级指针解引用）
字符串数组排序 char *names[]：你需要自行实现 cmp_str 比较器 + qsort 调用（二级指针解引用——本课核心难点）

int cmp_str(const void *a, const void *b);  /* ← 你来实现 */

程序从标准输入读取一行，第一个 token 是模式（"int" 或 "str"），后续 token 是待排序的数据：

输入: "int 5 3 8 1 4\n"          → ints: 1 3 4 5 8
输入: "str cherry apple banana\n" → strings: apple banana cherry

提示：qsort 的 comparator 总是接收数组中两个元素的地址。int 数组的元素就是 int → 地址是 int* → 一级指针。但字符串数组的元素是 char*（指针）→ 地址是 char** → 二级指针！这个"级数差"是本课最重要的陷阱——绝大多数同学的 bug 都犯在这里。请先画内存图，再动笔写代码。

核心知识点

qsort 泛型三要素：void *base + size_t size + int (*cmp)(const void*, const void*) 构成了 C 语言最经典的泛型编程模式——编译期类型擦除，运行期通过 cmp 恢复类型信息
cmp 参数的本质：qsort 传给 cmp 的是元素的地址（指针的指针）。int 数组 → cmp 收到 const int*（一级）；char*[] 数组 → cmp 收到 const char**（两级！）
cmp_str 的死亡陷阱：必须写 *(const char **)a（两级解引用拿 char*），绝对不能写成 (const char*)a——后者把指针值的字节当成字符串来读，必然段错误或乱序
泛型的前提与代价：void* 擦除类型信息，size 提供单位大小，cmp 在运行时恢复类型知识——这是没有模板的年代里 C 实现"一套代码，多种类型"的手段
指针级数速查表：掌握常见数组类型在 qsort cmp 中需要的解引用级数——int → int* / char*[] → char** / struct node*[] → struct node**
glibc qsort = introsort：以快排为主，三数取中选 pivot；递归深度超过 2log₂n 时自动切换堆排防退化；子问题小于阈值时切换插入排序
C qsort vs C++ std::sort：void* + 函数指针（编译期无类型检查、运行时回调开销） vs 模板特化（编译期内联展开、完全类型安全）
qsort 的局限性：C 标准不保证稳定性；函数指针无法内联，每次比较都有间接调用开销；不支持内联比较器

代码框架

44_qsort.c

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

/* 整数比较器 — 一级指针 */
int cmp_int(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

/* 字符串比较器 — 注意二级指针！ */
int cmp_str(const void *a, const void *b) {
#error TODO: Finish this exercise. Run "clings hint" for help.
    /* 先把 void* 强转为 const char**，再解引用得到 const char*
     * sa = *(const char **)a
     * sb = *(const char **)b */

    /* strcmp(sa, sb) 比较两个字符串 */
}

int main(void) {
    char line[512];
    fgets(line, sizeof(line), stdin);
    int len = strlen(line);
    if (len > 0 && line[len - 1] == '\n') line[len - 1] = '\0';

    /* 第一个 token 是模式："int" 或 "str" */
    char *mode = strtok(line, " ");

#error TODO: Finish this exercise. Run "clings hint" for help.
    /* 若 mode == "int":
     *   解析后续数字到 int arr[64]
     *   qsort(arr, n, sizeof(int), cmp_int)
     *   打印 "ints: N1 N2 ..."
     *
     * 若 mode == "str":
     *   将后续每个 token 的地址存入 char *strs[64]（不需要拷贝！直接用 token 指针）
     *   qsort(strs, n, sizeof(char *), cmp_str)
     *   打印 "strings: S1 S2 ..." */

    return 0;
}

框架中隐含的核心问题：

为什么 cmp_int 里强转 const int* 就行，而 cmp_str 必须是 const char**？
qsort(strs, n, sizeof(char *), cmp_str) — 为什么 sizeof(char *) 而不是 strlen？
字符串数组的元素不是"字符"总是"指针"——这个认知决定了整个设计的正确性

TIP

先不要看参考解答。画一张内存图：char *strs[] = {"cherry", "apple", "banana"} 这三个元素在栈上长什么样，每个元素的值指向哪里，qsort 传给 cmp 的是什么地址？把这张图画清楚，代码自然就写出来了。

深度讲解

1. qsort 签名解析 —— 泛型三要素

标准库 qsort 的完整签名：

void qsort(void *base, size_t n, size_t size,
           int (*cmp)(const void *, const void *));

四个参数各自承担不同的职责：

参数	类型	含义	int 数组示例	字符串数组示例
`base`	`void *`	数组首地址（擦除类型）	`arr`	`strs`
`n`	`size_t`	元素个数	`5`	`3`
`size`	`size_t`	单个元素字节数	`sizeof(int)` = 4	`sizeof(char *)` = 8
`cmp`	函数指针	比较两个元素的规则	`cmp_int`	`cmp_str`

            qsort 的泛型机制
            ┌──────────────────────────────────────┐
            │                                      │
            │  void *base  ─→  不知道什么类型       │
            │  size_t size ─→  但知道每个元素多大    │
            │  cmp 函数    ─→  由调用者告诉"怎么比" │
            │                                      │
            │  ≈ 把类型信息拆成两块：                │
            │     size 负责"移动"（swap 时用）       │
            │     cmp  负责"比较"（分大小靠它）       │
            │                                      │
            └──────────────────────────────────────┘

2. cmp 接收的到底是什么？

这是本课最重要的认知起点。qsort 在内部比较两个元素时，调用的是：

cmp(&arr[i], &arr[j])   // 传入的是元素的地址！

2.1 int 数组：简单的一级指针

int arr[] = {5, 3, 8, 1, 4};
qsort(arr, 5, sizeof(int), cmp_int);

qsort 工作时传给 cmp 的参数：

&arr[0], &arr[1], &arr[2], ... → 类型都是 int*

所以 cmp_int 的实现非常简单：

int cmp_int(const void *a, const void *b) {
    const int *pa = (const int *)a;   // void* → int*
    const int *pb = (const int *)b;   // void* → int*
    return *pa - *pb;                  // 解引用一次 → 拿到 int 值
}

内存视角 — int 数组：
  arr[0]=5    arr[1]=3    arr[2]=8    arr[3]=1    arr[4]=4
  ┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
  │  5   │    │  3   │    │  8   │    │  1   │    │  4   │  ← sizeof(int)=4
  └──────┘    └──────┘    └──────┘    └──────┘    ───────┘
  ↑ 0x100      ↑ 0x104      ↑ 0x108      ↑ 0x10C      ↑ 0x110
  &arr[0]      &arr[1]      &arr[2]      &arr[3]      &arr[4]
  类型=int*    类型=int*    类型=int*    类型=int*    类型=int*

qsort 传给 cmp 的是 0x100, 0x104, ... (int*)
cmp 强转 void* → int*，解引用再拿到 int 值 ✓

2.2 字符串数组：致命的二级指针

现在考虑字符串数组：

char *strs[] = {"cherry", "apple", "banana"};
qsort(strs, 3, sizeof(char *), cmp_str);

这里 strs 的每个元素是什么？是 char*——一个指向字符串的指针。

qsort 传给 cmp 的是什么？元素的地址 &strs[i]——类型是 char**！

完整内存模型：
                栈上的 strs 数组                    堆 (.rodata) 上的字符串常量
地址 0xA00: ┌──────────────┐
            │    0x200     │────────────────────→ ┌───────┬───┬───┬───┬───┬────
            └──────────────┘  strs[0]              │ c │ h │ e │ r │ r │ y │\0 │
地址 0xA08: ┌──────────────┐                      └───┴───┴───┴───┴───┴───┴───┘
            │    0x300     │────────────────────→ ┌───────┬───┬───┬───┬───┐
            └──────────────┘  strs[1]              │ a │ p │ p │ l │ e │\0 │
地址 0xA10: ┌──────────────┐                      └───────┴───┴───┴───┴───┘
            │    0x400     │────────────────────→ ┌───┬───┬───┬───┬───┬───┬───┐
            └──────────────┘  strs[2]              │ b │ a │ n │ a │ n │ a │\0 │
                                                   └───────┴───┴───┴───┴───┴───┘

qsort 传给 cmp 的是元素地址：
  &strs[0] = 0xA00  → 类型是 char**  (这个地址上存储的是 char* 值 0x200)
  &strs[1] = 0xA08  → 类型是 char**  (这个地址上存储的是 char* 值 0x300)
  &strs[2] = 0xA10  → 类型是 char**  (这个地址上存储的是 char* 值 0x400)

关键洞察：a 指向的是栈上的某个 strs[i]，而 strs[i] 本身是一个 char*。所以 a 是 char**——两级指针。

3. cmp_str 的正确写法与死亡陷阱

3.1 正确写法 —— 两级解引用

/* ✅ 正确版本 */
int cmp_str(const void *a, const void *b) {
    const char *s1 = *(const char **)a;   // a 是 char**，解引用得到 char*
    const char *s2 = *(const char **)b;   // b 是 char**，解引用得到 char*
    return strcmp(s1, s2);                 // 正常比较两个字符串
}

/* 等价的一行版 */
int cmp_str(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

逐步拆解 *(const char **)a：

步骤 1: a 的值是什么？
  → a = &strs[i] = 某个栈地址（如 0xA00）
  → a 是 void*，实际指向一个 char* 变量

步骤 2: (const char **)a 做了什么？
  → 告诉编译器："把 a 当成指向 const char* 的指针"
  → 现在类型是 const char**，编译器知道 *a 应该读出 8 字节的 char* 值

步骤 3: *(const char **)a 得到了什么？
  → 解引用：读取 0xA00 处的 8 字节 = strs[i] = 0x200
  → 这就是指向字符串 "cherry" 的 char* 指针！

步骤 4: strcmp(s1, s2)
  → s1 = 0x200 → "cherry"
  → s2 = 0x300 → "apple"
  → strcmp 正常工作 ✅

IMPORTANT

核心规律：qsort 传给 cmp 的是元素的地址，所以 cmp 接收的 void* 总是比元素类型多一级指针。元素是什么类型，就强转为什么类型的指针，然后解引用一次。这就是"万能模板"。

3.2 死亡陷阱 —— `(const char *)a`

/* ❌ 错误写法 —— 考场上最常见的 bug */
int cmp_str_broken(const void *a, const void *b) {
    return strcmp((const char *)a, (const char *)b);
}

CAUTION

这是本课最常见的严重错误——编译器不会有任何警告，但运行时必出错。

逐步拆解这个错误：

qsort 传 a = &strs[0] = 0xA00

错误的转换路径：
  (const char *)a = (const char *)0xA00 = 0xA00
  → strcmp(0xA00, ...) 
  → 把地址 0xA00 处的字节当成字符串开始读取！

0xA00 处存储的是什么？
  → 不是字节串，而是 strs[0] 的内容：指针值 0x200
  → 在 64 位系统上，0xA00 处的 8 字节是：00 02 00 00 00 00 00 00 (小端)
  
strcmp 从 0xA00 开始读：
  → 第 0 字节: 0x00 → 认为遇到了 '\0'！
  → 返回空字符串 ""
  → 另一个参数同理 → 两个"空串"比较 → 结果为 0
  → qsort 认为所有元素相等 → 不交换 → 输出乱序！

内存视角 — 为什么 (const char*)a 是灾难：

地址 0xA00: ┌────┬────┬────┬────┬────┬────┬────┬────┐
内容是        │ 00 │ 02 │ 00 │ 00 │ 00 │ 00 │ 00 │ 00 │  ← 0x200 的小端字节
strs[0] 的值  └────┴────┴────┴────┴────┴────┴────┴────┘
              ↑                                  ↑
              │                                  │
     strcmp 从这开始读                第一个字节就是 0x00！
     → "空串"                        → strcmp 返回 0
                                     → 排序完全乱掉！

正确做法 *(const char**)0xA00：
  → 读取 8 字节：00 02 00 00 00 00 00 00
  → 组装成 char* 值：0x200
  → 从 0x200 开始读字符串："cherry" ✅

关键区分：

写法	做了什么	得到什么	结果
`(const char *)a`	把 a 的地址值当字符串起始地址	a 指向的内存位置上的字节（恰好是 `char*` 值的二进制表示）	读到指针值的低字节 → 大概率立即遇 `'\0'` → 段错误或乱序
`(const char *)a`	先把 a 视为 `char*`，然后解引用读出 `char` 值，再把这个值当字符串起始地址	真正的字符串指针	正常工作 ✅

4. void* + size + cmp = C 语言的"前模板"泛型

C 语言在 C++ 模板出现之前就用这套机制实现了泛型编程。其本质是：

                    编译期                   运行期
                  ┌────────┐            ┌──────────┐
    类型信息:      │ 完全擦除  │  ──void*──→  │ cmp 函数恢复  │
                  └────────┘            └──────────┘

    尺寸信息:      │ 编译期确定  │  ──sizeof──→  │ swap/memcpy 使用  │
                  └──────────┘            └──────────┘

    比较逻辑:      │ 用户提供函数指针  │  ──cmp──→  │ 回调调用  │
                  └──────────┘            └──────────┘

qsort 内部不关心元素类型。它只做三件事：

/* qsort 内部署伪代码 */
void qsort(void *base, size_t n, size_t size,
           int (*cmp)(const void*, const void*)) {
    // 1. Compare: 调用 cmp，传入两个元素的地址
    if (cmp(element_addr(i), element_addr(j)) > 0)
        // 2. Swap: 用 memcpy 交换两个 size 字节的元素
        swap(element_addr(i), element_addr(j), size);
    // 3. Recurse: 对左右子数组递归
}

qsort 的类型擦除与恢复机制：

    int arr[] = {5, 3, 8};          char *strs[] = {"c", "a", "b"};
    ┌──────────────┐                ┌──────────────┐
    │ sizeof(int)  │                │ sizeof(char*)│
    │     = 4      │                │     = 8      │
    └──────┬───────┘                └──────┬───────┘
           │                               │
           ▼                               ▼
    ┌──────────────────────────────────────────┐
    │              qsort (void*)                │
    │                                          │
    │   while (sorting) {                       │
    │     cmp(&left, &right);  // 不知道类型！  │
    │     swap(size);          // 只知道大小！  │
    │   }                                      │
    │                                          │
    │   泛型的代价：                             │
    │   - 编译期：类型安全 = 零                 │
    │   - 运行期：每次比较都有函数调用开销       │
    │   - 错误：void* 转换错误 → UB 无警告      │
    └──────────────────────────────────────────┘

NOTE

这是"结束上的泛型"而非"类型系统上的泛型"。C++ 模板在编译期为每种类型生成独立代码（编译期多态），而 qsort 只有一个实现，在运行期通过函数指针调度（运行期多态）。这正是 C 和 C++ 在泛型理念上的根本分歧。

5. 指针级数速查表

掌握这份速查表，任何数组类型都能写出正确的 cmp：

数组类型	元素类型	sizeof(元素)	qsort 传的地址类型	cmp 强转为	解引用得到	解引用次数
`int arr[]`	int	4	`int*`	`const int*`	int	1 次
`double arr[]`	double	8	`double*`	`const double*`	double	1 次
`char arr[]`	char	1	`char*`	`const char*`	char	1 次
`long arr[]`	long	8	`long*`	`const long*`	long	1 次
*`char arr[]`**	char*	8	`char`**	`const char`**	char*	2 次
`struct node *arr[]`	struct node*	8	`struct node**`	`const struct node**`	struct node*	2 次
`int *arr[]`	int*	8	`int**`	`const int**`	int*	2 次

记忆口诀：

qsort 总是传"元素的地址"
元素是什么类型，地址就比它多一级指针
int 数组 → 元素=int → 元素地址=int* → cmp 解引用 1 次
char* 数组 → 元素=char* → 元素地址=char** → cmp 解引用 2 次

cmp 万能模板

int cmp(const void *a, const void *b) {
    const ELEMENT_TYPE *pa = (const ELEMENT_TYPE *)a;  // 强转
    const ELEMENT_TYPE *pb = (const ELEMENT_TYPE *)b;
    return COMPARE(*pa, *pb);                          // 解引用 + 比较
}

把 ELEMENT_TYPE 换成数组的元素类型即可：

int 数组：ELEMENT_TYPE = int → const int *pa = a
char* 数组：ELEMENT_TYPE = char* → const char **pa = a

三级指针什么时候出现？

char **argv[] = {...};  // 字符串数组的数组

此时元素是 char** → 元素地址是 char*** → cmp 需要解引用 3 次。不过 qsort 极少用到三级指针，知道这个递推规律即可。

6. qsort 内部实现 —— introsort

glibc 中的 qsort 并非简单的快速排序，而是 introsort（内省排序）——一种混合排序算法：

            ┌──────────────────────────────────┐
            │         qsort (introsort)          │
            │                                    │
            │  主策略: 快速排序 (Quick Sort)       │
            │    ↓ 递归深度 > 2·log₂n            │
            │  切换: 堆排序 (Heap Sort)            │
            │    ↓ 子数组 ≤ 阈值 (通常 4~16)       │
            │  切换: 插入排序 (Insertion Sort)     │
            │                                    │
            └──────────────────────────────────┘

三层策略的原因：

策略	时间复杂度	适用场景	为什么
快速排序	O(n log n) 平均	主排序算法	缓存友好，实际最快
堆排序	O(n log n) 保证	快排退化时	防 O(n²) 最坏情况
插入排序	O(n²) 但常数极小	小数组	小 n 时比快排快

/* introsort 核心逻辑（伪代码） */
void introsort(void *base, size_t n, size_t size,
               int (*cmp)(const void*, const void*),
               int depth_limit) {

    if (n <= INSERTION_THRESHOLD) {       // 通常 4~16
        insertion_sort(base, n, size, cmp);
        return;
    }

    if (depth_limit == 0) {               // 递归太深！
        heapsort(base, n, size, cmp);     // 切换堆排防 O(n²)
        return;
    }

    // 三数取中选 pivot
    void *pivot = median_of_three(base, n, size, cmp);
    // 分区
    size_t left_n = partition(base, n, size, cmp, pivot);

    introsort(base, left_n, size, cmp, depth_limit - 1);
    introsort(base + left_n * size, n - left_n, size, cmp, depth_limit - 1);
}

这就是为什么 qsort 在实际使用中几乎不会出现 O(n²) 退化——堆排序兜底保证了最坏情况 O(n log n)。

7. C qsort vs C++ std::sort

cpp

// C: void* 泛型
int arr[] = {5, 3, 8, 1, 4};
qsort(arr, 5, sizeof(int), cmp_int);

// C++: 模板泛型
std::vector<int> v = {5, 3, 8, 1, 4};
std::sort(v.begin(), v.end());  // 甚至不需要传比较器！

维度	C qsort	C++ std::sort
泛型方式	`void*` + 函数指针	模板特化（编译期多态）
类型安全	编译期不检查 — 传错类型无警告	编译期完全检查 — 类型不匹配 → 编译错误
比较器开销	每次比较时通过函数指针间接调用	模板展开后，比较器内联为直接代码
代码膨胀	只有一份 `qsort` 实现	每种类型生成一份 `std::sort<Type>`
可内联性	函数指针不能被内联（通常）	模板特化后完全内联
速度	较慢（函数调用开销）	更快（内联 + 编译期优化）
排序对象	仅 C 数组（连续内存）	任意迭代器范围（数组、vector、list...）
默认比较	无（必须提供 cmp）	`operator<` 自动推导
稳定性	不保证	`std::stable_sort` 提供稳定版本

性能差异的本质：
                                      
  C qsort:                            C++ std::sort:
  ┌─────────┐                        ┌─────────┐
  │ qsort() │  ← 一份实现             │sort<int>│ ← 为 int 特化的版本
  │   │     │                        │   │     │   比较器内联在此！
  │   ▼     │                        │   ▼     │
  │ cmp()   │  ← 每次通过指针调用     │ 直接比较  │  ← 零开销抽象
  └─────────┘                        └─────────┘
  
  cmp 函数指针 → 无法内联              模板展开 → cmp 内容直接收入
  → 约 2-5x 比较开销                  → 与手写排序一样快

NOTE

虽然 C++ std::sort 更快，但 C qsort 在绝大多数场景下性能差距可以忽略——尤其是 introsort 的优化和现代 CPU 的分支预测已经大幅弥合了函数指针调用的开销。不要因为"qsort 比 std::sort 慢"就避免使用它——理解其机制比纠结微小性能差更重要。

8. 常见错误与修复

错误	后果	正确做法
`cmp_str` 用 `(const char *)a`	把指针值字节当字符串读 → 段错误/乱序	`(const char *)a`
qsort 的 size 参数写成 `strlen` 而非 `sizeof(char *)`	交换时只拷贝部分字节 → 指针被截断 → 悬垂	`sizeof(char *)`
`cmp_int` 的 `a - b` 溢出	INT_MIN - 1 溢出为 INT_MAX → 结果反了	用 if-else 比较：`if(pa < pb) return -1;`
忘记 `#include <stdlib.h>`	qsort 未声明 → 编译器警告/隐式声明	必须 include
cmp 参数忘记 `const`	编译器警告 `discards const qualifier`	`const void *`
字符串数组 `qsort` 写成 `sizeof(strs[0])` 但 strs 是局部拷贝	token 生命周期问题	本练习直接用 strtok 返回的指针即可

参考解答

练习：qsort 完整实现 (cmp_int + cmp_str)

solution_44_qsort.c

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

/* 整数比较器 — 一级指针：a 是 int*，解引用得到 int */
int cmp_int(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

/* 字符串比较器 — 二级指针！a 是 char**，解引用得到 char* */
int cmp_str(const void *a, const void *b) {
    const char *s1 = *(const char **)a;
    const char *s2 = *(const char **)b;
    return strcmp(s1, s2);
}

int main(void) {
    char line[512];
    fgets(line, sizeof(line), stdin);
    int len = strlen(line);
    if (len > 0 && line[len - 1] == '\n') line[len - 1] = '\0';

    char *mode = strtok(line, " ");

    if (strcmp(mode, "int") == 0) {
        int arr[64], n = 0;
        char *tok;
        while ((tok = strtok(NULL, " ")) != NULL)
            arr[n++] = atoi(tok);

        qsort(arr, n, sizeof(int), cmp_int);

        printf("ints:");
        for (int i = 0; i < n; i++)
            printf(" %d", arr[i]);
        printf("\n");
    } else if (strcmp(mode, "str") == 0) {
        char *strs[64];
        int n = 0;
        char *tok;
        while ((tok = strtok(NULL, " ")) != NULL)
            strs[n++] = tok;  /* 直接用 token 指针，不需要拷贝 */

        qsort(strs, n, sizeof(char *), cmp_str);

        printf("strings:");
        for (int i = 0; i < n; i++)
            printf(" %s", strs[i]);
        printf("\n");
    }

    return 0;
}

核心设计决策：

*(const char **)a：两级解引用——这是整个练习的灵魂。a 是 char**（元素地址），解引用一次得到 char*（字符串指针），再传给 strcmp。
sizeof(char *)：告诉 qsort 每个元素是 8 字节（指针大小）。如果误写成 strlen(tok)，qsort 在 swap 时只交换部分字节，导致指针值被截断。
直接用 strtok 返回的指针：不需要 strdup 拷贝——strtok 返回指向 line 内部的指针，qsort 只交换指针值不改变字符串内容，token 的生命周期足够。

对照检查：cmp_str 用了 *(const char **)a 还是 (const char *)a？qsort 的 size 参数是 sizeof(char *) 还是其他值？字符串数组的元素是 char* 不是 char，你确认了吗？

课堂讨论

为什么 int 数组的 cmp_int 只需要一级指针，而字符串数组的 cmp_str 需要二级指针？本质区别是什么？
qsort 的排序结果稳定吗？如果不稳定，什么情况下会出问题？
如果写成 (const char *)a 而不是 *(const char **)a，编译器为什么不报错？运行时到底会发生什么？
如果要对 int *arr[]（整型指针数组）做排序，cmp 应该怎么写？解引用几次？
手写快排（Lesson 41）和 qsort 相比，各有什么优劣？什么时候应该自己写，什么时候用 qsort？
C 的 qsort 和 C++ 的 std::sort 在泛型实现上有何本质区别？

讨论答案

Q1: 为什么 int 数组一级、字符串数组二级？本质区别是什么？

本质区别在于数组元素本身是不是指针。

int 数组的元素就是 int（值类型），qsort 传元素地址 → int*，解引用一次得到 int
字符串数组的元素是 char*（指针类型），qsort 传元素地址 → char**，解引用一次得到 char*

简单说：qsort 总是传"元素的地址"。如果元素本身已经是指针，那么"元素的地址"就是指针的指针。

Q2: qsort 的排序结果稳定吗？

C 标准不保证 qsort 的稳定性。

glibc 实现中的行为因数据规模而异：

小数组（≤ 阈值）：可能使用归并排序或插入排序 — 实际上稳定
大数组：快速排序 — 不稳定

不要依赖这个行为。

如果你需要稳定排序（如先按分数排序再按姓名排序时保持分数相同者的原始顺序），应该：

使用 stable_sort（C++）
或者在 cmp 中加入次要比较键作为 tie-breaker

示例——不稳定排序的问题：

// 输入：[(Alice, 90), (Bob, 85), (Carol, 90)]
// 不稳定的排序按分排 → 可能输出 [(Bob, 85), (Carol, 90), (Alice, 90)]
// Alice 和 Carol 的相对顺序变了！

Q3: (const char*)a 为什么编译器不报错？

qsort 的参数类型是 const void *，强转为 const char * 是完全合法的 C 语言操作——编译器无法知道你"真正想要"的是 const char **。

运行时到底发生了什么：

qsort 传 a = &strs[0] = 0xA00
(const char *)a = (const char *)0xA00 = 0xA00

strcmp 从 0xA00 开始读字节：
  0xA00 处存储的是 strs[0] = 0x200（一个 8 字节指针）
  小端字节序：00 02 00 00 00 00 00 00
  第 0 字节 = 0x00 → strcmp 认为遇到了字符串结束符 '\0'
  → 返回空串 ""
  → 所有元素都"相等" → 排序无效果 → 输出乱序

更严重的情况：
  如果指针值的二进制表示中没有 0x00 字节
  → strcmp 会一直读到非法内存区域 → 段错误

Q4: int *arr[] 的 cmp 怎么写？

/* int *arr[] — 元素是 int*，所以元素地址是 int**，需要二级解引用 */
int cmp_int_ptr(const void *a, const void *b) {
    const int *pa = *(const int **)a;  // 解引用得到 int*
    const int *pb = *(const int **)b;
    return *pa - *pb;                   // 再解引用得到 int
}

这里实际有三级解引用操作（两次在 cmp 内部，一个是 qsort 传的 &）：

qsort 传 &arr[i] = int**
cmp 内部 *(const int **)a → int*
再 *pa → int

Q5: 手写快排 vs qsort，何时用哪个？

	手写快排	qsort
优点	可内联比较器（零函数调用开销）；类型安全（编译期检查）；可定制分区策略	经过工业级优化（introsort）；代码量少；不易出 bug
缺点	需要自己管理边界、优化 pivot 选择；容易写错	函数指针开销；类型不安全（void*）
何时选用	性能敏感场景；需要对排序过程做特殊控制	常规场景；原型验证；无特殊性能要求

一般建议：先用 qsort，profile 确认是瓶颈后再考虑手写。

Q6: C qsort vs C++ std::sort 泛型机制的本质区别

C qsort 是运行期泛型：

编译时类型信息被擦除（void*）
运行时通过函数指针恢复比较逻辑
代价：函数调用开销 + 无编译期类型检查

C++ std::sort 是编译期泛型：

模板在编译期为每种类型生成独立代码
比较器被内联展开，成为排序代码的一部分
代价：代码膨胀（每种类型一份排序函数）

本质上这是两种泛型编程范式的差异：C 选择一份"万能"实现 + 运行时分发；C++ 选择为每种类型生成最优实现。没有对错之分，只是设计哲学的差异。

课后练习

为 double 数组编写 cmp_double。仿照 cmp_int 的结构确实现一个对 double arr[] 排序的比较器。注意 double 的比较不能用 -（精度丢失），应该用 if-else 判断大小关系。
知识点提示：double 数组元素典型为 double → 元素地址类型为 double* → 解引用一个。比较逻辑：if (*a < *b) return -1; else if (*a > *b) return 1; else return 0;。
参考解答
cmp_double.c
c
```
int cmp_double(const void *a, const void *b) {
    double da = *(const double *)a;
    double db = *(const double *)b;
    if (da < db) return -1;
    if (da > db) return 1;
    return 0;
}

// 调用：qsort(arr, n, sizeof(double), cmp_double);
```
1
2
3
4
5
6
7
8
9
为什么不能用 return *(double*)a - *(double*)b？因为 double 相减的结果仍是 double，而 cmp 需要返回 int。隐式转换可能截断小数部分，导致相等的两个数被判为不等。

为 struct Student 数组编写 cmp_by_score。有结构体 struct Student { char name[32]; int score; };，按 score 降序排列。写出 cmp 函数并调用 qsort。

知识点提示：struct Student arr[] 的元素类型为 struct Student → 元素地址类型为 struct Student* → 解引用一次。比较时访问成员 .score。

参考解答

cmp_by_score.c

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

int cmp_by_score(const void *a, const void *b) {
    const struct Student *sa = (const struct Student *)a;
    const struct Student *sb = (const struct Student *)b;
    return sb->score - sa->score;  /* 降序：大的在前 */
}

// 调用：qsort(arr, n, sizeof(struct Student), cmp_by_score);

用 qsort 对命令行参数 argv 排序。main(int argc, char *argv[]) 中的 argv 本质上就是一个字符串数组。编写程序，用 qsort 对 argv[1] 开始的参数按字典序排序并输出。
知识点提示：argv 和 char *strs[] 是同一种结构——元素是 char*，qsort 的 cmp 需要二级索引用。注意 argv[0] 是程序名，排序从 argv[1] 开始。
参考解答
sort_args.c
c
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp_str(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main(int argc, char *argv[]) {
    if (argc <= 1) return 0;

    qsort(argv + 1, argc - 1, sizeof(char *), cmp_str);

    for (int i = 1; i < argc; i++)
        printf("%s\n", argv[i]);

    return 0;
}
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
运行示例：./a.out cherry apple banana → 输出 apple\nbanana\ncherry

修复溢出 bug：安全部 cmp_int。标准 cmp_int 使用 *a - *b 存在溢出风险（INT_MIN - 1 = INT_MAX，符号翻转）。请写一个安全的 cmp_int_safe，用 if-else 逻辑消除溢出可能。

知识点提示：INT_MIN - INT_MAX 在 32 位有符号整数中会发生回绕（wraparound）。虽然实际较少触发，但在做通用排序库时必须考虑。

参考解答

cmp_int_safe.c

#include <limits.h>

int cmp_int_safe(const void *a, const void *b) {
    int va = *(const int *)a;
    int vb = *(const int *)b;
    /* 避免减法溢出 */
    if (va < vb) return -1;
    if (va > vb) return 1;
    return 0;
    /* 或: return (va > vb) - (va < vb);  // 无分支版本，同样安全 */
}

减法版本的风险场景：

int a = INT_MIN;  // -2147483648
int b = 1;
int diff = a - b; // -2147483648 - 1 = INT_MAX（溢出为 2147483647 正数！）
// cmp 返回正数 → 认为 a > b → 排序错误！

// if-else 版本：INT_MIN < 1 → 正确返回 -1 ✅

用 qsort 实现部分排序：找前 k 小。给定 int 数组和 k 值，用 qsort 对整参数组排序后输出前 k 个元素。思考：如果只关心前 k 小，全排序是否浪费？（提示：与 Lesson 39 的堆排序联系）
知识点提示：Top-K 问题中，全排序复杂度 O(n log n)，而堆方案只需 O(n log k)。qsort 虽然方便，但在只需要前 k 个的场景下有更高效的算法。理解"工具选择取决于问题需求"。

参考资料

man qsort — Linux 手册页，包含完整的函数签名、参数说明和简单的使用示例
C 标准 §7.22.5 — qsort 函数的正式规范（搜索、排序工具函数章节）
Bentley & McIlroy (1993) "Engineering a Sort Function" — 描述了 qsort 工业级实现中的 pivot 选择、小数组优化等关键技术
Musser (1997) "Introspective Sorting and Selection Algorithms" — introsort 原始论文，解释了从快排切换到堆排的深度阈值选择
glibc qsort 源码 — 工业级 introsort 实现，包括三数取中、插入排序阈值等细节
Lesson 41: 快速排序 — 手写快排，理解 qsort 内部的分区 + 递归原理
Lesson 26: my_memcpy — void* 内存操作基础，理解 qsort 中 swap 的底层实现

"The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise." — Edsger W. Dijkstra

Lesson 44: qsort 泛型排序 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. qsort 签名解析 —— 泛型三要素 ​

2. cmp 接收的到底是什么？ ​

2.1 int 数组：简单的一级指针 ​

2.2 字符串数组：致命的二级指针 ​

3. cmp_str 的正确写法与死亡陷阱 ​

3.1 正确写法 —— 两级解引用 ​

3.2 死亡陷阱 —— (const char *)a ​

4. void* + size + cmp = C 语言的"前模板"泛型 ​

5. 指针级数速查表 ​

cmp 万能模板 ​

三级指针什么时候出现？ ​

6. qsort 内部实现 —— introsort ​

7. C qsort vs C++ std::sort ​

8. 常见错误与修复 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 44: qsort 泛型排序

练习任务

核心知识点

代码框架

深度讲解

1. qsort 签名解析 —— 泛型三要素

2. cmp 接收的到底是什么？

2.1 int 数组：简单的一级指针

2.2 字符串数组：致命的二级指针

3. cmp_str 的正确写法与死亡陷阱

3.1 正确写法 —— 两级解引用

3.2 死亡陷阱 —— `(const char *)a`

4. void* + size + cmp = C 语言的"前模板"泛型

5. 指针级数速查表

cmp 万能模板

三级指针什么时候出现？

6. qsort 内部实现 —— introsort

7. C qsort vs C++ std::sort

8. 常见错误与修复

参考解答

课堂讨论

讨论答案

课后练习

参考资料