企业官网建设流程全解析

排序算法这块，很多朋友一开始是冲着背代码去的，但背着背着就乱了——七种排序，各自的代码长得差不多，又各有各的坑，考场上稍一紧张就把快排的 partition 写成死循环了。这篇东西就是把这七大排序（直接插入、希尔、冒泡、快速、简单选择、堆、归并）掰开揉碎讲清楚。每个算法我都按“思想图解 → 步骤拆解 → 代码实现 → 易错提醒”的顺序来写，全程用 C 语言风格伪代码，配套考点提示，适合正在学数据结构、准备 408 考研或者期末突击的朋友。你看完会发现，排序这东西根本不用背，理解了它的"脾气"之后，代码是顺着思路自己流出来的。

1. 七大排序的整体架构与学习主线

很多初学者拿到排序章节第一反应是"七个算法放一起，怎么记？"，我的建议是先别急着码代码，先在脑子里搭一个分类框架。

1.1 为什么偏偏是这七个算法

数据结构教材里标杆性排序远不止七种，还有基数排序、计数排序这类非比较排序，但核心的比较排序里，教材反复拎出来讲的就是这七种。原因很简单：它们覆盖了三种最基本、面试和考试中最高频的思想维度——插入、交换、选择，外加一个分治策略的归并。你把这三个维度的框架立住了，后面学什么排序都不会乱。

在实际应试里，这七个算法的出场率确实是最高的。408 统考、各大厂校招笔试、期末考试大题，翻来覆去考的就是复杂度推导、稳定性判断、手写核心代码，以及"哪种场景选哪种排序"。七种算法里，快排是推荐系统、数据库底层最常用的排序思路，堆排是大数据 TopK 的标配，归并是外部排序和链表排序的基石，而插入排序则是所有排序里"开窍"的第一步。把这七个吃透，就等于把整个比较排序的体系盘活了。

1.2 学习排序的"三要素"框架

我辅导过不少学生，发现大家排序学得混乱，根本原因是没建立分析维度。看任何一个排序算法，你只需要盯住三件事：

• 时间复杂度：最好、最坏、平均分别是多少，各自对应什么输入分布。
• 空间复杂度：是否原地排序，是否需要额外辅助数组或递归栈。
• 稳定性：相同关键字的元素排序后相对顺序是否保持不变，这在多关键字排序场景下非常重要。

这三要素不是孤立的知识点。比如快排平均 O(n log n) 但最坏退化 O(n²)，这个退化恰恰是因为 partition 极度不平衡导致的；堆排时间复杂度稳定但在实际系统中反而不如快排常用，是因为它访问内存不连续，对缓存不友好。一旦你开始用三要素去横向对比算法优劣，很多纠结自然就解开了。

我用下面这张总表先给你一个全局观，后续每个算法小节都会回到这张表来展开解释：

1.3 从"时间"和"空间"两条维度横向对比

除了三要素，我建议你再从"宏观行为"上感知这几个算法的差异。最直观的一个维度是"数据移动方式"。

插入类和冒泡类排序，每次比较后只交换相邻元素，每趟排序最多移动一个位置，这类算法在数据基本有序时表现极好，最好情况能到 O(n)。而选择类和希尔、快排、堆排这类"跳跃式"排序，每次比较后可能跨越很远距离移动数据，整体上加速了排序过程，但也失去了稳定性，因为跨距移动容易把相同值的相对顺序打乱。

另一个维度是"是否依赖初始序列"。依赖初始序列的算法有插入排序、冒泡排序、快速排序，它们在数据接近有序时效率显著提升；不依赖初始序列的算法有简单选择、堆排、归并，它们的效率完全由 n 决定。为什么？因为前者每趟比较能"提前终止"（比如冒泡已有序就停止交换），而后者的比较次数是数学上固定的。理解了这一层，你就知道为什么有时候"数据已经排好了，快排反而变慢了"——因为退化成了最坏情况。

2. 插入类排序：直接插入与希尔排序

插入类排序的核心思想一句话：把待排序的元素逐个插入到已经有序的序列中，像打扑克时整理手牌一样。这个思路朴素，但衍生出的希尔排序却是第一个突破 O(n²) 壁垒的排序算法，值得认真对待。

