排序算法练习题全解析：从冒泡到快排的实战演练

排序算法是所有算法学习绕不开的一关，不管你是准备笔试面试、应付课程设计，还是单纯想把代码功底打扎实，最后都会发现一个事实：光看教程和动画演示，看完觉得自己懂了，真让你手写一个快排、分析一次归并合并过程，立刻卡壳。这个现象太正常了，排序算法考的不是记忆，而是你对“每一轮比较、每一次交换、每一个指针移动”背后逻辑的掌握程度。这也是我整理这组排序算法练习题解答的初衷：用题目逼着你把细节抠明白，比反复看十遍讲解都管用。

这篇文章不是那种贴几个结论、抄几段代码就完事的水文。我按题型把最常出现的排序练习拆成了五类：结构模拟、性质判定、实现修正、应用变形、综合选型，每一类都配了具体的题目和完整解答。学完你能得到三样东西：遇到排序题知道怎么下手，手写代码时不容易在边界条件上翻车，以及面试里被问到“为什么”的时候能接得住。适合所有正在刷算法题、或者准备系统复习排序知识的读者。

1. 选题之前先搞清楚：排序练习题到底在练什么

很多人刷排序题有个误区，觉得把八大排序的代码背下来就万事大吉。但你去看真正有价值的练习题，几乎没有一道是“默写快排”这种纯记忆题。它们考核的是更深层的能力：你清不清楚算法每执行一步数组长什么样、你能不能判断一个排序算法在特定数据下的表现、你能不能把排序思想迁移到其它问题上。所以我选题的时候，刻意让每种题型都指向一种具体能力。

1.1 结构模拟类题目

结构模拟类题目，就是给你一个具体的数组，让你写出某排序算法执行到某一轮之后的结果。比如“冒泡排序第一趟结束后数组是什么状态”“插入排序完成第三次插入后序列长什么样”“堆排序建堆完成后数组顺序是什么”。

这类题看起来机械，实际上是最能暴露问题的。因为只要你写错一个交换、一个比较的顺序，整个结果就不对，没有蒙混过关的可能。我自己带新人时发现，十个人里有六个会在这类题上出错，出错原因基本集中在：循环边界没算清、相等元素是否交换搞混、以及数组索引从0开始还是从1开始没对齐。所以这个题型是所有排序练习的地基，先把它练扎实，再去谈应用和变形。

1.2 性质判定类题目

第二类是性质判定，典型问法是“这个排序算法稳定吗”“最好、最坏、平均复杂度分别是多少”“是原地排序吗”。这类题在笔试里经常以选择题或者判断题的形式出现，看似简单，但陷阱非常多。

一个最常见的例子就是选择排序。很多人因为插入排序是稳定的，就想当然认为选择排序也稳定，其实选择排序会因为“交换”操作破坏相同元素的相对顺序，这个细节下面我会专门展开。性质判定类题目练的不只是记忆，而是让你能针对一个具体算法，理性分析出它的运行特点。你会知道为什么快排在近乎有序的数据上反而慢，为什么归并排序无论什么数据都是O(n log n)，为什么堆排序的时间复杂度看起来很美却在实际中排不过快排——这些都是从性质推导出来的，不是背来的。

1.3 实现修正类题目

实现修正类题目，给你一段看似正确但运行结果错误的代码，让你找出Bug并修复。这类题在面试白板写代码时特别常见，考官不会直接让你背排序，而是写一段有问题的快排或堆排，看你能否定位问题。

这种题练的是调试能力和临界条件意识。排序代码里常见的Bug集中在几个点上：快排的双指针交换条件在边界上写错导致越界、堆排序的堆大小没有在每次删除堆顶后递减、归并排序的临时数组下标没对应上原始数组的偏移量。这些Bug在数据量大或者数据特殊时才会暴露，如果你对算法每一步的状态不够熟悉，根本找不到。所以我建议刷排序题时，不要只做正向默写，也要做反向纠错，这种训练的性价比极高。

1.4 应用变形类题目

应用变形类题目，是把排序思想包装成其它问题来问。经典的例子包括：找出数组中第K大的元素、统计数组中的逆序对数量、合并两个有序链表、按照自定义规则给字符串排序。这类题的难点在于识别出“这其实是在考排序”，然后用排序的思维框架去解。

