排序算法全解析：从冒泡到归并，掌握复杂度与优化

在数据结构这门课里，排序算法永远是绕不开的主线话题，考研笔试要考、面试手撕代码要考、工作里处理数据也随时可能用到。很多人学排序是死记硬背代码，今天记住了冒泡排序长什么样，明天换成快速排序又从头硬记一遍，最后考完试全部忘光。其实排序算法的每一行代码都是能推出来的，它背后靠的是几组非常朴素的直觉：怎么把无序变成有序、怎么减少不必要的比较、怎么利用已有的顺序。这篇文章我打算从零开始把排序算法完整拆一遍，先讲清楚分析排序的几个核心工具，再把冒泡排序、选择排序、插入排序逐个推到你能闭着眼睛写出来的程度，最后聊一聊归并排序这个从 O(n²) 跨到 O(n log n) 的分治思维拐点。整篇内容面向初阶读者，你不需要有很强的算法基础，只要会写最基本的循环和函数，能看懂数组下标，跟着思路走就能吃透这一篇。适合正在学数据结构的学生、准备校招面试的开发者，以及想系统梳理排序知识但一直被各种零散博客搞晕的人。

1. 排序问题的本质：比较、交换与复杂度直觉

1.1 把排序抽象成一个“比较 + 交换”的模型

排序问题表面上是“把数组排整齐”，但真正动手写算法之前，得先把问题抽象出来。几乎所有基于比较的排序算法，本质上都在重复两件事：比较两个元素的大小，决定它们的先后顺序；交换两个元素的位置，让它们朝正确的方向移动。为什么这个抽象很重要？因为你一旦把排序看成“比较 + 交换”的组合，几乎所有排序算法的代码都能直接从这句话里长出来。

比如数组 [5, 3, 8, 1] 要升序排列，你随手写的“把第一个数往后比，大的往后挪”这种操作，本质上就是一个比较和交换的循环。冒泡排序是相邻两个比，选择排序是“打擂台式”地比出最值再交换，插入排序则是往前比、腾位置、插入。三种算法代码长得完全不一样，但底层全都是“比较 + 交换”这两个动作。理解这一点之后，你再看任何排序代码，就不会觉得它是一个一个孤立的“模板”，而是在看同一套底层逻辑的不同调度方式。

还有一个特别容易被忽略的问题：比较排序的时间下界是 O(n log n)。这句话的意思是，只靠两两比较来排序，最坏情况下任何算法都不可能突破 n log n 的复杂度，快排、归并、堆排都是贴着这个下界跑。这个结论可能对初阶读者来说有点远，但建议你先记住，等你学完归并排序再回来看这条下界，会有一种突然通透的感觉——为什么 O(n²) 的排序和 O(n log n) 的排序之间隔着一道天堑，为什么市面上的通用排序都在 n log n 这个级别上做文章，都能从这个下界得到解释。

1.2 大 O 复杂度：不要背定义，要建立数量级感觉

大 O 复杂度是分析排序算法的核心工具。教材上一般会写一堆严格定义：存在常数 c 和 n₀，当 n > n₀ 时 f(n) ≤ c·g(n)。这句话数学上严谨，但初学的时候很难形成直觉。我换一种说法：大 O 描述的是一台“虚构的计算机”上，算法运行时间随数据规模增长的趋势，它把常数系数、低阶项全部抹掉，只留下增长最快的那个主体。

为什么可以把常数抹掉？因为当 n 足够大的时候，常数的影响远小于数量级的差距。比如 n = 100 万时，n² = 10¹²，除非你的常数系数小到 10⁻⁶，否则根本和 n log n 不在一个量级上。一个算法是 O(n²) 还是 O(n log n)，比它是“用 C 写的还是用 Python 写的”、比它是“循环里做 3 次操作还是做 10 次操作”重要得多。这就是为什么面试官问你复杂度，本质是想看你能不能预判程序在大数据规模下的表现。

对排序算法来说，你需要建立三档直觉：

