企业官网建设流程全解析

今天是我这个“大一小登”从零学算法的第三天。前两天刚把数组和暴力枚举折腾明白，还发了两篇打卡笔记，今天本来想直接开搞二分查找，结果打开刷题网站第一道题就给我来了个排序，还是那种不加优化就超时的。于是整个下午到晚上，我就跟冒泡排序、选择排序、插入排序这三兄弟杠上了。

如果你也刚接触算法，对排序的理解还停留在“直接调 sort 不就完了吗”，那我劝你先别急着调库，花一晚把这三兄弟手写一遍。排序代码看着短，但里面藏的循环控制、边界处理、复杂度分析，几乎把算法入门最重要的基本功一网打尽。今天这篇不将就，从原理到代码再到调试，一步不落，争取让零基础的人也能照着敲出来。

1. 为什么算法入门要先磨排序这道坎

1.1 排序背后藏着的三大基本功

很多人觉得排序太基础、太简单，不值得专门花时间。但我自己的真实感受是：写排序时，你无意识中在练三样特别重要的东西——数组下标操作、双重循环控制、以及交换变量的基本功。

先说数组下标。排序里到处都是a[j]、a[j+1]、a[minIndex]这种访问，下标一多，人就容易晕。尤其是插入排序里那个“移动元素”的过程，a[j+1] = a[j]和a[j] = a[j+1]写反了，整个结果就是错的。这种对下标的敏感度，只能靠反复写排序来练。

再说双重循环。冒泡、选择、插入全是“外层循环控制第几轮 + 内层循环控制本轮怎么比较/查找”。内外层循环的起点、终点、边界条件，每道排序题都有微妙的差别。如果你能把三种排序的循环边界都想清楚，后面学快排、归并、二分这些还不是手到擒来。

1.2 从暴力枚举到排序：为什么不能靠猜

第二天我学了暴力枚举，当时觉得“凡事枚举一下不就行了”。但今天看到排序题我就明白了，枚举这条路根本走不通。比如给 5 个互不相同的数排序，所有排列可能是 5! = 120 种，你还能勉强列一列；但如果是 50 个数，那排列数是 50!，这个数比宇宙中的原子数量还大得多，枚举过去你电脑早烧了。

暴力枚举之所以叫暴力，就是我们不用任何规律，一股脑把所有可能都试一遍。而排序之所以需要算法，是因为人类早就总结出了“通过两两比较和交换，可以一步一步逼近有序”的规律。这个规律，说白了就是把大问题拆成一轮一轮的小问题，每一轮解决一小部分，最后让整个数组有序。这就是所谓“循环不变式”思想的雏形，也是后续所有排序算法的底层逻辑。

2. 冒泡排序：用“冒泡”理解循环和交换

2.1 每一轮把最大的“泡”漂到末尾

冒泡排序的原理很形象：数组里相等的相邻元素，如果左边的比右边的大，就交换位置。因为大的元素会像水底的气泡一样慢慢往上浮，所以叫冒泡。

具体过程是这样：第一轮，从第 0 个位置开始，依次比较相邻的两个数。如果前一个比后一个大，就交换它们。这样一路比较到数组末尾，最大的数就会被交换到最后一个位置。第二轮重复同样的过程，但可以不用管最后一个位置了，因为它已经是全数组最大的了。第三轮再缩减一个比较范围……直到所有轮次结束。

我刚开始学的时候，总喜欢把冒泡想成“把最大的数往后拖”，后来我才意识到，它其实是“相邻两个数两两比较，谁大谁就被推向右边”。这个区别很重要，因为只有相邻比较，才能保证相等元素的相对顺序不被打乱，这也是冒泡排序“稳定”的原因。

2.2 手写代码：内外两层循环怎么定边界

冒泡排序的代码框架非常固定，核心就是两层循环。我先把 C++ 版本写出来，再解释为什么边界要这么定。

#include <iostream> using namespace std; void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); } } } }

外层循环i表示已经排好了几个最大的数，所以总共需要n-1轮。因为当n-1个数归位后，剩下的那个数自然就处在正确位置了，不用再排。内层循环j表示当前这一轮要比较到哪，用n-1-i而不是n-1，是因为后i个数已经在上几轮排好了，再比较它们纯粹是浪费。

我第一次写的时候，内层循环写成了j < n - 1，结果每轮都会把已经排好的最大数再比较一遍。虽然排序结果没错，但白白多跑了很多次，数据一多就超时。所以这个- i是冒泡优化的第一步，也是理解“规模递减”的好例子。

2.3 提前退出的优化，让最好情况变成 O(n)

