群里一到期末就热闹清一色的C语言问题里最常出现的一句是指针到底怎么用我见过不少同学书上的概念背得滚瓜烂熟一说数组名是常量指针、*(p1)等价于p[1]都能答可真让他写个字符串数组排序瞬间就懵了。这问题我也遇到过后来想明白一件事指针不是靠背学会的是靠用学会的。这一篇我想把快速排序和指针操作一维字符型数组捆在一起讲。这两个点单独拎出来都不算难但一旦组合在一起——比如给你一个字符串数组要求你用快排按字典序排一遍同时明确说用指针操作而不是下标访问——很多人的思路就堵住了。这篇文章适合谁如果你正在被C语言期末考试或课程设计折磨或者准备面试时突然发现基础题还是会卡壳再或者单纯想把快排和字符串指针这两块懂了但不会写的知识点打通那么这篇内容就是给你准备的。我不会只丢一个结论而是把从思想到代码、从坑到调试的完整过程拆开来说。1. 快速排序的分治骨架从冒泡的死缠烂打到一分为二的实用主义1.1 冒泡为什么不够用交换次数是最大的敌人先说个现象。很多教材把冒泡排序放在快速排序前面于是不少人写排序第一反应就是冒泡。冒泡的问题不是排不出来而是太拖拉。看一组数[7, 2, 5, 3, 9, 1, 4, 6]。冒泡每一轮只把当前最大的数顶到末尾每轮要比较很多次还要交换大量的相邻元素。数据量一旦上千冒泡的O(n^2)时间消耗立刻就能在运行结果上体现出来。我当年用冒泡排一万个整数机器都能感觉到顿挫这还是不谈数据量更大的场景。用生活化的话讲冒泡就像你在一堆乱放的书籍里做整理每次都把相邻的两本比较一下需要交换就换位置一轮只能确认一本书的最终位置。如果书架上有1000本书这个操作量是相当痛苦的。快速排序的思路不一样它不搞相邻死磕而是先挑一本书作为基准把所有比它小的放左边、比它大的放右边然后再对左右两堆分别执行同样的操作。1.2 分治思想每次划分都让基准到达最终位置快速排序的核心是分治简单说就是把一个大问题拆成两个小问题小问题处理完大问题自然就解决了。以[7, 2, 5, 3, 9, 1, 4, 6]为例。假设我们选定第一个元素7作为基准pivot目标是一轮划分之后7左边的元素都比7小7右边的元素都比7大而且7本身已经落在最终位置。划分结果大概是[2, 5, 3, 1, 4, 6] 7 [9]。接下来只需要对左边[2, 5, 3, 1, 4, 6]和右边[9]分别再排不需要再管7了因为7已经不用动了。这个划分之后基准元素固定不动的特性是快速排序效率高的关键原因之一。平均情况下每次划分大约能把数组分成两半递归深度是log n每一层总的比较次数大约是n所以平均时间复杂度是O(n log n)。这个复杂度比冒泡的O(n^2)在数据量大时快得不是一星半点。1.3 复杂度与退化风险有序数组反而是最坏情况快速排序有一个让初学者容易忽略的坑如果每次选基准都选到当前区间的最小值或最大值划分就会严重失衡。比如对一个已经有序的数组[1, 2, 3, 4, 5, 6, 7, 8]每次选第一个元素当基准划分结果就是左边为空右边是[2,3,4,5,6,7,8]。这样递归下去划分压根没有把问题减半复杂度直接退化成O(n^2)。解决思路有几种随机选基准不让数据分布规律算计你三数取中取区间最左、最右、中间三个位置的中间值作为基准避免有序数组踩坑递归到小区间时切换成插入排序减少递归开销。我自己的习惯是学习和教学场景里固定取第一个元素清晰易懂生产或竞赛场景里用三数取中。不过很多人不知道大多数能跑的比赛题里单纯的固定基准快排往往会被精心构造的数据卡死所以竞赛里的人几乎都写随机化快排。2. 两类partition实现的取舍挖坑法和左右交换法2.1 挖坑法新手最不容易写崩的划分方案划分动作是快排的核心也就是把区间内的元素按基准分成左右两部分。常见的实现有挖坑法和左右交换法我建议新手先练挖坑法。挖坑法的思路是这样的先把基准值保存到变量里此时基准原来的位置就空出来了形成一个坑。然后右指针向左扫描找到一个比基准小的元素把它填到这个坑里于是右指针的位置又成了新坑接着左指针向右扫描找到一个比基准大的元素填到右指针留出的坑里。反复交替直到左右指针相遇最后把基准值填入最后的坑。代码长这样#include stdio.h void quick_sort_dig(int arr[], int left, int right) { if (left right) { return; } int pivot arr[left]; int i left; int j right; while (i j) { // 从右向左找小于基准的元素 while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; // 填坑j位置成为新坑 } // 从左向右找大于基准的元素 while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; // 填坑i位置成为新坑 } } arr[i] pivot; // i j把基准放入最终位置 quick_sort_dig(arr, left, i - 1); quick_sort_dig(arr, i 1, right); }这段代码的边界条件比较好记外层大循环while(i j)两个内层小循环也都带着i j防止指针越界。需要注意右边的扫描条件是arr[j] pivot这意味着等于基准的元素不会被搬动这么做是为了避免一些边界上的死循环。实际测试也很稳。2.2 左右交换法教科书里的经典双指针方案另一种常见写法是左右交换法。同样选基准后用两个指针从两端向中间逼近。左指针停在比基准大的位置右指针停在比基准小的位置然后交换两处的值。最后把基准交换到中间位置。void quick_sort_swap(int arr[], int left, int right) { if (left right) { return; } int pivot arr[left]; int i left 1; int j right; while (i j) { while (i j arr[i] pivot) { i; } while (i j arr[j] pivot) { j--; } if (i j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; i; j--; } } // 基准归位j是最后一个不大于基准的位置 int temp arr[left]; arr[left] arr[j]; arr[j] temp; quick_sort_swap(arr, left, j - 1); quick_sort_swap(arr, j 1, right); }左右交换法的特点是划分完成后j指向的是最后一个不大于基准的元素所以基准最终和arr[j]交换。这个细节很多教材没点透导致不少人在写递归边界时搞错。我一度在这个问题上栽过跟头——quick_sort_swap(arr, left, j - 1)写成了i - 1结果总有些元素漏排。2.3 两种实现方式对比对比维度挖坑法左右交换法划分思路用一个坑位来回填值两个指针交换值直观程度更直观代码不易跑飞相对抽象边界条件略多交换次数赋值次数多但每次都是移动元素真正交换值整体操作略少适合谁建议初学者先练理解快排原理后可切换基准归位方式循环结束后把基准写入坑位循环结束后与arr[j]交换两者在时间复杂度上没有本质差别选哪个纯粹看个人习惯。我自己写C语言代码时如果是面试场景手写快排通常会选挖坑法因为解释起来清楚也不容易出现左右交换法那种到底是i还是j的边界迷惑。2.4 实测中发现的两个边界细节第一内层扫描遇到等于基准的元素时不能停下来。比如while (i j arr[j] pivot)里如果写成遇到连续相等的元素时左右指针可能一直交换陷入死循环。我试过在全是相同元素的数组上跑错误的版本程序直接卡死后来才意识到比较条件里必须带等号。第二递归出口不能只写left right必须写left right。因为当区间只有一个元素时left right没问题但某些情况下left可能大于right比如上一轮基准归位后右半区间的left i 1如果i已经到了区间末尾left就会大于right。不带的话递归会越界访问报出无法理解的错误。3. 字符数组排序的两个层级排单个字符与排字符串3.1 层级一给单个字符数组排序本质是按ASCII码排整数标题里说的是一维字符型数组这里先区分一个容易混淆的地方一维字符数组char a[10]和字符串数组char b[10][20]是两个完全不同的东西。前者存的是一个个字符后者存的是一个个字符串。如果你要对一个char s[]进行排序其实和给整数数组排序没有区别因为C语言里的char本质上就是1字节的整数字符比较就是ASCII码比较。比如char arr[] hello; // 按ASCII码升序排列h、e、l、l、o // 实际ASCII码104、101、108、108、111把之前写的快排函数稍微改一下类型就能用void quick_sort_char(char arr[], int left, int right) { if (left right) { return; } char pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; if (i j) arr[i] arr[j]; while (i j arr[i] pivot) i; if (i j) arr[j] arr[i]; } arr[i] pivot; quick_sort_char(arr, left, i - 1); quick_sort_char(arr, i 1, right); }唯一的区别是把int pivot换成char pivot其余逻辑一模一样。因为字符的ASCII码比较就是整数比较所以你可以把字符数组排序理解成更小范围整数数组排序。3.2 层级二给多个字符串排序二维数组需要strcmp和strcpy更有实际意义的是给字符串数组排序。比如你有一个学生名单{zhang, wang, li, chen, zhao}按字典序排好。用二维字符数组存储时每个字符串占用一行的空间需要注意char names[5][20]这种存储方式下每行元素在内存中连续分布。对二维字符数组做快排不能用或直接比较字符串必须用strcmp交换时也不能用临时变量char temp arr[i]必须用strcpy把整个字符串内容复制出来。原因很简单字符串是字符序列C语言里没有直接操作字符串的运算一切都要靠内存操作。我写的一个完整可运行版本如下#include stdio.h #include string.h #define NAME_NUM 5 #define NAME_LEN 20 void quick_sort_names(char names[][NAME_LEN], int left, int right) { if (left right) { return; } char pivot[NAME_LEN]; strcpy(pivot, names[left]); // 先复制基准字符串 int i left, j right; while (i j) { while (i j strcmp(names[j], pivot) 0) { j--; } if (i j) { strcpy(names[i], names[j]); // 整串复制覆盖 } while (i j strcmp(names[i], pivot) 0) { i; } if (i j) { strcpy(names[j], names[i]); } } strcpy(names[i], pivot); quick_sort_names(names, left, i - 1); quick_sort_names(names, i 1, right); } int main(void) { char names[NAME_NUM][NAME_LEN] { zhang, wang, li, chen, zhao }; quick_sort_names(names, 0, NAME_NUM - 1); for (int i 0; i NAME_NUM; i) { printf(%s\n, names[i]); } return 0; }运行结果chen li wang zhang zhao你注意看交换的部分每次strcpy都相当于把一整个字符串的内容从内存的一块区域复制到另一块区域。如果字符串很长、数量很多这部分的开销就不容忽视了。3.3 指针数组才是高效方案只交换指针不复制内容二维数组存储字符串交换成本高还有一个致命限制每一行的最大长度被NAME_LEN写死了。如果你想存一个特别长的字符串数组就放不下。更灵活、更常用的方式是指针数组char *names[]。每个元素是一个char *指针指向某个字符串的首字符。排序时根本不需要复制字符串内容只需要交换指针两个字符串在内存中的物理位置完全不动。#include stdio.h #include string.h void quick_sort_pstr(char *arr[], int left, int right) { if (left right) { return; } char *pivot arr[left]; // 保存的是指针不是字符串副本 int i left, j right; while (i j) { while (i j strcmp(arr[j], pivot) 0) { j--; } if (i j) { arr[i] arr[j]; // 直接指针赋值效率高 } while (i j strcmp(arr[i], pivot) 0) { i; } if (i j) { arr[j] arr[i]; } } arr[i] pivot; quick_sort_pstr(arr, left, i - 1); quick_sort_pstr(arr, i 1, right); } int main(void) { char *names[] { zhang, wang, li, chen, zhao }; int n sizeof(names) / sizeof(names[0]); quick_sort_pstr(names, 0, n - 1); for (int i 0; i n; i) { printf(%s\n, names[i]); } return 0; }注意上一版里strcpy(pivot, names[left])变成char *pivot arr[left]这个变化非常关键。基准变量只保存了原字符串的起始地址后面的arr[i] arr[j]操作仅仅是让arr[i]指向arr[j]原本指向的那段内存。整个排序过程中字符串本身没有被搬动过只是三根指针在数组里扭来扭去。这就像整理书架二维数组的做法是把每本书从一个格子搬到另一个格子指针数组的做法是只移动索引卡片的编号书还在原来的格子里。数据量大、字符串很长的时候后者的速度优势非常明显。3.4 非递归版本的思路用栈模拟递归热搜词里有快速排序非递归顺手提一下。递归版本在数组极大时可能爆栈因为每层递归都要占用函数调用栈空间。非递归版本的核心是用一个显式栈保存待处理的区间void quick_sort_iter(char *arr[], int left, int right) { int stack[1024][2]; int top 0; stack[top][0] left; stack[top][1] right; top; while (top 0) { top--; int l stack[top][0]; int r stack[top][1]; if (l r) { continue; } char *pivot arr[l]; int i l, j r; while (i j) { while (i j strcmp(arr[j], pivot) 0) j--; if (i j) arr[i] arr[j]; while (i j strcmp(arr[i], pivot) 0) i; if (i j) arr[j] arr[i]; } arr[i] pivot; stack[top][0] l; stack[top][1] i - 1; top; stack[top][0] i 1; stack[top][1] r; top; } }这里用int stack[1024][2]模拟函数调用栈每压入一个区间就相当于一次递归调用。好处是不担心递归深度坏处是栈的大小得自己控制数组太大时有可能不够用。实际使用时可以改成动态内存分配。4. 指针操作一维字符型数组语法糖背后的移动逻辑4.1 数组名和指针的关系arr[i]的本质是*(arri)很多人学到指针时会背一句话数组名是数组首元素的地址。但这句话在实际写代码时经常被滥用。C语言标准里其实说得很细大多数情况下arr会退化成指向首元素的指针所以arr[i]和*(arr i)完全等价。这带来两个实操上的推论下标访问是语法糖底层还是指针运算。arr[i]翻译过来就是*(arr i)先通过指针加法算出第i个元素的地址再解引用取出内容。数组名本身不是可变指针。arr是非法的因为arr是常量地址但int *p arr; p;合法因为p是独立的指针变量。看一个最普通的例子#include stdio.h int main(void) { char s[] hello; char *p s; printf(%c\n, s[1]); // e printf(%c\n, *(s 1)); // e printf(%c\n, *(p 1)); // e printf(%c\n, p[1]); // e return 0; }这四个输出完全一样。理解了这个等价关系你再看排序代码里的arr[i]其实每一步都在做指针运算。4.2 用手写字符串函数来体会指针遍历说到指针操作字符数组最好的练习就是自己去实现一遍strlen和strcpy。别急着用库函数手写之后你对指针的理解会上一个台阶。size_t my_strlen(const char *s) { const char *p s; while (*p ! \0) { p; } return (size_t)(p - s); } void my_strcpy(char *dest, const char *src) { while ((*dest *src) ! \0) { ; // 循环体空一切在条件和自增中完成 } }my_strlen的思路用一个指针从头往后走直到遇见字符串结束符\0最后用指针相减得到字符个数。my_strcpy更精妙它把赋值、移动指针、判断结束符三个动作压缩在一行里。*dest *src先把src指向的字符赋给dest指向的位置然后把两个指针同时后移一位。循环条件判断赋进去的字符是不是\0是的话就停止。这个写法看起来紧凑实际上是一个非常经典且高效的字符串拷贝模式。4.3 双指针实现字符串逆序排序之外的指针基本功题目里如果有字符串逆序用指针写法是最干脆的。一头一尾两个指针往中间靠拢逐一交换字符#include stdio.h void reverse_str(char *s) { char *left s; char *right s; // 右指针先移动到末尾 while (*right ! \0) { right; } right--; // 退到最后一个有效字符 while (left right) { char temp *left; *left *right; *right temp; left; right--; } } int main(void) { char s[] hello world; reverse_str(s); printf(%s\n, s); // dlrow olleh return 0; }这段代码有两点值得注意移动right时必须先到\0再回退一位否则会把结束符也交换到字符串开头导致输出乱码或丢失。这里必须用char s[]不能写成char *s hello world。原因后面章节细说这是新手最容易踩的坑。4.4 下标改指针排序核心代码里的等价替换回到排序本身。如果要求在快排函数里尽量用指针操作其实可以这么改void quick_sort_ptr(char arr[], int left, int right) { if (left right) { return; } char *base arr; char pivot *(base left); int i left; int j right; while (i j) { while (i j *(base j) pivot) j--; if (i j) { *(base i) *(base j); } while (i j *(base i) pivot) i; if (i j) { *(base j) *(base i); } } *(base i) pivot; quick_sort_ptr(arr, left, i - 1); quick_sort_ptr(arr, i 1, right); }你可能会觉得这写法比下标版本更啰嗦。确实是但重点在于理解下标版本只是把*(base i)悄悄写成了arr[i]而已。当你在指针数组排序中看到char **这种二级指针时前面的基础没打牢就会立刻晕掉。5. 字符排序场景里最容易翻车的五个细节5.1 字符串字面量vs字符数组能不能改内容的分界线这是C语言初学者最常见的地雷。看这两行代码char *p hello; char arr[] hello;第一行里p指向的是一个字符串字面量。在C语言标准里字符串字面量存储在只读区域任何尝试修改它的行为都是未定义行为。很多编译器在Linux下运行修改字符串字面量的程序会直接报段错误。第二行的arr是字符数组它会在栈上申请一块内存把hello的内容复制进去这块内存是可读可写的。在排序场景里这个区别极其致命。假如你写了char *names[] {zhang, wang, li};然后试图用交换指针的方式排序如果排序逻辑中发生对字符串内容的修改比如意外把names[1][0]赋值成别的字符程序就会崩溃。指针数组排序本身只交换数组元素指针不修改字符串内容所以通常是安全的但如果你在排序之外又顺手做了字符串处理务必确认这些字符串的来源是可写内存。德高望重的经验需要动态构造、拼接、修改的字符串用字符数组或malloc分配的内存只用固定内容做展示才适合用字符串字面量。5.2 交换逻辑里的数组越界快排最容易踩的边界错误我调试快排时翻过最大的车是把内层循环的比较条件写反导致指针越过区间边界。尤其是在指针数组版本中如果i越过j之后还在执行arr[i] arr[j]看起来好像没报错但你可能已经访问了数组末尾之后的内存甚至改写了不该动的数据。记住一个检查原则每一处通过下标访问arr[i]之前都想清楚i当前可能的最大值和最小值。内层大循环是while (i j)所以进入循环体时肯定i j但进入内层小循环后i可能自增到j 1所以小循环条件里也要写i j。少了这个条件在极端有序的情况下i会一路自增越过数组末尾读到垃圾数据。5.3 结尾的\0字符串操作的隐形边界strcmp依赖字符串末尾的\0来判断结束。如果字符数组没有正确以\0结尾strcmp就会越界读下去直到在内存中偶然遇到一个0字节才停下。结果就是两个字符串的比较结果完全随机。这个问题在二维字符数组里尤其隐蔽。比如char names[3][4]你往第一行存了abc实际内存布局是a,b,c,\0恰好够用。但如果存abcd\0没有位置存了。后面的strcmp读到第4个字符时取到的是下一行的第一个字符结果乱套。一个好习惯声明二维数组时行宽必须比最大字符串长度至少多1个字节。比如最大名字长度是19就至少用char names[][20]。5.4 scanf读取字符串的空白字符问题排序之前总得输入数据。很多同学喜欢直接scanf(%s, temp)但%s遇到空格、制表符、换行就会停止读取。如果你用zhang san这种带空格的名字%s只读到zhang后面的san会残留在输入缓冲区里直接影响下一次读取。应对方案用scanf(%[^\n]s, temp)来读取直到换行符之前的所有字符或者用fgets(temp, sizeof(temp), stdin)读取整行注意它会把末尾的换行也读进来需要自己处理掉读取多个字符串后如果紧接着还要排序别忘了清空缓冲区残留的换行符否则下一个输入会直接跳过。5.5 调试手段在partition前后打印数组状态最后一个建议也是最朴素有效的遇到排序结果不对别盯着代码干瞪眼在关键位置插入printf打印中间状态。我调试快排时习惯这么干在每次partition完成后打印当前的left、right、i、pivot和整个数组的内容。这样我能直接看到划分是否把基准放到了正确位置左右区间是否对应。printf([debug] left%d right%d pivot%c i%d j%d\n, left, right, pivot, i, j); for (int k left; k right; k) { printf(%c , arr[k]); } printf(\n);对于指针数组版本就打印字符串内容。多跑几组数据基本一眼就能看出问题是出在比较条件、交换逻辑还是递归边界。调试完再把printf注释掉或删除防止影响性能。我个人在实际操作中的体会是快排这套代码背下来远远不够必须亲手敲、亲手调、亲手改过几次bug指针和数组的关系才算真正内化。这篇里给的所有代码都是从能直接运行的版本里摘出来的建议你照着敲一遍再试着把挖坑法改成左右交换法把字符串数组从二维改成指针数组每一步的报错都是很好的学习素材。后面如果你还想深入可以继续研究随机化快排、三数取中优化、以及在海量字符串场景下如何减少比较次数——这些都是同一个框架上长出来的枝叶。
C语言指针操作字符数组：快速排序与字符串排序实战
群里一到期末就热闹清一色的C语言问题里最常出现的一句是指针到底怎么用我见过不少同学书上的概念背得滚瓜烂熟一说数组名是常量指针、*(p1)等价于p[1]都能答可真让他写个字符串数组排序瞬间就懵了。这问题我也遇到过后来想明白一件事指针不是靠背学会的是靠用学会的。这一篇我想把快速排序和指针操作一维字符型数组捆在一起讲。这两个点单独拎出来都不算难但一旦组合在一起——比如给你一个字符串数组要求你用快排按字典序排一遍同时明确说用指针操作而不是下标访问——很多人的思路就堵住了。这篇文章适合谁如果你正在被C语言期末考试或课程设计折磨或者准备面试时突然发现基础题还是会卡壳再或者单纯想把快排和字符串指针这两块懂了但不会写的知识点打通那么这篇内容就是给你准备的。我不会只丢一个结论而是把从思想到代码、从坑到调试的完整过程拆开来说。1. 快速排序的分治骨架从冒泡的死缠烂打到一分为二的实用主义1.1 冒泡为什么不够用交换次数是最大的敌人先说个现象。很多教材把冒泡排序放在快速排序前面于是不少人写排序第一反应就是冒泡。冒泡的问题不是排不出来而是太拖拉。看一组数[7, 2, 5, 3, 9, 1, 4, 6]。冒泡每一轮只把当前最大的数顶到末尾每轮要比较很多次还要交换大量的相邻元素。数据量一旦上千冒泡的O(n^2)时间消耗立刻就能在运行结果上体现出来。我当年用冒泡排一万个整数机器都能感觉到顿挫这还是不谈数据量更大的场景。用生活化的话讲冒泡就像你在一堆乱放的书籍里做整理每次都把相邻的两本比较一下需要交换就换位置一轮只能确认一本书的最终位置。如果书架上有1000本书这个操作量是相当痛苦的。快速排序的思路不一样它不搞相邻死磕而是先挑一本书作为基准把所有比它小的放左边、比它大的放右边然后再对左右两堆分别执行同样的操作。1.2 分治思想每次划分都让基准到达最终位置快速排序的核心是分治简单说就是把一个大问题拆成两个小问题小问题处理完大问题自然就解决了。以[7, 2, 5, 3, 9, 1, 4, 6]为例。假设我们选定第一个元素7作为基准pivot目标是一轮划分之后7左边的元素都比7小7右边的元素都比7大而且7本身已经落在最终位置。划分结果大概是[2, 5, 3, 1, 4, 6] 7 [9]。接下来只需要对左边[2, 5, 3, 1, 4, 6]和右边[9]分别再排不需要再管7了因为7已经不用动了。这个划分之后基准元素固定不动的特性是快速排序效率高的关键原因之一。平均情况下每次划分大约能把数组分成两半递归深度是log n每一层总的比较次数大约是n所以平均时间复杂度是O(n log n)。这个复杂度比冒泡的O(n^2)在数据量大时快得不是一星半点。1.3 复杂度与退化风险有序数组反而是最坏情况快速排序有一个让初学者容易忽略的坑如果每次选基准都选到当前区间的最小值或最大值划分就会严重失衡。比如对一个已经有序的数组[1, 2, 3, 4, 5, 6, 7, 8]每次选第一个元素当基准划分结果就是左边为空右边是[2,3,4,5,6,7,8]。这样递归下去划分压根没有把问题减半复杂度直接退化成O(n^2)。解决思路有几种随机选基准不让数据分布规律算计你三数取中取区间最左、最右、中间三个位置的中间值作为基准避免有序数组踩坑递归到小区间时切换成插入排序减少递归开销。我自己的习惯是学习和教学场景里固定取第一个元素清晰易懂生产或竞赛场景里用三数取中。不过很多人不知道大多数能跑的比赛题里单纯的固定基准快排往往会被精心构造的数据卡死所以竞赛里的人几乎都写随机化快排。2. 两类partition实现的取舍挖坑法和左右交换法2.1 挖坑法新手最不容易写崩的划分方案划分动作是快排的核心也就是把区间内的元素按基准分成左右两部分。常见的实现有挖坑法和左右交换法我建议新手先练挖坑法。挖坑法的思路是这样的先把基准值保存到变量里此时基准原来的位置就空出来了形成一个坑。然后右指针向左扫描找到一个比基准小的元素把它填到这个坑里于是右指针的位置又成了新坑接着左指针向右扫描找到一个比基准大的元素填到右指针留出的坑里。反复交替直到左右指针相遇最后把基准值填入最后的坑。代码长这样#include stdio.h void quick_sort_dig(int arr[], int left, int right) { if (left right) { return; } int pivot arr[left]; int i left; int j right; while (i j) { // 从右向左找小于基准的元素 while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; // 填坑j位置成为新坑 } // 从左向右找大于基准的元素 while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; // 填坑i位置成为新坑 } } arr[i] pivot; // i j把基准放入最终位置 quick_sort_dig(arr, left, i - 1); quick_sort_dig(arr, i 1, right); }这段代码的边界条件比较好记外层大循环while(i j)两个内层小循环也都带着i j防止指针越界。需要注意右边的扫描条件是arr[j] pivot这意味着等于基准的元素不会被搬动这么做是为了避免一些边界上的死循环。实际测试也很稳。2.2 左右交换法教科书里的经典双指针方案另一种常见写法是左右交换法。同样选基准后用两个指针从两端向中间逼近。左指针停在比基准大的位置右指针停在比基准小的位置然后交换两处的值。最后把基准交换到中间位置。void quick_sort_swap(int arr[], int left, int right) { if (left right) { return; } int pivot arr[left]; int i left 1; int j right; while (i j) { while (i j arr[i] pivot) { i; } while (i j arr[j] pivot) { j--; } if (i j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; i; j--; } } // 基准归位j是最后一个不大于基准的位置 int temp arr[left]; arr[left] arr[j]; arr[j] temp; quick_sort_swap(arr, left, j - 1); quick_sort_swap(arr, j 1, right); }左右交换法的特点是划分完成后j指向的是最后一个不大于基准的元素所以基准最终和arr[j]交换。这个细节很多教材没点透导致不少人在写递归边界时搞错。我一度在这个问题上栽过跟头——quick_sort_swap(arr, left, j - 1)写成了i - 1结果总有些元素漏排。2.3 两种实现方式对比对比维度挖坑法左右交换法划分思路用一个坑位来回填值两个指针交换值直观程度更直观代码不易跑飞相对抽象边界条件略多交换次数赋值次数多但每次都是移动元素真正交换值整体操作略少适合谁建议初学者先练理解快排原理后可切换基准归位方式循环结束后把基准写入坑位循环结束后与arr[j]交换两者在时间复杂度上没有本质差别选哪个纯粹看个人习惯。我自己写C语言代码时如果是面试场景手写快排通常会选挖坑法因为解释起来清楚也不容易出现左右交换法那种到底是i还是j的边界迷惑。2.4 实测中发现的两个边界细节第一内层扫描遇到等于基准的元素时不能停下来。比如while (i j arr[j] pivot)里如果写成遇到连续相等的元素时左右指针可能一直交换陷入死循环。我试过在全是相同元素的数组上跑错误的版本程序直接卡死后来才意识到比较条件里必须带等号。第二递归出口不能只写left right必须写left right。因为当区间只有一个元素时left right没问题但某些情况下left可能大于right比如上一轮基准归位后右半区间的left i 1如果i已经到了区间末尾left就会大于right。不带的话递归会越界访问报出无法理解的错误。3. 字符数组排序的两个层级排单个字符与排字符串3.1 层级一给单个字符数组排序本质是按ASCII码排整数标题里说的是一维字符型数组这里先区分一个容易混淆的地方一维字符数组char a[10]和字符串数组char b[10][20]是两个完全不同的东西。前者存的是一个个字符后者存的是一个个字符串。如果你要对一个char s[]进行排序其实和给整数数组排序没有区别因为C语言里的char本质上就是1字节的整数字符比较就是ASCII码比较。比如char arr[] hello; // 按ASCII码升序排列h、e、l、l、o // 实际ASCII码104、101、108、108、111把之前写的快排函数稍微改一下类型就能用void quick_sort_char(char arr[], int left, int right) { if (left right) { return; } char pivot arr[left]; int i left, j right; while (i j) { while (i j arr[j] pivot) j--; if (i j) arr[i] arr[j]; while (i j arr[i] pivot) i; if (i j) arr[j] arr[i]; } arr[i] pivot; quick_sort_char(arr, left, i - 1); quick_sort_char(arr, i 1, right); }唯一的区别是把int pivot换成char pivot其余逻辑一模一样。因为字符的ASCII码比较就是整数比较所以你可以把字符数组排序理解成更小范围整数数组排序。3.2 层级二给多个字符串排序二维数组需要strcmp和strcpy更有实际意义的是给字符串数组排序。比如你有一个学生名单{zhang, wang, li, chen, zhao}按字典序排好。用二维字符数组存储时每个字符串占用一行的空间需要注意char names[5][20]这种存储方式下每行元素在内存中连续分布。对二维字符数组做快排不能用或直接比较字符串必须用strcmp交换时也不能用临时变量char temp arr[i]必须用strcpy把整个字符串内容复制出来。原因很简单字符串是字符序列C语言里没有直接操作字符串的运算一切都要靠内存操作。我写的一个完整可运行版本如下#include stdio.h #include string.h #define NAME_NUM 5 #define NAME_LEN 20 void quick_sort_names(char names[][NAME_LEN], int left, int right) { if (left right) { return; } char pivot[NAME_LEN]; strcpy(pivot, names[left]); // 先复制基准字符串 int i left, j right; while (i j) { while (i j strcmp(names[j], pivot) 0) { j--; } if (i j) { strcpy(names[i], names[j]); // 整串复制覆盖 } while (i j strcmp(names[i], pivot) 0) { i; } if (i j) { strcpy(names[j], names[i]); } } strcpy(names[i], pivot); quick_sort_names(names, left, i - 1); quick_sort_names(names, i 1, right); } int main(void) { char names[NAME_NUM][NAME_LEN] { zhang, wang, li, chen, zhao }; quick_sort_names(names, 0, NAME_NUM - 1); for (int i 0; i NAME_NUM; i) { printf(%s\n, names[i]); } return 0; }运行结果chen li wang zhang zhao你注意看交换的部分每次strcpy都相当于把一整个字符串的内容从内存的一块区域复制到另一块区域。如果字符串很长、数量很多这部分的开销就不容忽视了。3.3 指针数组才是高效方案只交换指针不复制内容二维数组存储字符串交换成本高还有一个致命限制每一行的最大长度被NAME_LEN写死了。如果你想存一个特别长的字符串数组就放不下。更灵活、更常用的方式是指针数组char *names[]。每个元素是一个char *指针指向某个字符串的首字符。排序时根本不需要复制字符串内容只需要交换指针两个字符串在内存中的物理位置完全不动。#include stdio.h #include string.h void quick_sort_pstr(char *arr[], int left, int right) { if (left right) { return; } char *pivot arr[left]; // 保存的是指针不是字符串副本 int i left, j right; while (i j) { while (i j strcmp(arr[j], pivot) 0) { j--; } if (i j) { arr[i] arr[j]; // 直接指针赋值效率高 } while (i j strcmp(arr[i], pivot) 0) { i; } if (i j) { arr[j] arr[i]; } } arr[i] pivot; quick_sort_pstr(arr, left, i - 1); quick_sort_pstr(arr, i 1, right); } int main(void) { char *names[] { zhang, wang, li, chen, zhao }; int n sizeof(names) / sizeof(names[0]); quick_sort_pstr(names, 0, n - 1); for (int i 0; i n; i) { printf(%s\n, names[i]); } return 0; }注意上一版里strcpy(pivot, names[left])变成char *pivot arr[left]这个变化非常关键。基准变量只保存了原字符串的起始地址后面的arr[i] arr[j]操作仅仅是让arr[i]指向arr[j]原本指向的那段内存。整个排序过程中字符串本身没有被搬动过只是三根指针在数组里扭来扭去。这就像整理书架二维数组的做法是把每本书从一个格子搬到另一个格子指针数组的做法是只移动索引卡片的编号书还在原来的格子里。数据量大、字符串很长的时候后者的速度优势非常明显。3.4 非递归版本的思路用栈模拟递归热搜词里有快速排序非递归顺手提一下。递归版本在数组极大时可能爆栈因为每层递归都要占用函数调用栈空间。非递归版本的核心是用一个显式栈保存待处理的区间void quick_sort_iter(char *arr[], int left, int right) { int stack[1024][2]; int top 0; stack[top][0] left; stack[top][1] right; top; while (top 0) { top--; int l stack[top][0]; int r stack[top][1]; if (l r) { continue; } char *pivot arr[l]; int i l, j r; while (i j) { while (i j strcmp(arr[j], pivot) 0) j--; if (i j) arr[i] arr[j]; while (i j strcmp(arr[i], pivot) 0) i; if (i j) arr[j] arr[i]; } arr[i] pivot; stack[top][0] l; stack[top][1] i - 1; top; stack[top][0] i 1; stack[top][1] r; top; } }这里用int stack[1024][2]模拟函数调用栈每压入一个区间就相当于一次递归调用。好处是不担心递归深度坏处是栈的大小得自己控制数组太大时有可能不够用。实际使用时可以改成动态内存分配。4. 指针操作一维字符型数组语法糖背后的移动逻辑4.1 数组名和指针的关系arr[i]的本质是*(arri)很多人学到指针时会背一句话数组名是数组首元素的地址。但这句话在实际写代码时经常被滥用。C语言标准里其实说得很细大多数情况下arr会退化成指向首元素的指针所以arr[i]和*(arr i)完全等价。这带来两个实操上的推论下标访问是语法糖底层还是指针运算。arr[i]翻译过来就是*(arr i)先通过指针加法算出第i个元素的地址再解引用取出内容。数组名本身不是可变指针。arr是非法的因为arr是常量地址但int *p arr; p;合法因为p是独立的指针变量。看一个最普通的例子#include stdio.h int main(void) { char s[] hello; char *p s; printf(%c\n, s[1]); // e printf(%c\n, *(s 1)); // e printf(%c\n, *(p 1)); // e printf(%c\n, p[1]); // e return 0; }这四个输出完全一样。理解了这个等价关系你再看排序代码里的arr[i]其实每一步都在做指针运算。4.2 用手写字符串函数来体会指针遍历说到指针操作字符数组最好的练习就是自己去实现一遍strlen和strcpy。别急着用库函数手写之后你对指针的理解会上一个台阶。size_t my_strlen(const char *s) { const char *p s; while (*p ! \0) { p; } return (size_t)(p - s); } void my_strcpy(char *dest, const char *src) { while ((*dest *src) ! \0) { ; // 循环体空一切在条件和自增中完成 } }my_strlen的思路用一个指针从头往后走直到遇见字符串结束符\0最后用指针相减得到字符个数。my_strcpy更精妙它把赋值、移动指针、判断结束符三个动作压缩在一行里。*dest *src先把src指向的字符赋给dest指向的位置然后把两个指针同时后移一位。循环条件判断赋进去的字符是不是\0是的话就停止。这个写法看起来紧凑实际上是一个非常经典且高效的字符串拷贝模式。4.3 双指针实现字符串逆序排序之外的指针基本功题目里如果有字符串逆序用指针写法是最干脆的。一头一尾两个指针往中间靠拢逐一交换字符#include stdio.h void reverse_str(char *s) { char *left s; char *right s; // 右指针先移动到末尾 while (*right ! \0) { right; } right--; // 退到最后一个有效字符 while (left right) { char temp *left; *left *right; *right temp; left; right--; } } int main(void) { char s[] hello world; reverse_str(s); printf(%s\n, s); // dlrow olleh return 0; }这段代码有两点值得注意移动right时必须先到\0再回退一位否则会把结束符也交换到字符串开头导致输出乱码或丢失。这里必须用char s[]不能写成char *s hello world。原因后面章节细说这是新手最容易踩的坑。4.4 下标改指针排序核心代码里的等价替换回到排序本身。如果要求在快排函数里尽量用指针操作其实可以这么改void quick_sort_ptr(char arr[], int left, int right) { if (left right) { return; } char *base arr; char pivot *(base left); int i left; int j right; while (i j) { while (i j *(base j) pivot) j--; if (i j) { *(base i) *(base j); } while (i j *(base i) pivot) i; if (i j) { *(base j) *(base i); } } *(base i) pivot; quick_sort_ptr(arr, left, i - 1); quick_sort_ptr(arr, i 1, right); }你可能会觉得这写法比下标版本更啰嗦。确实是但重点在于理解下标版本只是把*(base i)悄悄写成了arr[i]而已。当你在指针数组排序中看到char **这种二级指针时前面的基础没打牢就会立刻晕掉。5. 字符排序场景里最容易翻车的五个细节5.1 字符串字面量vs字符数组能不能改内容的分界线这是C语言初学者最常见的地雷。看这两行代码char *p hello; char arr[] hello;第一行里p指向的是一个字符串字面量。在C语言标准里字符串字面量存储在只读区域任何尝试修改它的行为都是未定义行为。很多编译器在Linux下运行修改字符串字面量的程序会直接报段错误。第二行的arr是字符数组它会在栈上申请一块内存把hello的内容复制进去这块内存是可读可写的。在排序场景里这个区别极其致命。假如你写了char *names[] {zhang, wang, li};然后试图用交换指针的方式排序如果排序逻辑中发生对字符串内容的修改比如意外把names[1][0]赋值成别的字符程序就会崩溃。指针数组排序本身只交换数组元素指针不修改字符串内容所以通常是安全的但如果你在排序之外又顺手做了字符串处理务必确认这些字符串的来源是可写内存。德高望重的经验需要动态构造、拼接、修改的字符串用字符数组或malloc分配的内存只用固定内容做展示才适合用字符串字面量。5.2 交换逻辑里的数组越界快排最容易踩的边界错误我调试快排时翻过最大的车是把内层循环的比较条件写反导致指针越过区间边界。尤其是在指针数组版本中如果i越过j之后还在执行arr[i] arr[j]看起来好像没报错但你可能已经访问了数组末尾之后的内存甚至改写了不该动的数据。记住一个检查原则每一处通过下标访问arr[i]之前都想清楚i当前可能的最大值和最小值。内层大循环是while (i j)所以进入循环体时肯定i j但进入内层小循环后i可能自增到j 1所以小循环条件里也要写i j。少了这个条件在极端有序的情况下i会一路自增越过数组末尾读到垃圾数据。5.3 结尾的\0字符串操作的隐形边界strcmp依赖字符串末尾的\0来判断结束。如果字符数组没有正确以\0结尾strcmp就会越界读下去直到在内存中偶然遇到一个0字节才停下。结果就是两个字符串的比较结果完全随机。这个问题在二维字符数组里尤其隐蔽。比如char names[3][4]你往第一行存了abc实际内存布局是a,b,c,\0恰好够用。但如果存abcd\0没有位置存了。后面的strcmp读到第4个字符时取到的是下一行的第一个字符结果乱套。一个好习惯声明二维数组时行宽必须比最大字符串长度至少多1个字节。比如最大名字长度是19就至少用char names[][20]。5.4 scanf读取字符串的空白字符问题排序之前总得输入数据。很多同学喜欢直接scanf(%s, temp)但%s遇到空格、制表符、换行就会停止读取。如果你用zhang san这种带空格的名字%s只读到zhang后面的san会残留在输入缓冲区里直接影响下一次读取。应对方案用scanf(%[^\n]s, temp)来读取直到换行符之前的所有字符或者用fgets(temp, sizeof(temp), stdin)读取整行注意它会把末尾的换行也读进来需要自己处理掉读取多个字符串后如果紧接着还要排序别忘了清空缓冲区残留的换行符否则下一个输入会直接跳过。5.5 调试手段在partition前后打印数组状态最后一个建议也是最朴素有效的遇到排序结果不对别盯着代码干瞪眼在关键位置插入printf打印中间状态。我调试快排时习惯这么干在每次partition完成后打印当前的left、right、i、pivot和整个数组的内容。这样我能直接看到划分是否把基准放到了正确位置左右区间是否对应。printf([debug] left%d right%d pivot%c i%d j%d\n, left, right, pivot, i, j); for (int k left; k right; k) { printf(%c , arr[k]); } printf(\n);对于指针数组版本就打印字符串内容。多跑几组数据基本一眼就能看出问题是出在比较条件、交换逻辑还是递归边界。调试完再把printf注释掉或删除防止影响性能。我个人在实际操作中的体会是快排这套代码背下来远远不够必须亲手敲、亲手调、亲手改过几次bug指针和数组的关系才算真正内化。这篇里给的所有代码都是从能直接运行的版本里摘出来的建议你照着敲一遍再试着把挖坑法改成左右交换法把字符串数组从二维改成指针数组每一步的报错都是很好的学习素材。后面如果你还想深入可以继续研究随机化快排、三数取中优化、以及在海量字符串场景下如何减少比较次数——这些都是同一个框架上长出来的枝叶。