• O(n²) 这一档：数据规模到一万就已经开始吃力，到十万基本扛不住；
• O(n log n) 这一档：百万级数据量依然轻松，千万级才需要考虑优化；
• O(n) 这一档：只有桶排序、计数排序这类非比较排序能达到，但有数据范围限制。

后面讲到归并排序的 merge 过程时，你会看到 O(n log n) 到底是怎么算出来的。现在先在脑子里种下这棵数量级的树，后面所有分析都长在这棵树上。

1.3 稳定性：看起来不起眼，关键时刻很致命

稳定性的定义是：如果数组里有两个相等的元素 a 和 b，a 原本在 b 前面，排序之后 a 依然在 b 前面，这个排序算法就是稳定的；如果相等元素的相对顺序可能发生变化，就是不稳定的。

初学的人经常问一个问题：既然两个值相等，谁在前谁在后有什么区别？答案在“多关键字排序”里。假设你有一份学生成绩表，先按总分降序排序，总分相同的按学号升序排序。最直观的做法是先按学号升序排一遍，再按总分降序排一遍。第二次排序面对总分相等的学生，如果算法是稳定的，学号的顺序会原封不动保留下来，一道排序命令就完成了二级排序。如果算法不稳定，你需要分成多次排序或者用复合比较函数来处理。

从这个例子能看出来，稳定性不是数学上的洁癖，而是工程上的实用需求。具体到每个算法，冒泡排序和插入排序天然稳定，因为它们只交换相邻元素，相等的元素永远不会互相跨越；选择排序不稳定，因为它会把远处的元素直接交换到前面，跨越过程中可能改变相等元素的顺序。归并排序写得好可以稳定，写得不好也会悄悄把它弄丢。这些细节我会在对应章节里逐个点出来。

2. 冒泡排序：从最朴素的思路到两次优化

2.1 算法推导：把最大的数“冒”到末尾

冒泡排序是最容易从直觉里长出来的排序算法。想象你有一排高低不一的柱子，你想让它们从左到右从低到高排列。一个朴素的想法是：从左往右走一遍，看见相邻两根柱子左高右低，就交换它们。走完一遍之后会发生什么？最大的那根柱子一定会被一路换到最右边，因为只要它和右边的邻居比较，它总是比对方大，就会继续交换，一路上“冒泡”到最后。

这个过程重复 n 轮，每一轮都能确定一个当前未排序部分的最大值，放到正确的位置上。数据结构教材里一般用双重循环来实现：外层循环控制轮数，内层循环控制每一轮的相邻比较和交换。直接看 C 代码：