冒泡排序还能再加一个优化：在内层循环里设置一个布尔变量swapped，只要本轮发生过交换，就说明数组还没完全有序，继续下一轮；如果某一轮从头到尾一次交换都没有，说明数组已经完全有序，直接终止循环。

void bubbleSortOptimized(int a[], int n) { for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; } } if (!swapped) break; } }

最好情况是什么？是数组原本就完全有序。第一轮从头到尾比较一次，发现没有任何交换，swapped为 false，直接跳出。这种情况下，比较次数是n-1，时间复杂度是 O(n)。而最坏情况是数组完全逆序，每一轮都得完整比较交换，总次数是n(n-1)/2，也就是 O(n²)。平均情况差不多也是 O(n²)。所以你以后看到网上说“冒泡排序最好 O(n)、最坏 O(n²)”，说的就是加了提前退出优化的版本。

3. 选择排序：最符合直觉的“挑最小放前面”

3.1 思路非常直接

选择排序的思路是我见过最像人类直觉的：遍历一遍数组，找到最小的那个数，把它放到第 0 位；再从第 1 位到末尾重新找最小，放到第 1 位；再从第 2 位到末尾找最小，放到第 2 位……重复这个过程，直到数组有序。

我第一次听这个概念就想：“这不就是平时整理书架吗？把最左边的书先找出来，放好，再整理剩下的架子。”思路确实简单，代码写起来也没那么绕。但越简单的代码，越容易在细节上翻车。

3.2 代码实现：内层循环起点最容易写错

直接看代码：

void selectionSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[minIndex]) { minIndex = j; } } if (minIndex != i) { swap(a[i], a[minIndex]); } } }

外层循环i表示“当前要确定的第 i 个位置”，所以范围是0到n-2。最后只剩一个元素时，它一定是最大的，不用再管。内层循环从i+1开始扫描，目的是找到从i到n-1中最小元素的下标。

最容易写错的地方有两个。一个是不小心把内层循环起点写成i，或者写成0，结果每一轮都在全数组找最小，前面的顺序就被搅乱了。另一个是忘记记录“最小值的下标”，直接用一个变量存最小值本身。这样也能排，但交换时你得再遍历一遍找下标，效率低，而且代码容易出 bug。记住：这里存的是minIndex，不是minVal。

3.3 选择排序不稳定的坑

关于选择排序，面试和考试最喜欢问一个概念性问题：“选择排序稳定吗？”

答案是：不稳定。

举个例子，数组[5a, 5b, 3]，其中 5a 和 5b 是两个值相等的 5，用下标区分。第一轮选择排序找到最小值 3，下标 2，把它和下标 0 的 5a 交换。交换之后数组变成[3, 5b, 5a]。你看，5a 和 5b 的相对位置变了：原来 5a 在 5b 前面，现在 5a 跑到 5b 后面去了。稳定性的定义是“相等元素的相对顺序在排序前后保持不变”，选择排序做不到，所以它不稳定。

这个坑非常经典，面试时不知道会吃大亏。关键是理解它为什么不稳定：因为选择排序每次找最小值的那个“交换”是跨度很大的交换，很可能把一个靠前的相等元素一下子甩到后面去。如果你想保持稳定性，就不能随心所欲地交换，得像插入排序那样一个一个移动。

4. 插入排序：打扑克牌的时候你已经在用了

4.1 像理扑克一样把牌插进去

插入排序的思路，我每次解释给朋友听都用打牌的例子。你平时抓牌的时候，是不是会把新抓到的牌插到手里已经排好顺序的牌中？插入排序就是这么干的。

具体过程：把数组看成两部分，左边是已排序区，右边是未排序区。最开始已排序区只有第 0 个元素。然后从第 1 个元素开始，每次把“当前这个元素”想办法插入到左边的已排序区中，使已排序区始终有序。一直处理到最后一个元素，整个数组就有序了。

这个思路和冒泡、选择有本质差别。冒泡和选择是“每轮确定一个最终位置”，而插入是“每轮把一个新的元素融入到已经有序的前缀里”。所以插入排序对“基本有序”的数组特别友好，因为它不需要大幅度交换，只要做很少的移动就行。

4.2 代码实现：移动元素而不是交换

插入排序的实现有一个关键点：通常不是用swap，而是用一个临时变量key存住当前元素，然后把前面那些比key大的元素整体向后移动一格，最后把key放到空出来的位置。

void insertionSort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } }

