企业官网建设流程全解析

很多刚开始学C语言的朋友，第一次被数组难住，通常不是“数组怎么定义”这类基本操作，而是“排序”。课程作业让你把成绩从高到低排一排，考试卷问你对一组整数排序，面试笔试也总有一道手写排序题。看起来人畜无害，真上手写却总差那么一两行：边界越界、元素没排完、交换写反了……这篇文章就把C语言里最常用的三种数组排序方法——冒泡排序、选择排序、插入排序，以及排序背后几乎必用的“数组移动”操作，完整梳理一遍。代码一行行注释，后面还配了一套可以拿来练手的题目。你照着敲一遍、跑一遍，把这几个算法变成“肌肉记忆”，后面学快排、归并或者应付机考，都会舒服很多。

1. 排序算法怎么选：先看懂三兄弟的“干活思路”

1.1 冒泡排序：两两对比，把大的往后赶

冒泡排序是最直观、最容易在脑子里模拟的算法。它的思路一句话就能说清：从头到尾，两两比较相邻元素，如果顺序不对就交换，一趟下来，最大的那个数就会像气泡一样“冒”到最后面。下一趟再从头开始，但不包括已经就位的最后一个元素，因为最大值已经确定不会再变了。

这个过程用生活里的例子想，就是一群人排队站整齐：先让第1个人和第2个人比身高，高的往后站，再让第2个和第3个比……一趟走完，最高的人站到了队尾。第二趟只需要管前n-1个人，因为最高那个已经站在最后了。重复这个动作，队伍就按从矮到高排好了。

为什么叫“冒泡”？因为每一趟结束后，总有一个当前范围内的最大元素“咕噜”一下浮到末尾，就像气泡从水底升到水面。这种算法最容易被初学者接受，因为它每一步的逻辑都非常透明：比较、交换、移动指针，没有藏任何弯弯绕绕。

实际写代码时需要注意的细节不少。外层循环控制“要跑几趟”，n个元素的数组，最多只需要跑n-1趟，因为最后一趟只剩一个元素，不需要再比较。内层循环要控制“这一趟比较到哪个位置”，范围是0到n-1-i，这里的i就是已经跑完的趟数，刚好表示末尾已经有i个元素就位。很多初学者写成j < n，导致每一趟都比到最后一个元素，虽然结果往往没错，但是做了大量无用的比较，算法的效率就变差了。

1.2 选择排序：挑最值，换到前面去

选择排序的思路比冒泡更“省事”：每一趟从数组的未排序部分里找到最小的元素，然后把它和未排序部分的第一个元素交换位置。这样经过n-1趟之后，前面部分越来越满，后面部分越来越空，整个数组也就有序了。

你可以把它想象成在班里选人：老师每次从剩下的同学里挑一个最矮的，站到队伍前头，然后继续从剩下的人里挑……选n-1次之后，队伍自然排好了。选择排序和冒泡排序最大的不同在于：冒泡排序每比较一次就可能交换一次，而选择排序每趟只在整个未排序区间扫描一遍，记下最小值的下标，最后只交换一次。这样大大减少了移动次数，但比较次数依然是O(n²)。

有一个细节值得注意：选择排序在“相等元素”面前不太稳定。比如数组里有多个相同的值，它可能在交换过程中把相同值的相对顺序打乱。虽然对入门阶段，稳定性这个概念听起来很高端，但开始了解它对你以后学归并排序、理解各种排序算法的适用场景会有帮助。这里先留个印象，不用死记。

很多初学者第一遍写选择排序时，会把“找最小值”写成了“如果当前元素比第一个元素小，就立刻交换”。这不是选择排序的思路，更像一种变种的冒泡，而且交换次数会大幅增加。正确的做法是：先假设当前区间的第一个元素是最小值，用一个变量minIndex记录它的位置，然后往后遍历，只要发现更小的，就更新minIndex。这一趟结束时，才把arr[i]和arr[minIndex]交换。这个中间步骤很重要，也是选择排序的“灵魂”所在。