比如逆序对数量，表面上是计数题，实际上只要你在归并排序的合并阶段加一条统计语句就能高效解决。TopK问题表面上是查找题，但最经典的解法之一就是堆排序。这种迁移能力是刷题最有价值的部分，它能让你从“会写排序”升级成“会用排序”。我把这类题单独放在第四章，因为它们最能体现练习的价值——你练的不是算法本身，而是算法思维。

2. 基础排序练习题解答：冒泡、选择、插入

基础排序是指时间复杂度在O(n^2)级别的三类排序，冒泡、选择、插入。它们是很多人口中的“简单排序”，但简单不等于容易做对。下面这三道题，覆盖了基础排序里最容易出错的三个环节：循环优化、移动次数统计、稳定性反例构造。

2.1 练习题1：带标志位的冒泡排序

题目： 给定数组 [5, 1, 4, 2, 8]，写出一趟冒泡结束后数组的状态。然后说明：如果在代码中加入“是否发生过交换”的标志位，在哪种数据形态下收益最大？

解答： 冒泡排序的思想是从左到右依次比较相邻元素，如果前一个大于后一个就交换。第一趟里发生的事情是：

• 比较 5 和 1，5 > 1，交换，数组变成 [1, 5, 4, 2, 8]；
• 比较 5 和 4，5 > 4，交换，数组变成 [1, 4, 5, 2, 8]；
• 比较 5 和 2，5 > 2，交换，数组变成 [1, 4, 2, 5, 8]；
• 比较 5 和 8，5 < 8，不交换。

所以第一趟结束后数组为 [1, 4, 2, 5, 8]。最大值8已经沉到末尾，下一趟只需要比较前四个元素。

关于标志位的意义，看这段代码就明白：

python复制def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break

如果某一趟全程没有发生交换，说明数组已经有序，可以提前终止外层循环。这个标志位在“数组原本就基本有序”的时候收益最大。比如 [1, 2, 3, 5, 4]，第一趟把5和4换位后数组变为有序，第二趟扫描发现没有交换，直接结束，总共只做了两趟扫描。最理想情况下，即数组一开始就是升序，冒泡排序只需一趟扫描就能发现已经有序，时间复杂度直接降到O(n)。这个优化思路也体现了选择排序和冒泡排序的本质区别：冒泡可以利用“局部有序”快速退出，选择排序做不到。

2.2 练习题2：插入排序的移动次数统计

题目： 对序列 [9, 3, 7, 2, 8] 执行插入排序，统计整个过程中元素移动的总次数。这里的“移动”指的是把较大的元素往后挪一格的赋值操作。

解答： 插入排序的思想是维护一个有序前缀，每轮把新的元素插入到前缀的正确位置。初始时有序前缀是 [9]，我们从第二个元素开始逐步处理：

• 处理 3：与9比较，9比3大，把9后移一位，序列变成 [9, 9, 7, 2, 8]，然后把3放到开头，有序前缀为 [3, 9]。移动1次。
• 处理 7：从后往前比较，9比7大，把9后移，变成 [3, 9, 9, 2, 8]；再比较3和7，3比7小，停止，7放到中间，有序前缀为 [3, 7, 9]。移动1次。
• 处理 2：依次把9、7、3往后移，序列先变成 [3, 7, 9, 9, 8]，再变 [3, 7, 7, 9, 8]，再变 [3, 3, 7, 9, 8]，最后2放到最前面。移动3次。
• 处理 8：把9后移一位，8放在9前面。移动1次。

总移动次数 = 1 + 1 + 3 + 1 = 6。

如果你不想一步步模拟，这里有个快速统计技巧：插入排序的总移动次数，等于每个元素左边比它大的元素个数之和。比如9左边没有比它大的元素，贡献0；3左边有1个比它大的元素（9），贡献1；7左边有1个（9），贡献1；2左边有3个（9、3、7），贡献3；8左边有1个（9），贡献1。总数就是0 + 1 + 1 + 3 + 1 = 6。这个等价关系非常有用，它能让你在纸上快速算出答案，也解释了为什么插入排序在近乎有序的数组上效率极高——每个元素左边比它大的元素很少，移动次数自然少。