为什么不用swap？因为swap每次交换会多做一个临时变量的操作，而且逻辑上不够直白。插入排序的核心是“腾位置”：把比key大的元素往右挪，相当于在已排序区里“腾”出一个位置，然后把key稳稳放进去。虽然最终效果和交换差不多，但移动法对理解“数组插入”这个操作更深。

边界条件非常关键：while循环里必须写j >= 0，否则你会去访问a[-1]，程序直接崩溃。我昨天晚上就是漏了这个条件，结果用数组的第一个元素访问越界，排查了大半天。你千万别踩这个坑。

4.3 同是O(n²)，为什么插入更难对付

如果只看最坏情况，插入排序和冒泡、选择一样，都是 O(n²)。但在实际工程里，插入排序往往比冒泡和选择快，原因在于它利用了“局部有序”这个性质。

最好情况下，数组已经排好序，插入排序每轮只需要比较一次，发现左边元素已经比key小，直接退出循环。总比较次数是n-1，时间复杂度 O(n)。对于“几乎有序”的数据，插入排序的常数非常小，表现极好。这也是为什么很多高级排序算法（比如快速排序）在处理小规模子数组时会退回插入排序的原因之一。

另外，插入排序是稳定排序。它做的是相邻移动，不会跨距离交换，所以相等元素的相对位置不会被打乱。

5. 三兄弟对比与选型指南

5.1 一张表看清三兄弟的差别

三种排序学完之后，对照着看是巩固的最好方式。我整理了一张表，你把这张表背下来，面试手撕排序基本就稳了。

很多人看到了会说：“冒泡和插入最好时间不都是 O(n) 吗，为什么平均还都 O(n²)？”因为平均情况是考虑所有可能的输入排列后取平均，不是最好情况。三种排序的平均复杂度都是 O(n²)，这是它们相同的地方；真正区分它们的是最好情况的表现、稳定性和交换次数。

5.2 什么场景该选哪一个

虽然现实里很少自己手写这些排序，但刷题和面试时经常要手推“该用哪个”。我的经验是：

• 如果数组接近有序，果断用插入排序，它能在近乎线性的时间内完成排序。
• 如果你必须保持相等元素的相对位置，用冒泡或插入，别用选择。
• 如果需要交换次数尽量少，用选择排序。因为它每轮最多只交换一次，而冒泡可能一轮要交换很多次。写入磁盘等交换成本高的场景，选择排序可比冒泡香多了。
• 如果只是想快速写个排序且不关心性能，冒泡最好写，也最不容易错，适合当兜底。

但说到底，这只是入门阶段的选择。真正生产环境或刷题时数据量一大，还是会用sort()或者快排、归并这类 O(n log n) 的算法。不过把这三兄弟吃透，你再看快排和归并，理解会快非常多。

6. 实操过程：从零手写并调试三种排序

6.1 准备一个可以“看见过程”的开发环境

学算法不写代码等于白学。我推荐你在本地装一个简单的 C++ 开发环境，VS Code + MinGW 或者直接用在线编译器都行。但我更推荐在本地跑，因为你后面要调试、要打印过程，在线编译器会麻烦一些。

新建一个sort.cpp文件，把三种排序加一个主函数放进去，然后编译运行。如果你用的是 Linux/Mac 的终端，直接g++ sort.cpp -o sort && ./sort就能跑。Windows 上如果配好了 MinGW，也是同样的命令。

6.2 完整代码与测试用例：直接用数组 [3,44,38,5,47,15,36,26] 验证

下面我写一个可直接运行的完整程序，里面包含三种排序，并打印每一轮排序后的数组。这样你一眼就能看出每一轮做了什么。

#include <iostream> using namespace std; void printArray(int a[], int n) { for (int i = 0; i < n; i++) cout << a[i] << " "; cout << endl; } void bubbleSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; } } cout << "第 " << i + 1 << " 轮冒泡: "; printArray(a, n); if (!swapped) break; } } void selectionSort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int minIndex = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[minIndex]) minIndex = j; } if (minIndex != i) swap(a[i], a[minIndex]); cout << "第 " << i + 1 << " 轮选择: "; printArray(a, n); } } void insertionSort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; cout << "第 " << i << " 轮插入: "; printArray(a, n); } } int main() { int arr1[] = {3, 44, 38, 5, 47, 15, 36, 26}; int n = sizeof(arr1) / sizeof(arr1[0]); cout << "原始数组: "; printArray(arr1, n); cout << "\n=== 冒泡排序 ===\n"; bubbleSort(arr1, n); int arr2[] = {3, 44, 38, 5, 47, 15, 36, 26}; cout << "\n=== 选择排序 ===\n"; selectionSort(arr2, n); int arr3[] = {3, 44, 38, 5, 47, 15, 36, 26}; cout << "\n=== 插入排序 ===\n"; insertionSort(arr3, n); return 0; }