1.3 插入排序：像摸扑克牌，边摸边排

插入排序的思路，玩过扑克牌的同学肯定秒懂。你摸牌的时候，不会先把整副牌洗一遍，而是把新摸到的牌插到手里已经排好序的某张牌旁边。插入排序干的就是这件事：从第二个元素开始，把它当作“新摸到的牌”，在它前面的已经排序好的区间里找到合适的位置，把它插进去，同时把后面的元素依次往后挪。

这个算法最大的优势是“适应性强”。如果一个数组本身已经差不多有序，插入排序只需要做很少的移动就能完成排序，甚至在最好的情况下（数组完全有序），它的时间复杂度可以降到O(n)。这一点冒泡和选择都做不到，它们不管数据是否有序，该比较多少趟还是多少趟。

但好处也有代价：插入排序在数据量大且顺序混乱的情况下，移动次数非常可观。因为每次插入一个元素，都可能引发一串元素的后移。数组移动操作在排序中表现得最淋漓尽致的就是插入排序，这也是为什么题目里会特别强调“数组的移动”——你掌握了移动操作，才能真正理解插入排序在做什么。

初学者写插入排序时常见的问题是：把新元素和前面的元素比较时，一发现前面的元素比新元素大，就立刻交换或直接把前面的元素往后覆盖，结果整个数组就乱套了。正确思路应该是先把待插入的值存到一个临时变量key里，然后从后往前遍历已排序区间，只要发现某个元素比key大，就把它往后挪一个位置；直到找到一个不再比key大的位置，才把key放进去。整个过程里，key就像一个临时腾出来的“空位”，一路向后移动，直到找到落脚点。

1.4 三兄弟对比：什么时候用谁

三个算法都是O(n²)级别的排序算法，适用于数据量比较小（通常几百个元素以内）的场景。它们的实现难度、交换次数和稳定性各不相同，下面这个表格可以帮你一眼看清：

这里说一句个人经验：在你刚刚学排序的时候，不要急着“三选一”，更不要觉得“学了高级排序就瞧不上冒泡”。这三种算法各有各的启发意义。冒泡教会你如何用双层循环控制边界，选择教会你如何用一次遍历找到极值并用最少交换完成“定位”，插入教会你如何利用“局部有序”来降低工作量。把这些思想吃透，后面看快速排序、归并排序时，你才能一眼看出来它们到底“快”在哪里。

2. 手写代码：三个排序一次跑通（逐行注释版）

2.1 冒泡排序完整代码与优化标记

先看最基础的冒泡排序实现。

#include <stdio.h> // 冒泡排序（基础版） // 参数 arr 是待排序数组，n 是元素个数 void bubbleSort(int arr[], int n) { // 外层循环：一共需要 n-1 趟 // 每跑一趟，末尾就会多一个已经确定好的最大元素 for (int i = 0; i < n - 1; i++) { // 内层循环：从第一个元素比较到 n-1-i 位置 // 因为末尾的 i 个元素已经就位，不需要再参与比较 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 相邻两个元素逆序，交换 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main() { int arr[] = {9, 3, 8, 1, 7, 5, 6, 2, 4, 0}; int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度 bubbleSort(arr, n); // 打印排序后的数组 for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

这段代码的逻辑很直白，但有个小问题：如果数组本身已经有序，它仍然会跑完所有的比较。比如数组是{1, 2, 3, 4, 5}，冒泡排序依然会执行4趟完整的比较，白白浪费CPU。实际工程里，我们通常会给它加一个“优化开关”。

优化思路是这样的：在每一趟开始时设置一个标志变量swapped，初始为0（表示“这一趟还没交换过”）。只要在这一趟里发生了一次交换，就把swapped置为1。当一趟循环结束，如果swapped仍然是0，说明整个数组已经有序，不需要再继续后面的趟数，直接break退出即可。这个优化对接近有序的数据效果非常明显。