2.3 练习题3：三种基础排序的稳定性判定与反例构造

题目： 判断冒泡排序、选择排序、插入排序是否稳定，并为“不稳定”的算法构造一个具体反例。

解答： 稳定性定义是：如果两个相等元素的相对前后顺序在排序后保持不变，算法就是稳定的。判断方法不是背结论，而是看算法在执行过程中是否会让相等元素发生相对位置交换。

• 冒泡排序：稳定。因为它只在 a[j] > a[j + 1] 时交换，等于的时候不交换，相等元素永远不会越过对方。
• 插入排序：稳定。因为插入时是从后往前扫描，遇到大于当前元素的才后移，遇到相等的元素就停下来，把新元素放在它后面，相对顺序保持。
• 选择排序：不稳定。这是很多人容易错的点。看反例：数组 [5a, 3, 5b, 1]，其中5a和5b数值相等，标记a和b只是为了区分来源。第一轮选择排序找到最小值1，把它和第一个位置的5a交换，数组变成 [1, 3, 5b, 5a]。此时5a排到了5b的后面，相对顺序被破坏，所以选择排序不稳定。

构造稳定性反例的核心方法是：让一个较小的元素和靠前的相等元素交换，把另一个相等元素留在后面。只要你理解了选择排序“选最小值换到前面”这个动作，反例其实很容易构造。这道题的价值在于，面试时不仅会问结论，更会问“为什么”，你能不能三句话讲清楚选择排序为什么不稳定，比背住结论重要得多。

3. 进阶排序练习题解答：快速、归并、堆

进阶排序是分治思想的集中体现，也是笔试和面试的绝对主角。下面四道题分别覆盖了快排的Partition过程、复杂度退化防御、归并排序的经典应用、堆排序的建堆细节，每一个都是高频考点。

3.1 练习题4：快速排序的 Partition 过程与边界处理

题目： 对数组 [3, 7, 8, 5, 2, 1, 9, 5, 4] 执行快速排序的 Partition 操作。基准取最后一个元素4，采用Lomuto分区方案，写出 Partition 完成后数组的状态以及基准元素的最终位置。

解答： Lomuto 方案的核心是用一个指针i维护“小于等于基准的区间的末尾”，遍历指针j从左向右扫描。初始时 i = -1，基准 pivot = 4。逐步遍历：

• j=0，值3，小于等于4，i变为0，交换 a[0] 和 a[0]，数组不变。
• j=1，值7，大于4，跳过。
• j=2，值8，大于4，跳过。
• j=3，值5，大于4，跳过。
• j=4，值2，小于等于4，i变为1，交换 a[1] 和 a[4]，数组变为 [3, 2, 8, 5, 7, 1, 9, 5, 4]。
• j=5，值1，小于等于4，i变为2，交换 a[2] 和 a[5]，数组变为 [3, 2, 1, 5, 7, 8, 9, 5, 4]。
• j=6，值9，大于4，跳过。
• j=7，值5，大于4，跳过。

扫描结束，i = 2。最后把基准4放到 i + 1 的位置，也就是索引3，交换 a[3] 和 a[8]，数组变为 [3, 2, 1, 4, 7, 8, 9, 5, 5]。基准4的最终位置是索引3。可以看到，基准左边的 [3, 2, 1] 都不大于4，右边的 [7, 8, 9, 5, 5] 都不小于4。

这道题最常犯的错误是把“小于等于”和“小于”搞混。如果只能用“小于”，那么等于基准的元素会全部跑到右边，虽然最终排序还是正确，但左右规模可能严重不均。另外要特别注意的是，扫描结束后基准和 a[i + 1] 交换，这个位置恰好是“第一个大于基准的元素”的位置，如果你写成和 a[i] 交换，基准就会被放错地方。

3.2 练习题5：快排为什么退化，以及三种防御手段

题目： 对一个已经按升序排列的数组执行快速排序，基准固定取第一个元素。请问递归深度是多少？时间复杂度退化成什么？如何防御？

解答： 如果数组已升序，固定取第一个元素作为基准，每次 Partition 的结果是：基准是最小元素，它被放到第一个位置，左边为空，右边是剩下的 n-1 个元素。每次划分只消除了一个元素，递归深度变成 n，时间复杂度退化成 O(n^2)。这在工程上不是小概率事件，恰恰是最常见的输入之一——很多业务数据本来就是按某种顺序排列或近似排列的。

