这篇算是把我前面学的指针、字符串、排序几块东西串到一起了。第十四篇主题很明确先用快速排序把“分治”和“递归”讲透再回头用指针老老实实操作一维字符型数组最后让快排直接作用在字符数据和字符串数组上。老实说很多同学学快排的时候能看懂代码但自己手写就废原因多半是卡在“指针变量、数组名、内存布局”这些底层关系没理顺。这一篇就是想把这条线走通懂原理会写码踩过坑最后形成肌肉记忆。1. 快速排序分治思想和递归实现的完整拆解1.1 分治三步走选基准、分区间、递归快速排序的核心思想是“分治”。什么是分治就是把一个大问题拆成几个小问题小问题解决了大问题自然就解决了。排序一个数组我们不会直接想办法把整个数组排好而是先选一个基准元素一般叫 pivot然后把数组分成两半左边全是比基准小的右边全是比基准大的。这一步做完之后基准元素已经落在了它最终该待的位置上。举个例子数组 [6, 2, 8, 1, 9, 3]如果我选第一个元素 6 当基准经过一轮分区之后所有小于 6 的元素会挪到左边大于 6 的挪到右边结果是类似 [3, 2, 1, 6, 9, 8] 的状态。此时 6 的位置就是最终位置它左边不需要再关心大于 6 的元素右边也不用关心小于 6 的元素。接下来要做的事情非常机械对左边的 [3, 2, 1] 再重复“选基准、分区”对右边的 [9, 8] 也重复同样操作。当每个子区间只剩下一个元素或空区间时整个数组就是有序的了。这个“对子区间重复同样操作”的过程就是递归。递归写法有一个固定框架终止条件区间无效也就是 low high。递归分支先找到基准位置 pos然后分别对左右两个子区间调用排序函数。算法层面这很简单但它有几个细节决定性能基准怎么选、分区怎么实现、递归怎么return。后面几点我会逐个拆开讲。1.2 挖坑填数法经典分区代码一步步看网上快排代码五花八门但最经典、也最适合教学的是“挖坑填数法”。它不额外申请数组原地操作。基本流程是这样的先把基准值 pivot 取出来相当于在 low 位置挖了一个坑。然后右边的指针 high 往左走找到一个比 pivot 小的元素把它填进 low 位置的坑这样 high 位置又空出来一个坑。接着左边的指针 low 往右走找到一个比 pivot 大的元素把它填进 high 位置的坑。如此交替直到 low 和 high 相遇再把 pivot 放进这个相遇的位置。这个位置就是基准元素的最终下标。看代码更直观// 分区函数返回基准元素的最终下标 int partition(int arr[], int low, int high) { int pivot arr[low]; // 先取区间第一个元素作为基准 while (low high) { // 从右往左找第一个小于 pivot 的元素 while (low high arr[high] pivot) high--; arr[low] arr[high]; // 把这个小元素填到左边的坑 // 从左往右找第一个大于 pivot 的元素 while (low high arr[low] pivot) low; arr[high] arr[low]; // 把这个大元素填到右边的坑 } arr[low] pivot; // 最后把基准放回去 return low; // low high就是基准位置 } // 快速排序递归主体 void quick_sort(int arr[], int low, int high) { if (low high) { int pos partition(arr, low, high); quick_sort(arr, low, pos - 1); quick_sort(arr, pos 1, high); } }注意这版分区里的两个 while 循环判断条件里必须写low high这个前置条件不写的话比如数组里所有元素都比 pivot 大high 会一路减到越界那就出大问题了。很多人手写快排翻车就翻在这个细节上。还有一个容易绕晕的地方第一次执行arr[low] arr[high]时arr[low] 的值已经保存在 pivot 里了所以直接覆盖没问题。后面交替覆盖时也一样每次被覆盖的位置都是之前挖出来的“坑”值已经被保存过。最后把 pivot 放回去整个分区完成。1.3 复杂度与选基准的坑为什么有时候快排不快快速排序的平均时间复杂度是 O(n log n)在数据规模大、排列随机的情况下非常快。但它不是没有短板如果每次选基准都恰好选到区间的最小值或最大值那么分区严重失衡一个子区间基本空掉另一个子区间剩下 n-1 个元素递归深度变成 n时间复杂度退化成 O(n^2)。最典型的触发场景就是数据本身已经有序或者接近有序而你每次固定取第一个元素当基准。比如数组 [1, 2, 3, 4, 5]用上面的代码排第一次基准是 1右边全部大于 1分区后左边为空右边剩 [2, 3, 4, 5]第二次基准又是 2……这样一路下去性能跟冒泡排序差不多了。实际工程里通常用两种手段改善随机选择基准元素在 low 到 high 之间随机挑一个下标和 arr[low] 交换再走正常分区逻辑。三数取中比较 arr[low]、arr[mid]、arr[high] 三个位置的值把中间大小的那个换到 low 位置当基准。学习阶段用固定第一个元素当基准没问题目的是理解算法本身。但到了实战尤其数据量大时建议至少加上随机基准那一行。代码改动很小收益却很明显。// 取随机下标的简单写法实际要配合 srand 使用 int pivot_idx low rand() % (high - low 1); swap_int(arr[low], arr[pivot_idx]); int pivot arr[low];2. 指针操作一维字符型数组从内存布局到标准写法2.1 字符数组、字符串、指针三者的内存逻辑在C语言里字符数组和字符串的关系极其密切。定义一个char str[] hello其实是声明了一个包含 6 个元素的字符数组h、e、l、l、o、\0。那个\0是编译器自动补上的字符串结束标志。字符数组是内存里连续存放的一排字节数组名 str 代表这块内存的首地址但它本身是一个“常量地址”不能被赋值改变。再看指针变量char *p strp 存储的是那块内存的首地址。通过 p 能读取 str 的每一个字节也能通过 p 修改它们。区别在于p 是一个变量可以指向别的地方而数组名 str 只能指向数组起始位置不能自增自减不能重新赋值。为什么顺序这么重要因为后面很多坑都是从“数组名当指针用”开始的。比如新手经常会写str想跳过首字符编译直接报错报错信息里说“需要可修改的左值”。这时候正确做法是定义一个新指针变量char *p str; p;。内存没有变变的是指针变量指向的位置。还有一个经常被误解的知识点char *p hello和char arr[] hello看着很像本质完全不同。前者 p 指向的是字符串常量这个常量通常存放在只读区尝试p[0] H会导致未定义行为运气好能运行运气不好直接段错误。后者 arr 是数组数组元素存在栈上可以随便改。判断标准很简单你能修改的到底是“指针的指向”还是“指针指向的数据”。2.2 用指针读写字符数组的三种标准姿势遍历输出一个字符串下标写法是新手最熟悉的但指针写法才是理解C语言的关键。下面这一段代码把常见的几种方式都列出来#include stdio.h int main(void) { char str[] hello; char *p; // 方式一经典下标遍历 for (int i 0; str[i] ! \0; i) { putchar(str[i]); } putchar(\n); // 方式二指针变量移动遍历 p str; while (*p ! \0) { putchar(*p); p; } putchar(\n); // 方式三指针遍历条件更精简 for (char *q str; *q; q) { putchar(*q); } putchar(\n); return 0; }方式二里p很关键它让 p 从当前字节跳到下一个字节。数组元素是 charsizeof(char) 是 1所以 p 每加一次就前进一个字节。这个“指针移动”过程并不是什么玄学本质就是地址值加上一个偏移量具体多少由指针指向的类型决定。如果指针类型是 intp 会让地址加 4因为一个 int 占 4 个字节。搞清楚这一点指针的很多操作就通了。如果要把字符串里的所有小写字母转成大写指针写法同样很顺手char text[] hello world; for (char *p text; *p; p) { if (*p a *p z) { *p *p - (a - A); // 等价于 *p - 32 } } puts(text);这里通过指针直接修改了数组元素的内容因为*p 就是把新值写进 p 指向的那个内存字节。注意这个操作能成功的前提是 text 确实是一个可修改的数组而不是字符串常量。顺便一提处理字符类型时直接用标准库的toupper更稳但自己手写一遍能加深对 ASCII 码值关系的理解。2.3 函数传参为什么数组名当指针用会丢掉长度信息C语言里函数参数写成char *s和写成char s[]是等价的编译器会把它当成指针处理。这意味着调用func(str)的时候实际传过去的是数组首地址而不是整个数组的拷贝。函数内部如果想用sizeof(s)计算数组长度得到的永远是 4 或 8指针大小不是真实数组长度。这是初学者最容易踩的坑也是最常被面试官拿出来问的点。看一个典型例子// 反面教材函数里 sizeof 得不到数组长度 void bad_func(char s[]) { printf(字符串是%s\n, s); printf(函数内 sizeof(s) %zu\n, sizeof(s)); // 会输出 4 或 8不是 6 } int main(void) { char str[] hello; printf(函数外 sizeof(str) %zu\n, sizeof(str)); // 输出 6因为包含 \0 bad_func(str); return 0; }所以凡是需要长度的函数必须把长度作为参数传进去或者通过找\0的方式自己数。类似 strlen 的库函数就是基于后者实现的从地址开始逐个读字节数到\0为止数出几个就是长度。这也是为什么字符数组要求必须以\0结尾不然 strlen 会一直往后读直到读到内存里某个碰巧为 0 的字节结果不可控。很多内存越界漏洞就源于这种“不信任结尾标志”的情况。3. 用快速排序处理字符型数据从单个字符到字符串数组3.1 对一维字符数组排序把数字换成字母也没区别理解了通用快排之后把 int 换成 char 几乎是无痛迁移。因为字符本质上就是 0 到 127 之间的整数ASCII 码值决定了字典序。排序规则你只需要记住一点字符比较就是整数比较a b等价于97 98。下面是对一个字符数组做升序排列的完整代码#include stdio.h #include string.h void swap_char(char *x, char *y) { char tmp *x; *x *y; *y tmp; } int partition_char(char arr[], int low, int high) { char pivot arr[low]; // 取区间第一个字符当基准 while (low high) { while (low high arr[high] pivot) high--; arr[low] arr[high]; while (low high arr[low] pivot) low; arr[high] arr[low]; } arr[low] pivot; return low; } void quick_sort_char(char arr[], int low, int high) { if (low high) { int pos partition_char(arr, low, high); quick_sort_char(arr, low, pos - 1); quick_sort_char(arr, pos 1, high); } } int main(void) { char chars[] dabecf; // 期望排序结果是 abcdef printf(排序前%s\n, chars); // 这里的 high 是有效字符的下标不能包含结尾的 \0 int low 0; int high (int)strlen(chars) - 1; quick_sort_char(chars, low, high); printf(排序后%s\n, chars); return 0; }仔细看 main 函数里 high 的计算我特意用了strlen(chars) - 1而不是sizeof(chars) - 2。对于数组定义处两者都能算出同样的值但strlen表达的含义更清楚我们只对字符串里有效的字符排序\0永远应该待在字符串末尾它不能被当成普通字符换到中间去。如果你在 main 里用sizeof(chars)得到的是整个数组的大小。对char chars[] dabecf来说sizeof 是 76个字符加一个\0减 2 得到 5恰好是有效字符下标范围。但这样的代码可读性差而且一旦数组里存的内容变了就很容易错。更重要的原因是如果将来排序逻辑被封装成函数函数里只能拿到指针sizeof(chars)会变成指针大小。从第一天起就老老实实用strlen或显式长度参数能避开后续一箩筐问题。3.2 对字符串数组排序交换指针比拷贝整串更聪明上面处理的是“一个字符串内部按字符排序”。但实际开发里更常见的需求是“多个字符串按字典序排列”比如把若干英文单词排序。这时的数据结构表面上还是字符但排序单位从“单个字符”变成了“一串字符”。一个经典方案是用指针数组比如char *names[] {pear, apple, orange, banana, grape}。数组名 names 是一个指针数组每个元素 names[i] 都是一个 char *指向一块字符串内存。排序时真正交换的是这些指针的指向而不是逐个字符地搬运字符串内容。代码如下#include stdio.h #include string.h void swap_str(char **a, char **b) { char *tmp *a; *a *b; *b tmp; } int partition_str(char *arr[], int low, int high) { char *pivot arr[low]; while (low high) { // 用 strcmp 实现字符串的字典序比较 while (low high strcmp(arr[high], pivot) 0) high--; arr[low] arr[high]; while (low high strcmp(arr[low], pivot) 0) low; arr[high] arr[low]; } arr[low] pivot; return low; } void quick_sort_str(char *arr[], int low, int high) { if (low high) { int pos partition_str(arr, low, high); quick_sort_str(arr, low, pos - 1); quick_sort_str(arr, pos 1, high); } } int main(void) { char *names[] {pear, apple, orange, banana, grape}; int n (int)(sizeof(names) / sizeof(names[0])); quick_sort_str(names, 0, n - 1); for (int i 0; i n; i) { printf(%s\n, names[i]); } return 0; }这段代码里的关键点有两个第一个是strcmp它逐个比较两个字符串的字符返回值小于 0 表示第一个串字典序更小等于 0 表示相同大于 0 表示更大。注意返回值不一定只是 -1 或者 1可能是任意整数所以判断时只用符号别去期待具体数值。第二个是swap_str的参数类型因为我们要交换的是指针变量而指针变量本身也有地址所以参数类型是char **函数里通过*a和*b读写的是传入的两个指针变量的值。很多人在这一步卡住就卡在“指针的指针”上。你只需要记住一张图names[i]存的是一个地址names[i]是“这个地址在内存里存放的位置”要修改names[i]本身就必须访问names[i]也就是char **。3.3 二维字符数组版本必须整行拷贝时怎么办指针数组的缺点是每个字符串长度可以不同而且必须先有若干块可指向的字符串内存。如果需求要求用固定大小的二维字符数组比如char words[][20]那么排序时数组里每行是连续内存块交换两行不能靠指针赋值因为二维数组的每一行并不是独立的指针变量。直接写temp words[i]是编译不过的因为数组名不能赋值。正确做法是用strcpy把一整行字符串拷到临时数组再互相拷贝#include stdio.h #include string.h void swap_row(char a[][20], int x, int y) { char tmp[20]; strcpy(tmp, a[x]); strcpy(a[x], a[y]); strcpy(a[y], tmp); } int main(void) { char words[][20] {pear, apple, orange, banana, grape}; int n 5; // 这里只是演示 swap_row 的用法 // 完整快排只需要在分区交换处调用 swap_row 即可。 printf(交换前%s 和 %s\n, words[0], words[1]); swap_row(words, 0, 1); printf(交换后%s 和 %s\n, words[0], words[1]); return 0; }这种做法的代价很明显频繁整行拷贝非常耗时如果字符串很长、数量很多性能远不如交换指针的方案。所以我的建议是能设计成指针数组就先设计成指针数组二维数组的整行交换适合数据固定、字符串长度较短且数量不多的情况。学习阶段把两种写法都手敲一遍是有价值的因为面试经常让你实现“字符串数组排序”而面试官想看到的往往就是char **参数和strcmp判断。3.4 实际场景一份简单的英文单词按字典序排列把上面代码拼起来就是一个可以直接跑起来的单词排序小程序。假设输入来源是命令行参数程序对参数列表排序后输出#include stdio.h #include string.h void swap_str(char **a, char **b) { char *tmp *a; *a *b; *b tmp; } int partition_str(char *arr[], int low, int high) { char *pivot arr[low]; while (low high) { while (low high strcmp(arr[high], pivot) 0) high--; arr[low] arr[high]; while (low high strcmp(arr[low], pivot) 0) low; arr[high] arr[low]; } arr[low] pivot; return low; } void quick_sort_str(char *arr[], int low, int high) { if (low high) { int pos partition_str(arr, low, high); quick_sort_str(arr, low, pos - 1); quick_sort_str(arr, pos 1, high); } } int main(int argc, char *argv[]) { if (argc 1) { printf(用法%s 单词1 单词2 ...\n, argv[0]); return 0; } // 跳过执行文件名 argv[0]对实际参数排序 quick_sort_str(argv 1, 0, argc - 2); for (int i 1; i argc; i) { printf(%s\n, argv[i]); } return 0; }运行./sort banana apple pear会输出 apple、banana、pear。这里argv本身就是 char **也就是一个字符指针数组的数组名传给我们的quick_sort_str刚刚好。通过这个小程序你能把命令行参数、指针数组、快排三个知识点全部串联起来。4. 高频踩坑与排查技巧排序和指针最容易翻车的点4.1 边界问题长度算错\0被当成有效字符处理字符数组时sizeof、strlen、下标范围这三者经常被搅在一起。sizeof是整个数组占用字节数包含了末尾的\0strlen是有效字符数不包含\0。排序有效字符时循环的 high 应该是strlen(str) - 1。如果直接用sizeof(str) - 1排序范围就会包含\0等于把字符串结束标志也排了结果可能得到一个在中间位置带\0的字符串printf 输出了半截就没下文很难排查。建议写一个独立函数接收数组和有效长度避免到处计算void sort_char_array(char arr[], int len) { quick_sort_char(arr, 0, len - 1); }这样调用方只需计算int len strlen(str);意图非常明确。4.2 指针变量与数组名的操作限制数组名是常量地址不是左值str、str other都是非法的指针变量可以随便改p、p q都没有问题。遇到报错信息 “expression must be a modifiable lvalue” 时先检查是不是对数组名做了赋值或自增。还有一个细节char *p str和char *p str[0]完全等价但str[0]的写法在初学阶段更能帮助你意识到“数组首元素地址”这个概念。写成char *p str不合法因为str的类型是数组指针指向整个数组和字符指针类型不匹配这个以后再展开讲现在知道避坑就行。4.3 字符串常量修改崩溃的原因我见过很多新手写这样的代码char *msg hello; msg[0] H; // 危险程序可能正常运行也可能直接崩溃这就是典型的未定义行为。原因是字符串常量通常放在只读区段任何改写尝试都可能导致运行时报错。正确做法是char msg[] hello; msg[0] H;用数组的方式初始化编译器会把内容复制到可写的内存中。如果指针指向的是字符串常量就永远不要试图修改它指向的字符。这个规则很简单但踩过坑的人才知道它有多重要。4.4 快排退化与递归栈溢出的应对递归深度与调用栈相关。快速排序平均递归深度是 O(log n)但最坏情况下会变成 O(n)。当数据量达到百万级别而数据又接近有序时固定取第一个元素的快排可能直接把栈打爆。应对手段除了前面说的随机基准和三数取中之外还有一个工程常用技巧当子区间很小时改用插入排序减少递归调用次数。C标准库里的 qsort 内部也做了类似优化只是它通过函数指针实现通用比较那是另一个话题了。我这里给出一个最小改造版的分区开头加上随机基准之后最坏情况出现概率就低很多#include stdlib.h #include time.h int partition_rand(char arr[], int low, int high) { int idx low rand() % (high - low 1); swap_char(arr[low], arr[idx]); char pivot arr[low]; // 后面和普通分区逻辑一样 }调用前记得srand((unsigned int)time(NULL))。学习阶段不要求但写工程代码时这是加分项。4.5 调试手段打印每次分区的中间状态调试排序算法最好用的工具就是 printf。不要一上来就上调试器打断点先在关键位置打印数组内容快速定位是分区逻辑出错还是递归边界出错。我常用的调试习惯是在 partition 函数返回之前打印区间信息printf([%d, %d] - pos%d, arr, low, high, pos); for (int i 0; i len; i) printf(%c, arr[i]); printf(\n);这样能看到每次分区后基准元素被放到哪个位置左右区间范围是否合理。如果发现基准位置总是等于 high就说明选基准的策略有问题如果发现某些下标被跳过那就是 while 循环里的条件写错了。4.6 strcmp 返回值误判strcmp的返回值可能是负数、零或正数很多新手以为它只返回 -1、0、1。所以判断相等用strcmp(a, b) 0没错但判断大小关系时更要关注符号。比如while (low high strcmp(arr[high], pivot) 0)这里如果 strcmp 返回的是一个正数可能是 1也可能是 127只要它大于等于 0就说明 arr[high] 不小于 pivot这样排序才能得到正确顺序。在实际开发里函数指针和 typedef 可以让快排支持任意类型的元素比如 C 标准库qsort那样。但那一套泛型写法不适合放在第十四篇讲先把基础版本吃透更重要。最后再分享一点实际操作中的体会我在把这个系列从冒泡排到快排的过程中最明显的感觉是排序算法不难难的是把数组下标、指针操作和函数传参这三件事同步想清楚。每写一个排序我就把 int 数组改成 char 数组再改成字符串数组强迫自己把 swap 和比较两个环节分离。一旦你发现“换了类型只需要改类型定义和比较函数就能跑”说明你真正理解了排序的核心结构。另外一个建议是这阶段一定要用printf把每一步过程打出来不要以为自己脑子里能跟踪递归过程。肉眼看过几次之后你对递归和指针的理解会有一个质的飞跃。等哪天你能不看任何代码用刚刚这篇的快排思想给一组中文字符串按下标排个序就算真正过关了。