c复制void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {          // 需要 n-1 轮
        for (int j = 0; j < n - 1 - i; j++) {  // 每轮比较的范围逐渐缩小
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

内层循环里 j < n - 1 - i 这个边界很多人第一次写会写错。为什么要减 i？因为每一轮结束之后，数组尾部已经排好了 i 个元素，这些元素不需要再参与比较。比如第一轮结束，数组最大值已经在最后一位，第二轮就没必要再去碰最后一位了。减 i 是一个非常直观的剪枝：不去做已经确定没有意义的事。

轮数为什么是 n-1 而不是 n？因为只要 n-1 个元素到了正确位置，剩下的那一个元素自然也在正确位置，不需要再排一轮。

2.2 第一次优化：提前终止，处理几乎有序的数据

基础版冒泡有个很大的浪费：如果数组在中途就已经有序了，它仍然会把剩下的轮数全部跑完。举个例子，输入 [1, 2, 3, 4, 5, 6, 7, 8]，第一轮从头到尾比较一遍，发现一次交换都没发生，显然数组已经有序，可是基础版代码还是会跑 n-1 轮。对此一个非常经典的优化是加一个标志位，记录当前轮是否发生了交换，如果某一轮完全没有交换，就直接结束整个排序：

c复制void bubble_sort_optimized(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 tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // 这一轮没有交换，说明已经有序
    }
}

这个优化让冒泡排序的最好情况复杂度从 O(n²) 降到了 O(n)。最好情况对应输入数组已经有序的场景，只需要一轮扫描、比较 n-1 次、零交换，然后立刻退出。虽然平均和最坏仍然是 O(n²)，但这个优化让冒泡排序在“近乎有序”的数据上有了一点实际价值。

我见过不少面试场景，候选人写冒泡排序时能写出这个 swapped 标志位，面试官大概率会点个头，因为它说明你对“输入数据特征会影响算法实际时间”这件事有感知。这种感知在后面的插入排序里会再次出现，而且重要程度更高。

2.3 第二次优化：双向冒泡，解决“小乌龟”问题

基础冒泡还有一个隐蔽的低效点。如果数组是 [2, 3, 4, 5, 6, 7, 1]，也就是最小的元素 1 在数组最后一位，第一轮冒泡会把 7 冒到末尾，数组变成 [2, 3, 4, 5, 6, 1, 7]，1 只向前移动了一位。想让它回到数组开头，需要经历整整 n-1 轮，每一轮它都只向前挪一格。这类小的元素被形象地称为“小乌龟”，大的元素则是“兔子”——兔子从前往后跑得很快，小乌龟从后往前爬得很慢。

解决办法是双向冒泡，也就是常说的鸡尾酒排序：奇数轮从前往后把大数冒到尾部，偶数轮从后往前把小数冒到头部。这样小乌龟最多只需要一轮就能回到正确位置附近，整体轮数会明显减少。当然，双向冒泡的复杂度仍然是 O(n²)，它只是把常数因子优化了，并没有改变数量级。对初阶读者来说，理解这个优化思路比会默写双向冒泡代码更重要，因为“发现某种数据特征导致算法局部效率低下，然后针对性地调整遍历方向”这种思维，在后续学快速排序的 pivot 选取、学堆排序的堆化方向时都会反复出现。

冒泡排序本身的工程价值在工业界几乎为零，稳定排序有插入排序这个更好的选择，性能排序有快排和归并。但作为第一个排序算法，它是完美的教学素材：循环边界、交换、优化思路、稳定性，这些基础概念都能通过它建立起来。

3. 选择排序与插入排序：两种相反的局部策略

3.1 选择排序：反复选出最小值，放到正确的位置

选择排序的思路是“打擂台”：第一轮从整个数组里找出最小值，和第 0 个元素交换；第二轮从剩下的元素里找出最小值，和第 1 个元素交换；依此类推。每一轮都确定一个元素的最终位置，总共需要 n-1 轮。

有读者可能会问：这和冒泡排序看起来差不多啊，都是每轮把一个元素归位。区别在于交换的次数。冒泡排序每一轮可能发生很多次交换（最坏情况下每轮内层循环几乎每次比较都伴随交换），而选择排序每一轮只做一次交换，剩下的操作全是比较。C 代码：

c复制void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int tmp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = tmp;
        }
    }
}

选择排序的交换次数固定是 n-1，这意味着它的写操作很少，在“交换两个元素代价很高”的场景（比如元素是很大的结构体，或者存储在磁盘上）里有特殊价值。但这个优点在日常内存数组排序中基本体现不出来，因为内存交换一个 int 的代价可以忽略不计。

选择排序最大的问题是它的比较次数固定为 n(n-1)/2，不管数据是否有序，它都老老实实把每一对潜在的最小值比较完。这意味着选择排序没有最好情况、最坏情况之分，任何输入都是同一个复杂度 O(n²)。这一点和冒泡、插入完全不同，后两者在有序数据上都能提前“刹车”。

3.2 选择排序不稳定的根因：跨距离交换

前面提到选择排序是不稳定的，这值得展开说清楚，因为它很反直觉。考虑数组 [5a, 5b, 1]，其中 5a 和 5b 都等于 5，我们用下标区分它们在原数组中的先后位置。选择排序第一轮找到最小值 1，下标是 2，然后拿它和下标 0 的 5a 交换，数组变成 [1, 5b, 5a]。原来 5a 在 5b 前面，排序后 5a 跑到了 5b 后面，两个相等的 5 相对顺序被改变了。