防御手段通常有三层：

• 三数取中：取区间首、中、尾三个元素的中位数作为基准，能基本避免有序序列的退化。
• 随机基准：在区间内随机选一个位置和首元素交换，再执行正常的Partition。这样“有序数组”也被随机化破坏了，从概率上避免最坏情况。
• 小区间插入排序：当递归区间长度小于某个阈值（比如10或16）时，改用插入排序。快排在递归到很小区间时，调用开销超过收益，插入排序在小规模数据上反而更快。这个优化也被大量工业级排序实现采用。

补充一个容易被误解的点：随机基准并不能完全消灭最坏情况，只是让最坏情况的概率趋近于0。只要你运气差到每次都选到最小元素，退化依然会发生。所以在时间复杂度分析时，随机化快排的期望复杂度是O(n log n)，最坏复杂度依然是O(n^2)，这个说法要严谨。

3.3 练习题6：归并排序的逆序对计数

题目： 使用归并排序合并两个有序子数组 [2, 5, 8] 和 [1, 3, 9]，写出合并过程中每一次比较的结果，并统计原始数组 [2, 5, 8, 1, 3, 9] 中的逆序对数量。

解答： 归并排序的合并阶段是统计逆序对的关键战场。逆序对的定义是：如果 i < j 且 a[i] > a[j]，那么 (a[i], a[j]) 就是一个逆序对。合并两个有序数组时，每当我们从右半部分取走一个元素，它比左半部分剩余的所有元素都小，这就能一次性贡献多个逆序对。

模拟合并过程：

• 比较 2 和 1，取右半的1。此时左半还剩下 [2, 5, 8] 三个元素，也就是说1和它们都构成逆序对，计数加3。
• 比较 2 和 3，取左半的2。
• 比较 5 和 3，取右半的3。此时左半剩下 [5, 8] 两个元素，计数加上2。
• 比较 5 和 9，取左半的5。
• 比较 8 和 9，取左半的8。
• 左半耗尽，取右半的9。

总逆序对数量为 3 + 2 = 5。验证一下原始数组 [2, 5, 8, 1, 3, 9]，逆序对确实是 (2,1)、(5,1)、(5,3)、(8,1)、(8,3) 这5对。

基于这个思路，可以在归并排序代码里加一行统计，把逆序对问题的时间复杂度从 O(n^2) 降到 O(n log n)。核心代码逻辑是：只要右半部分的元素被选中，就说明左半部分剩余的所有元素都大于它，此时把左半剩余数量累加到答案里。这个“在合并中顺便统计”的模式很经典，值得多写两遍体会一下。

3.4 练习题7：堆排序的建堆过程模拟

题目： 把数组 [4, 1, 3, 12, 9, 6] 构建成一个大顶堆，写出建堆完成后数组的状态。并说明为什么建堆的时间复杂度是O(n)，而不是O(n log n)。

解答： 建堆的操作叫下沉（sift down），从最后一个非叶子节点开始，自底向上调整。数组长度为6，最后一个非叶子节点是索引 (6-2)/2 = 2，也就是值为3的节点。

• 下沉索引2：节点3，子节点是索引5的6，6大于3，交换，数组变为 [4, 1, 6, 12, 9, 3]。
• 下沉索引1：节点1，子节点是索引3的12和索引4的9，取较大的12，交换，数组变为 [4, 12, 6, 1, 9, 3]。1下沉到索引3后是叶子，结束。
• 下沉索引0：节点4，子节点是索引1的12和索引2的6，12较大，交换，数组变为 [12, 4, 6, 1, 9, 3]。4下沉到索引1，它的子节点是索引3的1和索引4的9，9较大，交换，数组变为 [12, 9, 6, 1, 4, 3]。4此时是叶子，结束。

建堆完成后数组为 [12, 9, 6, 1, 4, 3]，它满足大顶堆性质：任何一个父节点都不小于它的子节点。