我建议你把代码原样敲一遍，不要复制粘贴。因为敲代码时会强迫你自己过一遍逻辑，尤其是while (j >= 0 && a[j] > key)这条条件，手指记住和眼睛记住是完全不一样的。运行之后，仔细观察每一轮的输出，和自己在纸上推演的结果对比，印象才深刻。

6.3 验证排序写没写对的三个土办法

代码跑出来是排好序的，不代表你一定写对了，因为普通测试用例太简单。我一般用三个土办法验证排序是否真正正确：

第一，边界测试。写一个空数组[]、一个单元素数组[1]、两个元素的数组[2,1]，分别跑一遍。空数组最容易出现“莫名其妙进入循环”的情况，单元素数组最容易出现越界。

第二，重复元素测试。比如[2,2,2,1]，看看相同元素会不会被奇怪地改动。如果你的比较条件用了<=而不是<，排序虽然能完成，但可能影响稳定性，甚至多做无用的交换。

第三，随机大数组交叉验证。手动生成一个包含几千个随机数的数组，用自己写的排序跑一遍，然后用库函数sort（或 Python 的sorted()）也排一遍，最后逐位对比是否一致。这个办法我几乎天天用，帮我抓出了无数个隐蔽的 off-by-one 错误。

7. 常见问题与排查技巧实录

7.1 排序结果不对，先打印每轮数组

我写代码有个习惯：出 bug 了第一件事不是盯着屏幕发呆，而是加打印。把每轮排序后数组的状态打印出来，看着输出结果找规律就好办了。

比如冒泡排序，如果你发现第一轮结束后最大的数出现在最前面而不是最后面，那大概率是内层循环的比较方向写反了，把a[j] > a[j+1]写成了a[j] < a[j+1]，导致小的往下沉，大的往上浮。

选择排序如果发现排出来像“隔一个错一个”，多半是内层循环的j起点写错了，写成0导致每一轮都在全数组找最小，搅乱了前面已经排好的部分。打印一轮你就瞬间明白了。

插入排序如果发现某个元素“漂移”了，比如key被放到数组最后而不是它该去的位置，基本可以断定是while循环的条件写反了，把a[j] > key写成了a[j] < key，结果是比 key 小的元素被一直往后挪，key 被推到最右边。

7.2 数据一大就卡住，可能是复杂度爆了

有同学会问：“我把排序写对了，但数据一多就卡死，是电脑太差吗？”

不是。大概率是复杂度太高了。比如你明明只写 O(n²) 的冒泡排序，却用在了十万级数据的测试用例上，跑个上百亿次比较，不卡才有鬼。

这时候两条路：一是优化算法，换成快排或者归并；二是先确认自己的实现有没有做无用功。比如冒泡排序没加提前退出优化，面对已经有序的大数组，仍然傻乎乎地跑完全部轮次，白白浪费大量时间。你可以在代码里插入一个计数器，看看总比较次数和交换次数，如果明显远超你预期，就说明算法实现有冗余。

7.3 边界条件：空数组、单元素、重复元素

最后聊一个特别容易忽略的边界问题。很多新手写的排序函数，参数里如果传入n=0或n=1，循环压根不会执行，函数直接返回，这没问题。但如果你在函数里用了a[0]来做某些初始化，而n=0时a[0]根本不存在，程序就崩了。

重复元素更是隐藏的坑。我之前写选择排序时，测试一个全是相同元素的数组，发现某些位置的值偶尔会变成 0，排查半天才发现是minIndex初始化成了i，但代码写成了int minIndex = 0，导致每一轮都拿第 0 个元素和后面比较，不仅结果可能是错的，还会把不存在的空位置算进去。

所以每次写完排序函数，建议固定跑三组测试：空数组、单元素数组、重复元素数组。这三组过了，基础正确性就有保障了。

最后再说点个人体会。这三种排序代码确实短，但你要以为看看就能懂，那真的是想多了。我昨天把三个排序各手写了一遍，每一遍都写了至少半个小时，里面小错误不断：边界写错、方向写反、minIndex 的初始化位置错掉……写到第三遍的时候，那些错误才基本消失。

我曾经听一个学长说过：“排序算法入门你就学三件事：写熟冒泡、理解选择、掌握插入。学完之后算法的大门才算真正打开。”当时我还不以为然，今天写完这三种排序，再回头看这句话，确实有道理。你也不要急，一天一个算法，写熟了再往前走，后面的路会顺畅很多。