// 冒泡排序（优化版：提前退出） void bubbleSortOptimized(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; // 本趟是否发生过交换 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = 1; } } if (swapped == 0) { break; // 没有发生交换，数组已经有序 } } }

实际测试一下，对{9, 3, 8, 1, 7, 5, 6, 2, 4, 0}排序，普通版会执行9趟，而优化版第9趟开始时发现已经有序了，会提前结束。虽然最坏情况下的复杂度没变，但平均情况和最好情况都有明显改善。你在作业里也可以用统计交换次数的方式去验证优化前后的差别。

2.2 选择排序完整代码与交换优化

选择排序的代码实现起来略微抽象一些，因为它把“比较”和“交换”这两件事拆开了。看代码之前先记住核心：每一趟先找到范围内最小元素的位置，然后把这个位置记录到minIndex里，这趟结束才交换。

#include <stdio.h> // 选择排序 void selectionSort(int arr[], int n) { // 外层循环：只需要找 n-1 次最小值 // 最后一个元素不需要再找，因为它一定是剩下的最大值 for (int i = 0; i < n - 1; i++) { // 假设当前未排序区间的第一个元素是最小的 int minIndex = i; // 在剩下的未排序区间里找真正的最小值下标 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; // 发现更小的元素，更新下标 } } // 如果最小值下标不是 i，才需要交换 if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } }

这里的if (minIndex != i)判断不是多余的优化。当数组已经有序时，每一趟minIndex刚好等于i，我们不需要做交换；只有发现更小的元素才交换。这样既避免了无意义的写入操作，也让代码逻辑更清晰。

一个值得对比的细节：选择排序对外层循环的次数要求是固定的n-1趟。即便数组本来有序，它也一定要扫描完所有元素才能确认。所以它的最好情况也是O(n²)，这是它与插入排序之间最明显的差距。但在“交换次数”这个指标上，选择排序非常优秀，每一趟最多交换1次，总共最多n-1次。如果你处理的数组元素是结构体、字符串或者大体积数据，减少交换次数对性能有实实在在的帮助。

常见的一个错误是把内层循环写成for (int j = i; j < n; j++)，这会导致把自己（arr[i]）也跟自己比较一次，虽然不影响最终结果，但是多余的比较。更要注意的是，有些人会在循环体里看到arr[j] < arr[minIndex]时直接交换arr[i]和arr[j]，这就完全不是选择排序了，而是误把选择排序写成了“循环交换版冒泡”，会导致交换次数急剧上升，性能下降明显。

2.3 插入排序完整代码与后移逻辑

插入排序的代码量不大，但理解它的核心逻辑——“后移腾位置”——可以让你一次性把数组移动操作也掌握大半。

#include <stdio.h> // 插入排序 void insertionSort(int arr[], int n) { // 从第二个元素开始，第一个元素天然是有序的 for (int i = 1; i < n; i++) { int key = arr[i]; // 当前要插入的元素 int j = i - 1; // 往前找插入位置 // 从后往前扫描已排序区间 // arr[j] > key 时，说明 key 应该插在更靠前的位置 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 把大的元素往后挪一位 j--; } // 找到位置后，把 key 放进去 arr[j + 1] = key; } }

这段代码最需要仔细体会的是while (j >= 0 && arr[j] > key)这一行。条件里j >= 0绝对不能省略，因为当key是整个数组的最小值时，j会一路减到-1，此时如果缺少j >= 0这个条件，循环还会继续访问arr[-1]，这是一个典型的越界错误。C语言里越界访问不会主动报错，但会读取到内存里的随机数据，轻则结果错误，重则程序崩溃。

另一个理解难点是为什么用arr[j + 1] = arr[j]而不是交换。想象你现在手里有一堆已经按顺序排好的牌，你需要把一张新牌插进去。你不会把每一张牌都和新牌交换一次，而是把比新牌大的牌依次往后挪一个位置，腾出一个“空位”来放新牌。这里的key就是那张新牌，它是独立存放的，不会因为后移而被覆盖。整个过程看下来，插入排序本质上就是在反复使用“数组移动”这个基础操作——这也正是题目里把“数组的移动”放在排序旁边强调的原因。