关于复杂度，很多人误以为建堆是O(n log n)，因为觉得每个元素下沉log n次。但仔细分析会发现：高度越低的节点数量越少，而且它们的下沉距离也短。堆的高度是log n，但第一层只有一个根节点要下沉log n次，第二层两个节点各下沉log n减1次，越往下节点越多、下沉次数越少。把每层的工作量加起来，你会发现它是一个收敛的等差级数，总和是O(n)。这个结论经常被拿来当考察点，如果你能现场推一遍，会明显加分。

4. 实战变形练习题解答：把排序思想用到具体问题上

这个部分的题目不再问“怎么排”，而是问“用排序怎么解决这个问题”。每一道题都是一类经典场景的代表。

4.1 练习题8：三个最快的 TopK 方案对比

题目： 找出包含n个元素的数组中最大的K个元素。要求给出三种不同思路，并说出各自的时间复杂度、空间复杂度和适用场景。

解答： 这是排序应用最经典的变形题，常见方案有三种：

• 全局排序法：先对数组做一次完整排序，取最后K个。时间复杂度 O(n log n)，空间O(1)（如果原地排序）。代码最简单，但n很大时就亏了，因为排序把不需要的位置也排掉了。
• 堆方案：维护一个大小为K的小顶堆，数组遍历一遍，如果当前元素比堆顶大，就替换堆顶并下沉。时间复杂度 O(n log K)，空间 O(K)。当K远小于n时，这是效率最均衡的方案。找最小的K个元素时反过来，用一个大小为K的大顶堆，堆顶是当前K个候选里最大的，新元素比堆顶小就替换。
• 快速选择法：借鉴快排的Partition思想，每次把数组分成“大于基准”和“小于基准”两部分，根据基准的位置判断目标在左还是在右，只递归处理一侧。平均时间复杂度 O(n)，最坏O(n^2)，空间O(1)。如果不需要保证K个元素之间的相对顺序，这是方案里理论最快的。

三种方案的取舍在实践中非常清晰：数据量不大直接用全排序；数据量大且需要频繁取TopK，用堆；只要单次查询、内存有限且能接受偶发的最坏情况，用快速选择。工程里的流式数据场景，比如日志TopK统计，几乎都用堆方案，因为数据是不断进来的，堆可以增量维护，其它两种方案都需要拿到全量数据才能启动。

4.2 练习题9：合并两个有序单链表

题目： 合并两个有序单链表，链表A的值为 [1, 3, 5, 7]，链表B的值为 [2, 4, 6]。分别用递归和迭代方式实现，并对比两种方式的空间复杂度。

解答： 合并有序链表本质上是归并排序的合并阶段去掉数组下标操作，改用指针移动。迭代版本是标准解法：

python复制def merge_two_lists(a, b):
    dummy = ListNode(0)
    cur = dummy
    while a and b:
        if a.val <= b.val:
            cur.next = a
            a = a.next
        else:
            cur.next = b
            b = b.next
        cur = cur.next
    cur.next = a if a else b
    return dummy.next

这里用了一个虚拟头节点（dummy），好处是不用单独处理结果链表的头节点为空的情况，最后返回 dummy.next 即可。

递归版本更短，但要理解“递归函数返回的是合并后的链表头”这个设计：

python复制def merge_two_lists(a, b):
    if not a:
        return b
    if not b:
        return a
    if a.val <= b.val:
        a.next = merge_two_lists(a.next, b)
        return a
    else:
        b.next = merge_two_lists(a, b.next)
        return b

两个版本的时间复杂度都是O(n+m)。空间上，迭代用O(1)额外空间，递归因为调用栈的存在是O(n+m)的空间。链表题里递归好在代码短，但面试时可以顺势提一句“递归有栈溢出风险，工程上优先迭代”，能展示你的实际工程意识。这道题还提醒了一点：排序算法的思想不依赖具体数据结构，数组上的归并逻辑迁移到链表上，只要把“索引移动”换成“指针移动”，一切依然成立。

4.3 练习题10：一道选择填空题背后的设计权衡

题目： 给下列场景选择最合适的排序算法：(1) 数据量不大但内存极紧，希望额外空间尽量小；(2) 数据近乎有序，单次排序；(3) 需要稳定排序且数据量较大。请说明理由。

解答： 这类题在练习里属于综合应用，考察的是你对每种算法的性格特点足够熟悉。