问题出在“跨距离交换”：选择排序把远处的最小值直接交换到前面，交换过程中很可能跨越了多个和它值相等的元素，导致这些相等元素的相对位置被打乱。对比之下，冒泡排序和插入排序都只交换相邻元素，相等的元素要越过另一个相等元素，必须一步一步地交换过去，这个过程里它们的相对顺序不会颠倒。这个规律总结成一句话：相邻交换的排序天然稳定，跨距离交换的排序容易不稳定。

3.3 插入排序：像整理扑克牌一样往前插

插入排序的思路很多人第一次玩扑克牌就见过：手里已经拿了几张牌，是按顺序排好的，新摸一张牌，从右往左跟已有的牌比较，找到合适的位置插进去，后面的牌依次往右挪一格。这个“摸牌、比较、后移、插入”的动作翻译成代码就是插入排序。

C 语言实现：

c复制void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

外层循环 i 从 1 开始，因为第 0 个元素自己天然构成一个有序区间。每次把 arr[i] 记到 key 里，然后往前看：只要前面的元素比 key 大，就把它们往后挪一位，给 key 腾位置。挪完之后，在 j + 1 这个位置把 key 放进去。

这里有一个初学容易写错的点：为什么必须先用 key 把 arr[i] 保存下来？因为后移过程中，arr[i] 的位置会被前面的元素覆盖掉。如果不用 key 保存原始值，等找到插入位置时，这个值已经被覆盖得找不回来了。

插入排序有两个显著优点：

• 对“近乎有序”的数据，它非常快。假设数组只有少数几个元素位置不对，插入排序每轮可能只往前比一两次就找到了位置，总比较次数接近 n，整体接近线性时间。
• 它稳定，因为元素是逐位后移的，相等的 key 不会越过相等的前一个元素。
• 它不需要额外空间，原地排序。

有一个经典的说法：插入排序的 O(n²) 是“便宜的 O(n²)”，因为它常数小、对有序数据友好，所以很多工程实现会把插入排序作为“小数组兜底”。比如 Java 的 Arrays.sort 对基本类型的实现里，对长度小于某个阈值的数组会切到插入排序；Python 的 Timsort 里小分区的排序也用插入排序。

3.4 插入排序为啥能衍生出希尔排序：相邻交换的局限

如果你把插入排序理解透了，你会发现它的一个天然局限：一个很小的元素如果待在数组很靠后的位置，它每一轮只能往前挪一格，和冒泡排序里“小乌龟”的问题一模一样。比如 [6, 7, 8, 1]，1 需要在第 4 轮插入时才能回到最前面，前 3 轮都在做徒劳的比较。

希尔排序就是冲着这个痛点去的：先让元素大步长地跳着插，把小元素快速甩到前面，再逐步缩小步长，直到步长为 1 做一次标准的插入排序。理解插入排序是理解希尔排序的跳板，所以哪怕你现在不学希尔排序，也要记住“相邻交换导致元素移动慢”这个观察，它会在很多排序优化里反复出现。

4. 归并排序：第一次跳出 O(n²) 的思维框架

4.1 分治思想：把大问题切成小问题再合起来

前面三种排序都是 O(n²) 级别，它们共同的特点是“通过局部比较不断修正顺序”。当 n 变大，这种逐对修正的方式成本急剧上升。归并排序带来的新思路是分治：把数组从中间一分为二，左半边排序、右半边排序，然后把两个有序数组合并成一个有序数组。

看到这里很多人会问：把数组切开再合并，为什么就能比 O(n²) 快？核心在于“把两个已经有序的数组合并”这件事的代价是 O(n)——两个有序数组的合并只需要线性扫描，不需要两两穷举。而把数组对半切开，切 log₂n 次就切到了单个元素，单个元素天然有序。整个过程就像一棵递归树：每一层上所有子问题的总工作量是 O(n)（每层都要合并总长度为 n 的元素），树的高度是 log₂n，所以总复杂度就是 O(n log n)。这个推导思路比背公式重要得多，面试时讲解归并排序复杂度，把这个“每层 O(n)，共 log n 层”的逻辑讲清楚，比直接甩出一个公式有说服力得多。

C 代码演示 merge 过程：

c复制void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