测试时可以用一组简单数据验证：{5, 2, 4, 6, 1, 3}。第一趟，key=2，它前面的5比2大，5后移，数组变成{5, 5, 4, 6, 1, 3}，然后key放到位置0，变成{2, 5, 4, 6, 1, 3}。第二趟，key=4，5比4大，5后移，2不比4大，停止，4放到位置1，得到{2, 4, 5, 6, 1, 3}。这个过程自己手动推一遍，远比看我写一百遍有用。

2.4 测试代码：把三个排序放在一起比较

把三个排序放在同一个主函数里跑，直观感受它们的运行效果。

#include <stdio.h> void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr1[] = {9, 3, 8, 1, 7, 5, 6, 2, 4, 0}; int arr2[] = {9, 3, 8, 1, 7, 5, 6, 2, 4, 0}; int arr3[] = {9, 3, 8, 1, 7, 5, 6, 2, 4, 0}; int n = sizeof(arr1) / sizeof(arr1[0]); printf("原始数组: "); printArray(arr1, n); bubbleSort(arr1, n); printf("冒泡排序: "); printArray(arr1, n); selectionSort(arr2, n); printf("选择排序: "); printArray(arr2, n); insertionSort(arr3, n); printf("插入排序: "); printArray(arr3, n); return 0; }

运行结果都是0 1 2 3 4 5 6 7 8 9。我建议你在写练习时，用不同的数组重复测试：完全逆序、已经有序、有大量重复值、只有一个元素。不同数据能暴露不同问题。比如只有一个元素的数组，三个排序都能正确跳过，但如果你的循环条件写的是i <= n而不是i < n，就很容易越界。

3. 数组移动操作：插入、删除、循环移位一次讲透

3.1 在指定位置插入元素：先把后面的让开

数组和链表的区别，学C语言的人都清楚：数组是连续内存空间，插入一个元素不能像链表那样“改一下指针就完事”，必须把插入位置后面的所有元素整体往后挪一个位置，腾出一个空位来放新元素。这个“挪”就是数组移动。

比如数组当前有5个元素：{1, 2, 3, 4, 5}，要在下标2的位置插入元素99，最终应该是{1, 2, 99, 3, 4, 5}。操作顺序是：先把下标4的元素5移到下标5，再把下标4空出来（准确说是把下标3的4移到下标4），再把下标2的3移到下标3……也就是从最后一个元素开始，依次往后覆盖。关键点是必须“从后往前”移动。

#include <stdio.h> int main() { int arr[10] = {1, 2, 3, 4, 5}; int len = 5; // 当前有效元素个数 int pos = 2; // 要插入的位置（下标） int value = 99; // 要插入的值 // 检查插入位置是否合法 if (pos < 0 || pos > len) { printf("插入位置不合法\n"); return 1; } // 还需要检查数组是否已满（len == 容量），这里容量是10 // 从最后一个元素开始，往后移动 for (int i = len; i > pos; i--) { arr[i] = arr[i - 1]; } // 腾出的位置赋值 arr[pos] = value; len++; // 数组长度加1 // 打印结果 for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

如果反过来从前往后移动，比如先把arr[2]移到arr[3]，那arr[2]的新值还没放进来，旧的arr[2]已经被覆盖丢失，后面就乱了。这个“从后往前”的记忆点值得刻在脑子里。删除操作恰恰相反，是从前往后移动。一正一反，恰好形成对称。

3.2 删除指定位置的元素：把后面的往前挪

删除元素比插入简单，逻辑上也恰好反过来：从被删除位置的下一个元素开始，把每个元素往前挪一个位置。