2.1 直接插入排序的图解流程

直接插入排序的整个流程非常直观。假设当前数组是[5, 2, 4, 6, 1, 3]，我们从第二个元素开始往前看：

• 第一趟：取2，与前面的5比较，5 往后挪，把 2 放到位置 0，序列变成[2, 5, 4, 6, 1, 3]。
• 第二趟：取4，依次与5、2比较，4 比 5 小所以 5 后挪，4 比 2 大所以停在位置 1，序列变成[2, 4, 5, 6, 1, 3]。
• 第三趟：取6，和前面的 5 比，比 5 大，直接不动。
• 第四趟：取1，一路往前比，把前面所有比自己大的元素都往后挪一位，最后插入到位置 0。
• 第五趟：取3，同理插入到位置 1。

如此迭代 n-1 趟，所有元素就有序了。这个"往前挪"的过程本质上是tmp = arr[i]; j = i-1; while(j >= 0 && arr[j] > tmp) { arr[j+1] = arr[j]; j--; } arr[j+1] = tmp;的操作。注意arr[j] > tmp这个条件用的是严格大于，也就是说相等的元素不会发生交换，相等值的相对顺序被完整保留——这就是它稳定的根源。

你画图的时候会发现，每一趟排序后，序列前半部分始终有序。这跟选择排序不一样，选择排序是"每趟找到最小值放到前面，但前面未必有序"，插入排序则是每趟都维护前面整体有序，后面待处理的元素不断插入到这个有序区中。

2.2 直接插入排序的代码实现与考场细节

C 语言风格实现直接插入排序非常短：

