从0学算法第三天：四种基础排序与时间复杂度实战解析

说实话今天这一天学得有点刺激。昨天我还觉得算法就是“暴力循环一把梭”今天光是交换两个数就写到手抽筋终于理解了为什么学长们总说排序算法是算法大厦的砖头。如果你也是从零开始学算法看到“第三天”这个标题先不要慌今天没有高深莫测的数学推导核心就一件事——把四种最基础的排序算法吃透。1.1 前两天我到底学了个啥先交代一下进度方便后来的人跟上节奏。第一天我干的事情是理解时间和空间复杂度什么是 O(n)什么是 O(n^2)为什么一段双层循环比单层循环慢那么多。那时候我是拿求和来感受的——单层循环算 1 累加到 n 是 O(n)双层循环每对数字比较一次是 O(n^2)。第二天我开始碰数组、循环和函数把 for 遍历数组写顺了也简单了解了栈和队列的入出逻辑。这些听起来零散但今天全都要用上。为什么要特意提基础因为我发现很多新手包括昨天的我会一头扎进“看大佬刷题视频”上来就想学动态规划结果连个冒泡都写不利索。第三天学排序其实是把前两天的基本功做一个打包应用数组下标、循环边界、遍历、交换、函数封装每一个都会在排序代码里反复出现。如果你正准备入门我的建议是先别跳步把这三样基本功练到闭眼能写再来看今天的排序。1.2 排序在算法学习里的位置第三天为什么要学排序而不是直接上贪心、动态规划那些“听着就很高级”的东西因为排序是所有算法学习里性价比最高的一块垫脚石。先说最直白的理由后面的算法一大半要建立在“有序”之上。二分查找的第一前提是数组有序很多贪心策略的第一步就是把数据排序合并区间要排序求逆序对要排序甚至做结构体排序的时候你还得理解稳定的意义。可以说不会排序后面做题会处处卡壳。另外从应试角度来看蓝桥杯、LeetCode 这些平台上的入门题排序题的占比特别高。大一小登最需要的就是正反馈先 AC 几道排序题信心就起来了。更关键的是排序算法能一次性锻炼好几种算法基本功遍历、交换、递归、分治、稳定性判断。尤其是归并排序里的递归和分治思想那不只是排序更是后续很多复杂算法的思维模板。我愿把这天称为“从照着循环写代码到开始思考算法怎么做”的转折日。1.3 这一天我的验收标准我今天没有给自己定特别离谱的目标就四条不看模板手写冒泡、选择、插入、归并四种排序能说清每种排序的时间复杂度、空间复杂度和稳定性能用随机数据验证自己写的排序是对的最后在刷题平台上 AC 一道排序题。如果你今天也跟我一样从零学到这里可以用这四条给自己做个检查。为什么要定“能验证”这个标准因为在没有老师盯着的情况下光看讲解视频很容易产生“我会了”的错觉。手写一遍是一层能运行正确是另一层能说清原理才是真正入脑。所以接下来的每一段我都会把“原理”和“我踩过的坑”放在一起写让大家别重蹈覆辙。2. 冒泡排序手撸实录从“背模板”到“看懂为什么”2.1 一句话思想和第一版代码冒泡排序的思想一句话就能说完从左到右把相邻两个数比较如果左边比右边大就交换这样每一轮会把未排序部分的最大值“冒”到最右边。你可以想象成一排同学按身高站队两个两个比高的往右挪挪到最后那个肯定是全场最高。然后对剩下的 n-1 个人重复这个过程。第一版代码长这样void bubbleSort(int a[], int n) { for (int i 0; i n - 1; i) { // 每轮把最大值挪到 n-1-i 的位置 for (int j 0; j n - 1 - i; j) { if (a[j] a[j 1]) { int temp a[j]; a[j] a[j 1]; a[j 1] temp; } } } }我第一次写的时候最不理解的就是为什么内层循环要写成 j n - 1 - i而不是 j n - 1。后面想明白了外层每跑一轮数组尾部就会多一个已经就位的最大值下一轮根本不用再碰它。比如数组 [5, 3, 8, 2]第一轮结束后 8 已经到最后一个位置了第二轮如果还让 j 跑到 n-2势必要再拿 j 和 j1 比较8 其实是多余的。去掉这个尾巴比较次数正好是 n(n-1)/2不会做无效功。2.2 我的两个翻车现场看模板写冒泡很简单但自己默写的时候我翻了两次车都挺典型的。第一次是把内层循环条件写成 j n - 1。结果是什么每一轮都跑到数组最后一个元素已经就位的最大值被反复比较排序结果不会错但有效率问题。最坑的是这种错很难发现因为小数据跑起来结果是对的只有把循环里打印出来看到尾部元素每一轮都在被重复访问才意识到边界画错了。我的建议是学排序的时候别偷懒把每一次外层循环结束后的数组状态 print 出来你能非常直观地看到“最大值沉底”的过程。第二次是交换写错了经典到不能再经典。我写的不是三行交换而是a[j] a[j 1]; a[j 1] temp;结果就是数组中一个数直接被覆盖丢掉了比如 [3, 5] 变成了 [3, 3]。这种错误不用大数测试根本看不出来尤其在小规模数据上你甚至会怀疑是不是自己看错了。从那以后我写排序都先默认用 swap(a[j], a[j 1])减少手写交换出错的机会。2.3 冒泡排序的优化和复杂度标准冒泡的复杂度是很好算的外层 n-1 轮内层平均差不多 n/2 次比较总比较次数是 n(n-1)/2所以时间复杂度是 O(n^2)。空间上只用一个临时变量所以空间复杂度是 O(1)。但冒泡有一个非常经典的优化加一个标记变量如果某一轮从头扫到尾一次交换都没发生说明数组已经整体有序了直接结束循环。代码是这样的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; } } if (!swapped) break; } }加了标记之后最好情况数组本来就是有序的下内层只要跑一轮就退出复杂度从 O(n^2) 变成 O(n)。别小看这个优化面试里问“冒泡能不能提前退出”其实就是在考这个。另外冒泡排序是稳定排序当 a[j] 等于 a[j1] 时我们不交换相等元素的相对顺序不会被打乱这为后面理解结构体排序里的“保持原有顺序”打好了基础。2.4 一个小记为什么有时候冒泡反而有存在感现在很多人觉得冒泡排序太笨了实际开发里几乎不会用它。但作为算法入门第一课它依然有不可替代的作用所有排序里它最直观让你理解“比较-交换”这个循环模型。而且在小规模数据或教学环境下它的代码最容易写对。我今天的体会是不要因为冒泡简单就跳过手写它的一大堆边界细节正好磨练你对下标的敏感度。3. 选择排序与插入排序同是 O(n^2)性格完全不一样3.1 选择排序每轮把最小的捡出来如果说冒泡是“大的往右挪”选择排序就是“最小的往前放”在未排序的部分中找到最小值把它放到当前的最前面。外层 i 从 0 到 n-2内层从 i1 扫到 n-1记录下最小值的下标 minIdx最后和 a[i] 交换。void selectionSort(int a[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) { minIdx j; } } if (minIdx ! i) { swap(a[i], a[minIdx]); } } }注意这里记录的是下标 minIdx而不是直接把最小值存进某个变量。为什么因为交换的时候你不但需要值还需要知道它在数组里的位置。这也是一个容易想当然的细节我第一次想当然地用一个变量存最小值结果交换时根本不知道该跟谁换。选择排序的交换次数很少最多 n-1 次但比较次数是固定的 n(n-1)/2。所以如果你的数据对象很大交换成本高选择排序的“每次只交换一次”反而有价值。3.2 插入排序像打扑克插牌三种 O(n^2) 排序里我最喜欢插入排序因为它的思想完全就是生活场景打扑克的时候你拿到一张新牌会从左到右或从右到左找到位置插进去手牌永远是有序的。代码里也一样从第二个元素开始把当前位置的值 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; } }这段代码里最容易错的是 while (j 0 a[j] key) 这个条件顺序不能反。如果先判断 a[j] key 再判断 j 0当 j 变成 -1 时就会越界访问。插入排序最好的情况很惊艳数据基本有序时内层 while 基本不执行整体复杂度可以降到 O(n)。正是因为这个特点很多高效排序比如 C 标准库里的 sort在处理接近有序的小数组时会用插入排序收尾。3.3 三者横向对比稳定的、不稳定的、快的慢的把冒泡、选择、插入放到一张表里看会非常清晰排序平均最坏最好空间稳定性冒泡O(n^2)O(n^2)O(n)O(1)稳定选择O(n^2)O(n^2)O(n^2)O(1)不稳定插入O(n^2)O(n^2)O(n)O(1)稳定稳定性怎么看冒泡和插入在元素相等时不交换所以稳定选择排序不稳定因为它在每轮选最小值时会把前面的元素直接跳过。举个例子[5a, 5b, 1]第一轮发现最小的是 1就把 1 和 5a 交换数组变成 [1, 5b, 5a]两个 5 的顺序变了。这个例子在面试八股里经常出现建议记下来。实际跑数据的话在同样随机、同样数据量下插入排序通常会比选择排序快一点因为插入的移动在内存里更连续缓存友好。冒泡因为交换太频繁常常最慢。但对 1000 以内的数据三者耗时差不了多少今天的目标是理解思维不是优化性能。3.4 怎么选什么时候用哪种如果数据量很小比如十几个元素插排最顺手代码也简单。如果担心中间有大量结构体交换选择排序的“交换次数少”可以考虑。冒泡嘛教学意义大于实战意义。不过这些都是“流程性理解”真正竞赛里数据量上来之后不会用 O(n^2) 的排序顶至少会先上快排或归并这个后面再说。4. 归并排序第一次真正体验到“分治”的存在感4.1 核心合并两个有序数组到归并排序这里思路突然就变了。前面三种都是在一个数组内部比较交换归并排序则引入了“分治”把数组从中间劈成两半左半边和右半边各自先排好序然后合并成一个有序整体。这种“大事化小、小事化无再把结果合起来”的思路就是分治。合并两个有序数组本身不难用双指针就行两个指针分别指向两半头部谁小谁先进临时数组某一边先放空了另一边剩下的整体拷进去。生活里也有对应场景你有两堆已经按身高排好的小朋友要合成一排只需要每次从两堆队头里挑较矮的出队直到一堆先空再把另一堆整体接上去。4.2 完整递归代码和几个容易错的地方void merge(int a[], int left, int mid, int right) { int n right - left 1; int* tmp new int[n]; int i left, j mid 1, k 0; while (i mid j right) { if (a[i] a[j]) { tmp[k] a[i]; } else { tmp[k] a[j]; } } while (i mid) tmp[k] a[i]; while (j right) tmp[k] a[j]; for (int t 0; t n; t) { a[left t] tmp[t]; } delete[] tmp; } void mergeSort(int a[], int left, int right) { if (left right) return; int mid (left right) / 2; mergeSort(a, left, mid); mergeSort(a, mid 1, right); merge(a, left, mid, right); }这里容易错的地方有三个。第一个是临界条件left right 直接返回我是靠递归树才想明白的因为单个元素已经是有序的。第二个是拷回原数组时的下标a[left t] tmp[t]不是 a[t] tmp[t]这个错会导致返回后数组后面一段被覆盖我第一版就是这么挂的。第三个是 mid 的计算数据量小的时候 (left right) / 2 没问题但严谨写法是 left (right - left) / 2防止 left right 溢出算是好习惯。4.3 用递归树推导时间复杂度归并排序的复杂度推导和前面几种“数循环”不一样得靠递归树。递推式写出来是 T(n) 2T(n/2) O(n)意思是处理 n 个元素的开销等于处理两个 n/2 子问题再加一次 O(n) 的合并。画成递归树的话第一层合并 n 个元素第二层有两个部分合起来也是 n 个元素第三层四个部分加起来还是 n 个元素……每一层都要处理 O(n) 的数据而层数是 log2 n所以总复杂度是 O(n log n)。空间上不要被 O(1) 骗了归并排序需要额外的临时数组空间复杂度是 O(n)。它不是原地排序。后面如果去面试这个会被追问要提前有意识。4.4 彩蛋归并排序顺带解决逆序对为什么我喜欢在今天讲归并还有个原因有一个高频题叫“求逆序对数量”归并排序的合并过程天然就能统计。合并时如果左边的 a[i] 右边的 a[j]说明左半部分从 i 到 mid 的所有元素都和这个 a[j] 构成逆序对直接一次加上 mid - i 1 个就行。这比暴力一个个数快得多。这个彩蛋现在不用全部消化今天只要理解一个点排序算法不只是把数据排整齐它内部的信息往往能“顺带”解决其他问题。这种观察力比单纯背排序代码重要得多。5. 学完排序之后的第一轮实战我拿这些题练手5.1 刷题平台和心理建设学到第三天光看不写肯定不行。平台方面我自己用的是蓝桥杯题库和 LeetCode蓝桥杯的题更契合竞赛LeetCode 的题更偏向面试风格。作为大一新生别一上来就挑困难题先把模板题 AC再往后延伸。一个很重要的心态调整第一天刷题没 AC 的时候我真会怀疑自己智商今天已经接受了“调试半小时、提交 WA”是常态。手写排序出现 WA多数不是思路问题而是下标和边界问题。我自己的做法是每道题先打印中间变量确认排序过程符合预期再提交。别嫌土这个习惯能帮你把“我大概会了”变成“我真的写对了”。5.2 三道适合第三天的练习题推荐三道题按顺序做。第一道基础排序模板题输入若干个整数从小到大输出。要求冒泡、选择、插入、归并各写一遍不要用 sort 函数。这道题的意义在于四种写法都过一遍确保不是只会背其中一种。第二道排序后求相邻两数的最大差值。比如数组 [3, 1, 8, 4, 11]排完序扫一遍看相邻两个数的差值谁最大。如果你用 O(n^2) 的冒泡去跑大数据会直接超时这样你就能亲身体会到“复杂度不是概念是会超时的”。这道题很适合做“从排序过渡到算法复杂度”的接点。第三道逆序对。这一题有点难但因为今天学了归并排序正好可以拿来做。你要是能在第三天把逆序对调通后面很多分治题都会轻松一些。顺便提一嘴热搜里那个“找下一个身高更高的小朋友”名字听着像排序题其实是单调栈的经典题靠的是栈而不是排序。别被名字坑了等后面把栈学扎实了再回去做。5.3 我用的“土办法”验证排序怎么确认手写排序没问题我有一个超级土但实用的验证流程随机生成几组数组用 std::sort 排一遍当标准答案再跟自己写的排序结果对比。全对之后把数据量加大再测一轮。另外写一个 isSorted 函数检查排完序后数组是否满足 a[i] a[i1]bool isSorted(int a[], int n) { for (int i 1; i n; i) { if (a[i] a[i - 1]) return false; } return true; }这个方法看起来很基础但它会给你非常诚恳的反馈。尤其是那种“小数据碰巧对、大数据就错”的排序随机测试很快就能暴露出问题。我今天靠这个流程发现了好几个边界 bug比肉眼盯着代码管用多了。5.4 一个小提示别急着离开手写也别抗拒 std::sort最后说点真心话。我知道 C 自带 std::sort底层是内省排序综合快排、堆排、插入排序日常开发用它是绝对正确。但既然你正处于“从零学算法”的阶段前三天请老老实实把手写排序练熟。如果一上来就只会调用 sort你可能永远体会不到“为什么插入排序在小数组里很香”“为什么归并排序能顺便求逆序对”。等你能把快排和归并也手写顺了再回头用 std::sort心态完全不一样。第三天结束的时候我最大的感受是算法这东西看视频和写代码完全是两回事。今天我调试最久的不是归并反而是那个交换写错的冒泡丢数都不知道怎么丢的。但恰恰是这种翻车让我第一次真正记住了“稳定”“逆序对”“分治”这些概念不再是背下来的名词。明天我准备进攻二分查找不过睡前还是要把今天这四种排序各默写一遍保持住手感。