merge 函数做的事：把 arr[left..mid] 和 arr[mid+1..right] 两个有序部分合并。先把两半分别复制到临时数组 L 和 R，然后用 i、j 两个指针分别扫描，每次把两者中较小的一个放回原数组，直到某一半耗尽，再把剩下的元素整体拷回去。

注意我在比较里写的是 L[i] <= R[j] 而不是 <。这个 <= 就是归并排序稳定性的关键。当 L 和 R 里的元素相等时，选择 L 的元素先放入，也就是左边部分的元素先放，这样相等元素的相对顺序和原数组保持一致。很多教材的代码会写成 <，逻辑上合并结果还是有序的，但稳定性就丢了。面试时如果面试官追问“归并排序稳定吗？你的代码保持住稳定性了吗？”答得上看不起的就是这个细节。

4.2 递归版本的完整结构：分解、合并、边界条件

有了 merge 函数，归并排序的递归主体就非常简单，它只做三件事：算中点、递归左半、递归右半、合并：

c复制void merge_sort(int arr[], int left, int right) {
    if (left >= right) return;        // 只剩一个元素或空区间，天然有序
    int mid = left + (right - left) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

递归的终止条件是 left >= right，意思是区间里最多只有一个元素，不需要再排序。mid = left + (right - left) / 2 这种写法比 (left + right) / 2 更好，因为后者在 left 和 right 都很大时可能溢出。虽然初阶学习时很少会用到那么大的数组，但养成写防溢出版本的习惯没坏处。

递归的调用过程可以用一棵树想象：最上层处理整个数组，它先处理左半，再处理右半，最后合并。处理左半时又会先处理左左半……一路递归下去，直到最底层每个“区间”只有一个元素。然后从最底层开始一层层向上合并。合并的过程画出来很像一棵倒着的树，每层的总工作量都是 n，层数是 log₂n，所以总工作量是 n log n。这个递归树视角非常重要，因为它同样可以用来分析快速排序（后续文章会展开）。

4.3 归并排序的工程细节：额外空间、对小数组切换策略

归并排序有一个不能回避的成本：它需要 O(n) 的额外空间。如果你在递归函数里每次 merge 都临时创建 L 和 R 数组，空间开销会随着递归调用反复分配释放，虽然总空间复杂度 O(n) 不会变，但常数会很难看。实际工程实现里，通常会预先分配一个和原数组等长的临时数组，传给递归的每一层复用，这样避免了频繁 malloc 的开销。这一点数据结构教材上不会太强调，但真正写高性能代码时很重要。

另一个优化是“小数组切换策略”：递归到区间足够小（比如长度小于 16 或 32）时，不再继续递归切分，直接改用插入排序。原因是递归本身的函数调用和数据搬移有固定开销，当子问题足够小的时候，插入排序的 O(k²) 代价远小于递归合并的固定开销，整体反而更快。Java 的 Arrays.sort 里对对象数组的归并实现就有类似的分区阈值设计。Python 的 Timsort 更夸张，它本身就是“归并排序 + 插入排序”的混血，靠着检测数据中的有序片段来加速。学归并排序时不了解这些工程化操作没问题，但如果学完有印象，面试的拓展题就能说出东西来。

归并排序还有一个隐藏的优点：对链表排序非常友好。数组归并需要额外空间是因为合并时要同时访问两个有序区间的元素，数组的原地合并很复杂；但对链表来说，合并两个有序链表只需要改指针，不需要搬动元素、不需要额外空间。LeetCode 上那道“排序链表”题目，标准解法就是归并排序。这点不用初阶阶段深入，但值得知道。

5. 实测对比：在相同数据规模下看不同排序的真实表现

5.1 实验设计：为什么需要多种输入分布

前四节的理论分析已经足够扎实，但“复杂度是渐进的，常数被抹掉了”这句话在工程上会带来怎样的体验差异，还是要动手跑一跑数据才知道。我建议你亲手做这样一组对照实验：分别用冒泡、选择、插入三种 O(n²) 排序和归并排序，对同一批数据进行排序，对比耗时。

实验最关键的一点是数据分布。只测一组随机数据是不够的，因为不同排序对输入的有序程度敏感度差异很大。我建议至少测三组：

• 完全随机的数组，数据范围不需要很大，两万左右就够让 O(n²) 有明显耗时差异了；
• 已经升序的数组；
• 接近升序的数组（比如升序基础上随机挑少量元素交换位置）。

如果机器性能很好两万看不出差别，就把随机数组加到五万或十万，但注意 O(n²) 的耗时随 n 平方增长，五万已经是几秒级别，根据你的机器调节一个舒适的规模。

我用 Python 写实验脚本比 C 更方便控制输入和计时，但请注意：Python 的循环解释执行会让常数被放大，四种排序在 Python 下的绝对耗时和 C 环境下会差很多。不过我们关心的是相对趋势和数量级差距，这个趋势在 Python 里体现得更夸张、更直观。如果你想把现象拿到 C 里再验证一遍，结论是一致的。

5.2 实验结果：随机数据的数量级碾压

下面是我在本机用 Python 跑出来的参考数据，数据规模两万、随机整数，单位是秒。不同机器具体数值会有差异，但数量级关系是稳定的：

这张表能看出几件很有意思的事。第一，未优化的冒泡排序在有序数组上和随机数组上耗时几乎一样，这是它最大的浪费——明明已经有序了，它还坚持跑完全部轮次。加了一个 swapped 标志位之后，有序数据的耗时从秒级暴跌到毫秒级，这也是“算法优化不是玄学”最直观的证据。

第二，选择排序在有序数据上并没有变快。这和理论完全吻合：它每轮都要完整扫描一遍找最小值，不管数据长什么样，比较次数固定是 n(n-1)/2。在此你能直观理解为什么说选择排序“没有最好情况”——它对输入不敏感。

第三，插入排序的“近乎有序”优势非常夸张。接近有序的数据耗时只有随机数据的几百分之一，这个特性正是它被大量工业级排序当作“兜底方案”的最大原因。如果哪一天你发现某个线上服务排序特别慢，而数据又非常接近有序，不妨想想是不是该换插入排序的思路。

第四，归并排序在随机数据上比三种 O(n²) 快了两三个数量级。注意这只是 n = 20000 的规模，当 n 翻倍到 40000，O(n²) 的耗时基本要翻四倍，而归并排序只翻两倍多一点，数据规模越大，差距越恐怖。这就是 n log n 和 n² 的真实差距。

5.3 从跑分回到思维：为什么分析复杂度比背代码重要

跑分实验的目的不是让你记住“插入排序 0.8 秒，选择排序 1.3 秒”这些数值，数据换个机器就全变了。真正值得带走的是：复杂度分析能够提前预测算法在大规模数据上的结局。如果你没有学复杂度，你只会一句“插入排序好像快一点”，但不知道为什么快、快多少、换一种输入会不会翻车。学了复杂度分析，你能在编写代码之前就判断一个排序方案能不能扛住十万、百万级数据，这种预判能力是数据结构这门课真正想教给你的东西。

回到开头的那个问题：为什么排序是数据结构里最值得反复琢磨的主题？因为它像一个微型宇宙，把所有算法核心要素都装进来了——复杂度分析、稳定性权衡、原址与额外空间、分治思维、输入特征对性能的影响。吃透排序，你后面学二分查找、二叉树、堆、哈希表时的很多思维工具，都已经在排序里练过一遍了。

这篇是排序算法的上篇，我把复杂度基础、冒泡排序、选择排序、插入排序、归并排序的完整推导和工程细节都拆解了一遍。你如果能动手把上面的代码敲一遍、跑一遍实验数据，收获会比只看文章大得多。下一篇会对快速排序做同样的深度拆解，同时把堆排序、希尔排序以及各类排序的应用场景对比讲完，到时候三种 O(n²) 排序、三种 O(n log n) 排序就会在你脑子里构成一张完整的图。如果你在跑实验或者推导复杂度的过程里有卡住的地方，欢迎在评论区把具体数据贴出来，我来帮你分析是不是哪个环节出了问题。