场景1，内存极紧：选堆排序。堆排序的额外空间是O(1)，原地排序，虽然实际运行速度和缓存友好度不如快排，但空间占用是硬指标。插入排序、冒泡排序同样O(1)空间，但O(n^2)的复杂度在数据量稍大时就扛不住。归并排序直接排除，因为它需要O(n)的辅助空间。

场景2，数据近乎有序：选插入排序。插入排序在近乎有序的数据上接近O(n)，而且实现简单。很多生产环境的排序库也会在快排递归到小区间时切到插入排序，利用的正是这个特性。

场景3，需要稳定且数据量大：选归并排序。能在O(n log n)时间内完成并且保持稳定的主流算法就是归并排序。注意快排虽然平均更快，但它不稳定；堆排也不稳定。如果稳定性是硬性要求，归并是没有选择的选择。当然它的代价是O(n)额外空间，在部分对空间不敏感的业务场景里，这个代价完全可以接受。

这道题真正的考点不是背结论，而是让你理解“排序算法没有全能最优解”，每种算法都有它最适用的场景，能说出选择的理由比选择本身更重要。

5. 刷完这组练习后，我踩过的坑和排查方法

最后一章是我自己在反复刷这些练习时总结出来的经验教训。很多问题不是光看标准答案能避开的，只有自己写错一遍、再回头对比，才记得住。

5.1 边界条件错到怀疑人生

排序代码的Bug高发区几乎都是边界条件。我见过太多次快排的递归里没有判断 start < end，导致空区间也递归调用，最后栈溢出；也见过堆排序删除堆顶后忘记把堆大小减一，导致已经排好的最大值又参与下一轮下沉，整个数组乱套。

经验是：写完排序代码后，不要急着拿大数组测，先用长度为0、长度1、长度2的数组跑一遍，再跑一个全是相同元素的数组。排序算法面对这三种输入时边界最容易出错。比如长度为2的数组排降序，冒泡排序需要恰好交换一次；全是相同元素时，冒泡和插入必须一趟结束，如果你用了阈值的优化写法，必须保证相等元素不会被误判成需要交换。

5.2 稳定性判断不能靠背诵，要会构造反例

稳定性这个结论，靠背很容易混。我的建议是，不要只记“快排不稳定、堆排不稳定、选择不稳定”这个列表，试着给每个不稳定的算法亲手构造一个反例。构造的过程会让你真正理解原因。

稳定的算法也有值得琢磨的地方。比如插入排序为什么稳定？因为扫描时遇到相等的元素就停下来。你把代码里的 a[j] > key 改成 a[j] >= key 之后，稳定性立刻就被破坏了。这个改动是稳定性问题最好的实验素材：你可以亲手验证“一个排序算法的稳定性是建立在严格的大小比较约定上的”。理解了这一层，以后任何一道“修改排序算法使其稳定/不稳定”的变形题，你都能应对。

5.3 复杂度结论要在具体数据形态下才成立

完全有序的数组对插入排序是O(n)，对固定基准的快排却是O(n^2)。所以复杂度从来不是脱离数据形态存在的。我之前带新人时出过一道题：同一个数组，用冒泡排序排需要一趟结束，用固定基准的快排却递归了n层，问为什么。能答上来的人，一定不是背复杂度表的人。

排查类似问题时的思路建议是：把复杂度分析拆成“最好情况”“最坏情况”“平均情况”三列，然后逐个思考什么样的输入会触发哪种情况。你会得到一个规律：触发最好情况或最坏情况的数据形态，才是面试官最爱考的。比如堆排序复杂度稳定在O(n log n)，但它在现实中的常数项较大，实际表现常常不如快排，这个“理论复杂度好看但实际不快”的现象，也是复杂度列表中无法体现的重要一面。

5.4 十分钟完成的排序选型速查表

最后送你一张我平时自己用的速查表，它总结了几种主流排序的核心性质。刷题之前扫一眼，能让思路清晰很多：

我自己整理这套练习时的最大体会是：排序算法你从表面看是知识，训练多了就会发现它其实是判断力。判断一个算法在什么场景下正确、什么场景下最快、什么场景下会崩掉，这种能力才是刷题留下的真正资产。希望这些题目和解答，能帮你在手写排序时少走一些我走过的弯路。