#include <stdio.h> int main() { int arr[10] = {1, 2, 3, 4, 5}; int len = 5; // 当前有效元素个数 int pos = 2; // 要删除的位置（下标） if (pos < 0 || pos >= len) { printf("删除位置不合法\n"); return 1; } // 从 pos 的下一个位置开始，依次往前覆盖 for (int i = pos; i < len - 1; i++) { arr[i] = arr[i + 1]; } len--; // 数组长度减1 for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

执行过程：原数组{1, 2, 3, 4, 5}，删除pos=2。先把arr[3]的4赋给arr[2]，数组变成{1, 2, 4, 4, 5}；再把arr[4]的5赋给arr[3]，数组变成{1, 2, 4, 5, 5}；最后len减1，有效元素是{1, 2, 4, 5}。那个停留在末位的“5”虽然还在内存里，但因为len已经变成4，没有任何逻辑会再去访问它，通常不需要专门清理。

这里有一个很容易被忽略的问题：删除操作对数组末尾的老值没有自动清零。如果你把整个数组打印出来，会看到最后一个位置还存着旧值。这是正常的，因为在C语言中“数组长度”本质上只是你的一块“约定”，你必须用len来管理有效区间，而不是依赖数组末尾有什么特殊标记。

3.3 循环左移和右移：整组数据搬家

循环移动是另一种常见的数组移动操作：把整个数组向左移一位或向右移一位，移出去的元素绕到数组另一端。

循环左移一位：先把第一个元素存到临时变量，然后从第二个元素开始，每个元素往前挪一位，最后把临时变量放到末尾。

// 数组循环左移一位 void rotateLeftOne(int arr[], int n) { if (n <= 1) return; // 只有一个元素或空数组，不需要移动 int first = arr[0]; for (int i = 0; i < n - 1; i++) { arr[i] = arr[i + 1]; } arr[n - 1] = first; }

循环右移一位：先把最后一个元素存到临时变量，然后从倒数第二个元素开始，每个元素往后挪一位，最后把临时变量放到开头。

// 数组循环右移一位 void rotateRightOne(int arr[], int n) { if (n <= 1) return; int last = arr[n - 1]; for (int i = n - 1; i > 0; i--) { arr[i] = arr[i - 1]; } arr[0] = last; }

这两个操作本身不难，难的是理解为什么必须把端点元素临时保存起来。你如果把数组想象成一排人，左移一位就是第一个人走到最后，其他人依次往左补位。如果不提前记住第一个人的位置，第一个人走了之后他的位置马上会被第二个人占据，后面就找不回来了。

如果你要循环移动k位，最简单的方式是执行k次单位移位操作，但这样效率是O(k*n)。更好的方案是“三次反转法”：先把整个数组反转，再反转前半部分，再反转后半部分。这个方法在不少面试题里会出现，如果你现在只求掌握基础，可以先记住单位移位的写法，反转法放到后面的练习题里挑战。

3.4 数组移动为什么这么重要

很多初学者觉得插入、删除、移位是“数组的基础操作”，和排序有什么直接关系？实际上关系大得很。插入排序的每一趟都在做“后移腾位”，这就是数组移动的典型应用；删除元素时覆盖移动的操作思路，在数组去重、合并等场景里也会反复出现。可以说，你把这几个移动操作练熟，写排序算法时的手感和速度都能提升一个档次。

我自己带新人的时候经常看到一种情况：讲解插入排序时，很多人代码能背下来，但被人问一句“为什么后移时要倒着来”，就卡住了。原因就是他们只背了代码，没有真正理解“数组移动”的底层逻辑。反过来，如果你已经熟练掌握了插入和删除的移动方向规律，那么插入排序的代码根本不用背，顺着思路自然就写出来了。这也是我把“数组移动”单独拎出来放在排序三兄弟之后讲透的原因。

4. 新手最容易踩的坑：边界、越界与调试思路

4.1 sizeof陷阱：数组长度到底是几

写C语言排序时最容易错的第一坑，不是在排序函数内部，而是在主函数里求数组长度。初学者很自然地写int n = sizeof(arr) / sizeof(arr[0]);，这在主函数里是对的，但一旦你把数组传给函数，在函数内部再用同样的写法，就会出问题。

