C语言指针操作字符数组：快速排序与字符串排序实战

群里一到期末就热闹，清一色的C语言问题里最常出现的一句是：指针到底怎么用？我见过不少同学，书上的概念背得滚瓜烂熟，一说数组名是常量指针、*(p+1)等价于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 两种实现方式对比

两者在时间复杂度上没有本质差别，选哪个纯粹看个人习惯。我自己写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]的本质是*(arr+i)

很多人学到指针时会背一句话："数组名是数组首元素的地址。"但这句话在实际写代码时经常被滥用。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，指针和数组的关系才算真正内化。这篇里给的所有代码，都是从能直接运行的版本里摘出来的，建议你照着敲一遍，再试着把挖坑法改成左右交换法，把字符串数组从二维改成指针数组，每一步的报错都是很好的学习素材。后面如果你还想深入，可以继续研究随机化快排、三数取中优化、以及在海量字符串场景下如何减少比较次数——这些都是同一个框架上长出来的枝叶。