void insertSort(int arr[], int n) { int i, j, tmp; // 从第二个元素开始逐个插入 for (i = 1; i < n; i++) { if (arr[i] < arr[i - 1]) { // 这句判断是优化关键 tmp = arr[i]; j = i - 1; while (j >= 0 && arr[j] > tmp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = tmp; } } }

考场上有两个细节容易丢分：第一，while (j >= 0 && arr[j] > tmp)里的j >= 0一定要写在前面，否则当 j 变成 -1 时再去访问arr[j]就越界了。第二，if (arr[i] < arr[i-1])这个判断不能省，它是优化代码的关键——如果当前元素已经比有序序列最后一个元素大，说明它已经在正确位置，直接跳过这一轮内层循环。这在数据基本有序时能省掉大量无意义的比较。

复杂度方面，最好情况是数组本身有序，每趟只需比较一次就结束，总比较次数 n-1，时间复杂度 O(n)；最坏情况是逆序，比较和移动次数都是 n(n-1)/2，O(n²)。空间复杂度 O(1)。稳定性方面，因为只有arr[j] > tmp才移动，相等的元素不移动，所以是稳定的。

提醒：408 和期末考经常考一个问题："数组基本有序时，哪种排序最快？"答案就是直接插入排序，因为它的最好情况是 O(n)，而快排和选择排序在这种场景下依然要老老实实跑完 O(n²) 或 O(n log n)。

2.3 希尔排序的增量思想图解

希尔排序是插入排序的"跳跃版本"，它引入了增量（gap）概念：先让相距 gap 的元素组成一个逻辑子序列，分别做插入排序；然后缩小 gap，再排序，直到 gap 为 1 做最后的全体插入排序。

为什么这样做会快？因为直接插入排序最致命的问题是移动太慢，每次只能挪一步，如果最小的元素在最后面，它要一步步挪到最前面，消耗 O(n) 次移动。希尔排序先按大步长把远处的小元素"快速传送"到前面，数据整体接近有序后，最后一步 gap=1 的插入排序就非常快。

图解一个例子，数组[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]，第一趟取 gap=5：

• 下标 0 和 5 一组：8 和 3，插入排序后为3, 9, 1, 7, 2, 8, 5, 4, 6, 0。
• 下标 1 和 6 一组：9 和 5，排序后为3, 5, 1, 7, 2, 8, 9, 4, 6, 0。
• 下标 2 和 7 一组：1 和 4，排序后不变。
• 下标 3 和 8 一组：7 和 6，排序后为3, 5, 1, 6, 2, 8, 9, 4, 7, 0。
• 下标 4 和 9 一组：2 和 0，排序后为3, 5, 1, 6, 0, 8, 9, 4, 7, 2。

可以看到，最小的元素 0 从位置 9 直接跳到了位置 4，再经过下一轮 gap=2 的排序，就能很快到达前面。这就是"跳跃式插入排序"的优势所在。

2.4 希尔排序的代码与增量序列选择

希尔排序代码基于直接插入排序改了一个外层循环：

void shellSort(int arr[], int n) { int gap, i, j, tmp; // 增量序列：n/2, n/4, ..., 1 for (gap = n / 2; gap >= 1; gap /= 2) { for (i = gap; i < n; i++) { // 对每个子序列做插入排序 tmp = arr[i]; j = i - gap; while (j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } } }

这段代码里最有意思的地方是for (i = gap; i < n; i++)这一行。表面上看是遍历整个数组，实际上它把间隔 gap 的子序列交叉在一起处理，每个元素都跟它前面 gap 位的元素比较。这样写比"先处理第 0 组、再处理第 1 组"更简洁，逻辑上也等价。

增量序列对希尔排序的效率影响很大。教材常见的 n/2 折半序列实现简单，但最坏情况依然是 O(n²)。比较经典的优化序列有 Hibbard 增量序列（2^k - 1），最坏情况能压到 O(n^(3/2))，Sedgewick 序列能达到 O(n^(4/3))。考试如果问"希尔排序的时间复杂度"，标准答法是"取决于增量序列，平均大约 O(n^1.3)，最坏 O(n²)"，不必死记具体推导。

稳定性方面，希尔排序因为分组后跨距交换，相同元素可能被分到不同组并发生交换，所以是不稳定的。我在这个点上吃过亏，有次笔试问"稳定的 O(n²) 算法有哪些"，我写了希尔排序，当场白给一分。

3. 交换类排序：冒泡排序与快速排序

交换类排序的核心动作是"比较 → 交换"，区别在于冒泡是相邻交换，快排是跳跃交换。两者的性能天差地别，但思想上是一脉相承的。

3.1 冒泡排序的图解与优化点

冒泡排序每趟从前往后扫描，如果相邻两个元素逆序就交换，这样每趟都会把当前未排序部分的最大值"冒泡"到末尾。以[5, 2, 4, 6, 1, 3]为例，第一趟下来6会浮到最右边，第二趟5浮到倒数第二，依次类推。

代码很简单：

void bubbleSort(int arr[], int n) { int i, j, tmp; // 用一个 flag 标记本趟是否发生交换 for (i = 0; i < n - 1; i++) { bool swapped = false; for (j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; swapped = true; } } // 如果本趟没有交换，说明已经有序，提前结束 if (!swapped) break; } }

这个swapped标志是冒泡排序的灵魂优化。如果某趟扫描发现一次交换都没发生，说明序列已经有序，直接终止外层循环。加了这行代码后，冒泡排序在基本有序场景下最快可以到 O(n)，不加的话即使有序也要跑满 n-1 趟。

冒泡排序是稳定的：只有arr[j] > arr[j+1]才交换，相等元素不会跨越彼此，相对位置保持不变。空间 O(1)。

实战经验：很多人觉得冒泡排序"太笨了"，实际编码里确实不会用它处理大量数据，但它的价值在于"探测有序性"。比如数据流场景里你需要判断一个几乎有序的序列是否真的有序，冒泡天然给你答案，因为一趟扫描无交换就说明有序。

3.2 快速排序的核心 partition 图解

快速排序的思想是分治：任选一个基准元素 pivot，把数组分成两部分，左边所有元素 ≤ pivot，右边所有元素 ≥ pivot，然后对左右子数组递归继续。这里最关键的是 partition（划分）怎么实现。

教科书里最常见的 partition 是"挖坑法"或"左右指针法"。我演示左小右大的左右指针法：

• 选定最左边元素5为 pivot，left 指针指向下标 0，right 指针指向下标 n-1。
• 先从右往左找第一个比 pivot 小的元素，停下；再从左往右找第一个比 pivot 大的元素，停下；交换两者。
• 重复上述过程，直到 left 和 right 相遇。相遇点就是 pivot 的最终位置，把 pivot 与相遇点交换。

以[5, 2, 4, 6, 1, 3]为例，pivot=5，right 先往左走找到3（下标 5）比 5 小，left 往右走找到6（下标 3）比 5 大，交换 6 和 3 得到[5, 2, 4, 3, 1, 6]。然后 right 继续左移找到1（下标 4），left 右移与 right 相遇在下标 4，此时交换 pivot 5 和 1，得到[1, 2, 4, 3, 5, 6]。以 5 为界，左边全小于它，右边全大于它，第一趟 partition 完成。

int partition(int arr[], int low, int high) { int pivot = arr[low]; // 选第一个元素为基准 while (low < high) { // 从右向左找比 pivot 小的元素 while (low < high && arr[high] >= pivot) high--; arr[low] = arr[high]; // 挖坑填数 // 从左向右找比 pivot 大的元素 while (low < high && arr[low] <= pivot) low++; arr[high] = arr[low]; } arr[low] = pivot; // 基准归位 return low; } void quickSort(int arr[], int low, int high) { if (low < high) { int pos = partition(arr, low, high); quickSort(arr, low, pos - 1); // 递归左半区 quickSort(arr, pos + 1, high); // 递归右半区 } }

3.3 快排的退化风险与工程优化技巧

快排平均时间复杂度 O(n log n)，空间复杂度 O(log n)（递归栈深度），但有一个致命弱点：当每次 partition 选中的 pivot 恰好是当前区间最小值或最大值时，划分极端不平衡，递归树变成一条链，时间复杂度退化为 O(n²)。

最典型的退化场景就是"数组已经有序 + 固定选第一个元素作 pivot"。每次 pivot 都是最小值，右侧递归树深度 n，总比较次数 n(n-1)/2。很多新手第一次用快排排序一个有序数组，直接被性能吓到，就是这个原因。

工程上的优化手段主要有四种：

• 随机选取 pivot：在low到high之间随机选一个下标交换到 low 位，使最坏情况概率趋近于零。
• 三数取中法：取low、mid、high三个位置的中位数作为 pivot，能有效避免有序数组的退化。
• 小区间使用插入排序：当递归区间长度小于某个阈值（比如 15）时，不再递归，直接对小区间做插入排序。因为插入排序在数据量小时开销低于快排的递归开销。
• 尾递归优化：对递归栈深度进行控制，减少栈溢出风险。

考试和面试里，你至少要知道"有序数组 + 固定 pivot 导致快排退化 O(n²)"这个结论，然后能说出随机化和三数取中两种优化方案就够了。至于具体的随机数生成、三数取中代码，属于加分项。

经验分享：我在实际写快排的时候习惯把 pivot 选中间位置的元素 ——int pivot = arr[(low+high)/2]，这样对于很多特殊输入都能自动避开退化。虽然理论上依然存在最坏情况，但工程上已经足够稳。考试手写代码时如果题目没有特别要求，写自然的递归版本就行，但一定要在 partition 前加一行随机交换，显得你有工程意识。

4. 选择类排序：简单选择与堆排序

选择类排序的核心是"每趟选出一个极值放到最终位置"。简单选择每趟线性扫描选最小值，堆排序则用堆这种数据结构加速"选最小值"的过程。

4.1 简单选择排序的图解与代码

简单选择排序的思路最直观：第一趟扫描全部元素，找到最小值放到下标 0；第二趟扫描下标 1 到 n-1，找到最小值放到下标 1；重复 n-1 趟。

void selectSort(int arr[], int n) { int i, j, minIdx, tmp; for (i = 0; i < n - 1; i++) { minIdx = i; for (j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } if (minIdx != i) { tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } } }

代码里有个细节：if (minIdx != i)保证了只有在找到更小元素时才交换。这不仅是为了减少无意义的赋值，更重要的是如果两个元素相等，选择排序不会做出多余的交换，这在某些评判标准下能保住稳定性。但严格来说，选择排序并不能保证稳定性——看一个例子[5, 5, 1]，第一趟最小值 1 与第一个 5 交换，两个 5 的相对顺序虽然没有变化，但如果后面有和第一个 5 相等的另一个 5，交换后相对位置就可能改变。所以标准结论是简单选择排序不稳定。

无论数组是否有序，简单选择排序的比较次数都是 n(n-1)/2，时间复杂度恒定 O(n²)，这也是它"死板"的一面。空间 O(1)。实际开发中基本不用它，但考试必考，因为它是"每趟选一个极值"思想最简单的载体。

4.2 堆排序的建堆过程图解

堆排序利用的是完全二叉树结构的数组表示。大根堆满足父节点值 ≥ 子节点值，堆顶就是最大值，每趟把堆顶与末尾元素交换，然后对堆顶做"下沉"调整，就能依次把最大值放到末尾。

建堆的过程是"从最后一个非叶子节点开始，从下到上、从右到左做下沉调整"。对数组[4, 10, 3, 5, 1, 8, 7]来说，n=7，最后一个非叶子节点的下标是 n/2 - 1 = 2，也就是值 3 的节点。以它为例：

• 节点 3 的左右孩子下标分别是 5（值 8）和 6（值 7），8 最大且大于 3，交换 3 和 8。
• 接着处理下标 1（值 10），它的左右孩子是下标 3（值 5）和下标 4（值 1），10 已经大于两个孩子，无需调整。
• 再处理下标 0（值 4），它的左右孩子是下标 1（值 10）和下标 2（值 8），10 最大且大于 4，交换 4 和 10；交换后下标 1 的子树可能被破坏，继续对下标 1 做下沉，发现它的孩子是 5 和 1，4 小于 5，继续交换，直到越界。

经过这个过程，数组变成了[10, 5, 8, 4, 1, 3, 7]，一个大根堆就建成了。

void siftDown(int arr[], int k, int n) { int tmp = arr[k]; // 暂存待下探的节点 while (k * 2 + 1 < n) { // 存在左孩子 int child = k * 2 + 1; // 如果右孩子存在且更大，选取右孩子 if (child + 1 < n && arr[child + 1] > arr[child]) { child++; } if (tmp >= arr[child]) break; // 父节点已不小于较大孩子 arr[k] = arr[child]; // 孩子上移 k = child; // 继续向下比较 } arr[k] = tmp; } void heapSort(int arr[], int n) { // 建堆：从最后一个非叶子节点开始 for (int i = n / 2 - 1; i >= 0; i--) { siftDown(arr, i, n); } // 依次把堆顶元素与末尾交换并调整 for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; siftDown(arr, 0, i); // 对缩小后的堆继续调整 } }

4.3 堆排序的复杂度分析与实战定位

堆排序建堆过程的时间复杂度是 O(n)（注意不是 O(n log n)，数学推导是利用二叉树高度累加得到的总和公式，证明过程考试偶尔会考），然后每趟下沉调整是 O(log n)，共 n 趟，总体 O(n log n)。空间 O(1)，这是它对比归并排序最大的优势。稳定性方面，堆顶元素与末尾元素交换时，可能打乱相同值的相对位置，所以不稳定。

堆排序工程上有个隐藏短板：内存访问是跳跃式的，对 CPU 缓存非常不友好。同样 O(n log n)，实际运行时间往往比快排慢 2~5 倍。所以日常排序任务，语言标准库基本都用快排（比如 C 的 qsort、C++ 的 std::sort 内省式混合排序），而堆排序真正的用武之地是 TopK 问题——在海量数据里找最大的 K 个元素，维护一个小根堆，堆顶就是当前第 K 大的门槛值，每个新元素只需跟堆顶比较，复杂度 O(n log K)，比全排序快得多。

教训：有次我在项目里用堆排序给 10 万条用户记录排序，实测比快排慢了三倍还不止。后来查资料才发现问题出在缓存局部性上。从那以后我给自己定了个规矩——堆排序只用在"需要原地排序且对最坏时间复杂度有硬性要求"或者"TopK、堆这种二选一场景"，一般数据排序直接调用标准库快排。

5. 归并排序：分治思想的完美实践

归并排序和前面几个排序思路都不一样。它的核心理念是"先把问题切到最小，再向上合并"，整个过程分拆和合并两个阶段，典型的分治策略。

5.1 归并排序的图解流程

归并排序把数组递归拆成两半，直到每个子数组长度为 1（天然有序），然后两两合并有序数组，依次向上返回。拿[8, 4, 5, 7, 1, 3, 6, 2]举例：

• 递归拆到最底层，分成 8 个单元素数组。
• 合并[8]和[4]成[4, 8]，合并[5]和[7]成[5, 7]，合并[1]和[3]成[1, 3]，合并[6]和[2]成[2, 6]。
• 继续合并两个长度为 2 的有序数组：[4, 8]和[5, 7]归并成[4, 5, 7, 8]；[1, 3]和[2, 6]归并成[1, 2, 3, 6]。
• 最后合并[4, 5, 7, 8]和[1, 2, 3, 6]，得到[1, 2, 3, 4, 5, 6, 7, 8]。

这个"归并过程"就是经典的二路归并：两个指针分别指向两个有序数组头部，谁小谁进入临时数组，直到全部处理完。

其中的一笔关键账是：归并排序的比较次数是固定的，无论数组初始顺序如何，每层都要做 n 次比较合并，层数是 log n，总复杂度稳定 O(n log n)。它不会像快排那样退化，这是它最大的优势。

5.2 归并排序的代码实现与空间开销

void merge(int arr[], int left, int mid, int right) { int i = left, j = mid + 1, k = 0; int n = right - left + 1; int* tmp = (int*)malloc(sizeof(int) * n); // 临时数组 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i <= mid) tmp[k++] = arr[i++]; // 左边剩余 while (j <= right) tmp[k++] = arr[j++]; // 右边剩余 for (i = 0; i < n; i++) { arr[left + i] = tmp[i]; // 回写 } free(tmp); } void mergeSort(int arr[], int left, int right) { if (left >= right) return; int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }

注意 merge 里的条件arr[i] <= arr[j]，用的是小于等于而不是小于，这样当左右两个子数组里有相等元素时，左边数组的元素先被取出，右边相等元素的相对顺序依然在它之后，归并排序因此是稳定的。这个细节很多教材不提，但手写代码时一旦写错，稳定性就丢了。

空间复杂度是 O(n)，因为每一层递归归并都要用到临时数组，虽然递归深度 log n，但同一时刻最多有一个完整长度的临时数组占用，所以额外空间是 O(n)。这也是归并排序唯一的"软肋"——内存开销大。但对于链表这类不能用随机访问的结构，归并排序反而是最佳选择，因为它只需要遍历指针就能实现排序。

5.3 归并排序的复杂度推导与"多路归并"扩展

归并排序时间复杂度的推导可以用递推公式表达：设 T(n) 是对 n 个元素排序的时间，则有 T(n) = 2T(n/2) + O(n)。用主定理或者展开计算可得 T(n) = O(n log n)。考试有时候会让你展开推导，过程是：T(n) = 2T(n/2) + n = 4T(n/4) + 2n = ... = 2^k T(n/2^k) + k·n，当 n/2^k = 1 时 k = log n，所以 T(n) = n·T(1) + n log n = O(n log n)。

归并排序在实际工程中还有一个重要变体：外部排序。当数据量大到内存放不下时（比如 10GB 文件排序），操作系统层面就是把文件切块，每块装载内存做归并排序，再通过多路归并合并成有序大文件。这就是为什么数据库和 MapReduce 底层离不开归并排序。理解了二路归并，自然就能扩展到 K 路归并：用一个大小为 K 的最小堆来快速选取 K 个序列中最小的当前元素，每次堆调整 log K，整体效率 O(n log K)。

6. 排序代码易错细节与考试避坑指南

最后这部分我从实战和考试角度出发，把七大排序里最容易翻车的几个点集中拎出来，帮你快速自查。这个板块的信息，是普通教材里不会专门给你标记出来的"血泪教训"。

6.1 边界条件与循环终止条件

排序代码写错，九成是边界问题。我总结了几个高频雷区：

• while (j >= 0 && arr[j] > tmp)里j >= 0的位置。一旦 j 变成 -1 才去访问 arr[j]，在 C/C++ 里就是数组越界，在 Java 里直接抛异常。正确做法是 j 减到 -1 之前就判断循环是否继续。
• 冒泡排序内层循环j < n - 1 - i，这个- i是为了忽略已经浮到末尾的有序区域。漏掉- i不会让结果错误，但会徒增大量无意义比较。
• 快排 partition 里的while (low < high && arr[high] >= pivot)不能丢掉low < high这个前置条件。原因很简单：如果 pivot 是当前区间最小值，high 指针会一路左移越过 low，出现 low > high 的混乱状态，整个数组就被"穿串"了。
• 堆排序中n / 2 - 1是最后一个非叶子节点下标，前提是数组下标从 0 开始。如果你用的是从 1 开始的数组，最后一个非叶子节点下标是n / 2，两者不能混用，考试时尤其容易搞混。

6.2 稳定性判断的快速记忆法

稳定性是选择题、判断题的常客。死记硬背容易混，我教你一个推理记忆法：

• 稳定：直接插入排序（相等不移动）、冒泡排序（相等不交换）、归并排序（左边先取）。这三个的共同特点是只在相邻或有序合并时操作，相等元素不会跨距交换。
• 不稳定：希尔排序（分组跨距交换）、简单选择排序（极值跨越交换）、堆排序（堆顶与末尾交换）、快速排序（partition 时相等元素可能被越过）。

一句话口诀："快些选堆"不稳定（快排、希尔、选择、堆排），剩下三个稳定。这个谐音梗我用了很多年，屡试不爽。

6.3 每个排序的"最好情况"考点总结

408 和面试有一个高频对比题："以下排序算法中，哪些的最好时间复杂度是 O(n)？"答案是直接插入排序、冒泡排序（带 flag 优化版）。原因我在前面说过，这两个算法能提前终止，而其他算法无论输入如何都必须跑完固定轮次。

还有一个容易混淆的点：简单选择排序的时间复杂度不随初始序列变化，无论有序还是逆序都是 O(n²)。它的"选择最小值"操作必须扫描完剩余所有元素才能确定，没有提前终止的机制。而归并排序也不依赖初始序列，始终保持 O(n log n)，但它的常数因子较大，小数据量排序不如插入排序快。

6.4 面试和考试现场手撕排序的"万能策略"

如果面试官让你手写排序，我建议你按照这个策略来：

• 如果只说"写个排序"，优先写"插入排序 + 快排"两个。插入排序证明你基本功扎实，快排证明你有高级算法意识，两者互补。
• 如果面试官指定"手写快排"，一定要在开头加一句"我选随机 pivot 或三数取中来避免有序数组退化"，这是明显的加分项，很多候选人栽在这里。
• 如果面试官问"海量数据 TopK"，用堆排序思路给出 O(n log K) 方案，并说明为什么不用快排——快排必须全量数据都在内存中，大数据场景下内存不够。
• 如果面试官问"链表怎么排序"，直接答归并排序，因为链表的随机访问特性决定了快排的 partition 在链表上效率很低，而归并只需要指针操作。

考试手撕代码时，时间有限，写核心函数即可。我给你的建议是：先把 partition 单独写出来，再写快排的递归函数；堆排序则分 siftDown 和 heapSort 两个函数写。函数的拆分本身就是给阅卷老师的"得分点"，因为即使最后结果有小 bug，核心逻辑的步骤分也拿到了。平时练习的时候，不要光在 IDE 里跑，一定要在纸上手写几遍，因为 IDE 的自动补全会掩盖你对变量声明和循环结构的真实掌握程度。

最后说几句个人感受。排序算法这章，我当年学的时候也觉得难，但后来发现的规律是：这七个算法本质上就三种思维模式，插入类是"维护有序区"，交换类是"比较后交换"，选择类是"每趟选极值"，归并是"分而治之再合并"。你只要抓住每种思维模式的"一句话核心"，代码就像顺着思路自己长出来一样，根本不用背。面试和考试再怎么变，核心考的就是这几个算法的复杂度、稳定性、边界条件、场景适配。把这篇文章里每一个算法的图解流程和易错点过一遍，再自己动手在纸上画几轮排序的过程，这个章节你就彻底拿下了。