原因在于：C语言传数组给函数时，数组会“退化”成指针。sizeof(arr)在函数内部得到的是指针的大小（通常是8字节或4字节），而不是整个数组占用的字节数。于是sizeof(arr) / sizeof(arr[0])结果可能是2或者1，而不是你期望的数组长度。

所以正确做法是：在主函数定义数组时算好长度，把长度作为参数传给排序函数。这也是我前面所有代码都写成void bubbleSort(int arr[], int n)的原因。你在做练习时如果发现排序结果只处理了前几个元素，先去检查一下是不是在函数内部重新用sizeof算了长度。

4.2 越界和边界条件：一个元素、重复元素、空数组

数组越界是最折磨人的问题，因为C语言不像一些高级语言会在越界时直接报错，它只是无脑访问那块内存，程序可能碰巧运行正常，也可能莫名其妙崩溃，或者出现非常离谱的排序结果。

以冒泡排序为例，内层循环写成for (int j = 0; j < n - i; j++)时，最后一轮会访问arr[j+1]即arr[n-i]，当i=0时就是arr[n]，已经越过数组最后一个有效元素。C语言不会拦着你，但你会读到数组后面内存里的垃圾值，这些垃圾值如果小于arr[j]，就会参与交换，排序结果自然是一团糟。

边界测试是排查这类问题的最好办法。建议你每次写完排序函数，多用以下几组数据跑：

• 一个元素的数组{42}：应该原样输出。
• 已经有序的数组{1,2,3,4,5}：不应该出错。
• 完全逆序的数组{5,4,3,2,1}：最能暴露边界问题。
• 包含重复值的数组{3,3,1,2,3}：检查是否漏排。
• 空数组（n=0）：你的循环是否直接跳过。

把这几组数据输入跑一遍，绝大多数边界错误都会现出原形。

4.3 交换三步法别写错

交换两个元素是排序算法里最基础的操作，但“交换写错”的概率比想象中高得多。最常见的是这么写：

arr[j] = arr[j + 1]; arr[j + 1] = arr[j];

这个写法本质上是把arr[j]的值赋值给arr[j+1]，然后又把它赋回去，结果什么都没换。正确写法必须借助一个临时变量，形成“三步走”：先把arr[j]的值存入temp，再把arr[j+1]的值赋给arr[j]，最后把temp的值赋给arr[j+1]。

有些同学会想，能不能用异或交换省掉临时变量？比如a ^= b; b ^= a; a ^= b;。确实可以，但我不建议初学者这么做，因为可读性差、容易出错，而且对某些极端情况也不如临时变量来得直观。排序已经是入门阶段最需要“写清楚”的代码，没必要在这种地方炫技。老老实实用temp三步法，保证不出错，也方便别人读你的代码。

4.4 调试技巧：打印数组跟踪过程

很多人写完排序发现结果不对，第一反应是盯着代码看半天，或者去查别人的实现。我的建议是：不要干看，用printf把每一趟的结果打出来。做一个打印函数，在每趟循环里调用，你会非常直观地看到“第几趟排序后，数组变成了什么”。

比如在冒泡排序的每趟外层循环结束时加一句printArray(arr, n);，输出大概是这样的：

第1趟: 3 8 1 7 5 6 2 4 0 9 第2趟: 3 1 7 5 6 2 4 0 8 9 ...

看到第1趟结尾是9，你就知道这一趟把最大值送到底了；如果第2趟结尾是8，说明第二个最大值也归位了。这个逐步打印的方法几乎能解决80%的排序调试问题。等确定函数逻辑没问题之后，再把打印语句删掉就行。

插入排序更适合在“每一趟结束后”打印，因为它的每一趟会把前缀区间变成有序的。你可以看到前缀长度在逐渐扩大，这比空想“整体有序”要真实得多。调试不是丢人的事，恰恰是快速建立代码手感的最短路径。

5. 配套练习题：从基础到进阶一次练到位

5.1 基础巩固题：理解算法逻辑

先来几道不太动脑、但能帮助你熟悉代码结构的题。每一道都建议先自己写，再对照上面的代码，不要直接复制。

题1：降序冒泡。把冒泡排序改成从大到小排序，并增加一个变量统计整个排序过程中发生了多少次交换。最后输出排序结果和交换次数。

题2：选择排序追踪过程。输入一个长度为10的数组，每完成一趟选择排序后，打印一次当前数组的状态。运行后写下三句话：这一趟选出的最小值是谁？它被放到了哪个位置？交换了几次？

题3：插入排序手动模拟。用插入排序对数组{8, 3, 9, 1, 4}进行排序。在草稿纸上，写出每一趟结束后数组的内容，以及被移动过的元素有哪些。画出key的移动路径。

题4：逆序输出。不修改原数组，将数组元素逆向打印出来。然后再写一个reverseArray函数，把数组原地反转，并打印反转后的结果。注意区分“逆向打印”和“原地反转”这两种不同的需求。

这几道题做完，至少能保证你在面对机考基础题时，不至于手抖写出越界代码。

5.2 进阶实战题：数组移动的灵活运用

题5：删除指定元素。输入一个数组和一个值x，删除数组中所有等于x的元素，返回删除后的数组长度，并保证元素的相对顺序不变。比如{1, 2, 3, 2, 4, 2}删除2后变成{1, 3, 4}。提示：一个主循环遍历原数组，用一个“新长度指针”记录不删除的元素应该放到哪里。

这道题是典型的“双指针”入门，表面上是数组移动，实际上是在为以后学快慢指针、处理有序数组去重打基础。

题6：把0移到末尾。给定数组{0, 1, 0, 3, 12}，把所有的0移动到数组末尾，同时保持非0元素的相对顺序。输出{1, 3, 12, 0, 0}。这道题看起来和题5像，但要求不同，需要你动脑筋想一下怎么用一次遍历完成移动。

题7：循环右移k位。实现一个函数rotate(int arr[], int n, int k)，把数组循环右移k位。k可能是负数（表示左移），也可能大于n（需要取模）。你至少要写出两种实现：一种是用额外数组（简单，O(n)空间），另一种是在原数组上通过三次反转完成（O(1)空间）。把两种都写出来，你就会发现“为什么”三次反转能成立。

题8：合并两个有序数组。有两个已经排好序的整数数组A和B，把B合并到A中，使合并后的A仍然有序。这是排序算法中“归并”思想的最小原型。建议限制自己不用额外数组，直接在A上从后往前填充。提示：比较两个数组末尾较大的元素，从A的尾部开始放。这道题做一遍，你对“从后往前移动”的理解会上升到新层次。

5.3 思考题：近乎有序时谁最快

最后留一道不需要写代码的思考题：假设你有一个几乎排好序的数组，比如100个元素里只有两三个元素是放乱了的，让你从冒泡、选择、插入三种排序里挑一个来排，你会选谁？为什么？

答案是插入排序。因为插入排序的时间复杂度在“近乎有序”的情况下会显著下降，最好的情况甚至能做到O(n)。而冒泡排序虽然优化后也能提前退出，但它的交换次数通常更多；选择排序就完全不行了，它无论数据长什么样都必须扫描完所有未排序区间。这道题的结论以后也成立：在正式工程里，很多排序算法会在数据规模较小时切换到插入排序来“兜底”，靠的就是它在这种场景下的高效表现。

我个人的习惯是学排序算法时，不满足于“代码能跑通”，而是每学一个算法都问自己三个问题：最坏情况是什么？最好情况是什么？它适合出现在什么场景？这三个问题想明白了，排序从“背代码”变成了“选工具”，你对数组的理解也会顺手打通。这组练习题你不用一下全做完，拆成三天也行，但每一道都值得用纸笔把过程画一遍。排序这点事，练扎实了，后面的路会顺很多。