排序算法练习题解答：从易到难吃透八大排序

排序算法练习题解答：从易到难带你吃透八大排序

这段时间有不少读者问我：“排序算法到底该怎么练？为什么书上的代码都能看懂，一关掉书自己写就卡壳？”这个问题问到了点子上。排序算法是数据结构与算法里的“基础科目”，笔试、机试、面试手撕代码、项目里的海量数据预处理，全都要用到它。光看理论没用，真正的功夫在“练”字上，而且要按套路练：先搞懂每种排序的核心思路，再动手写代码实现，最后用测试用例验证行为，并分析复杂度边界。

这篇文章我把自己平时带新人时整理的一套“排序算法练习题解答”体系放出来，从最基础的冒泡排序到工程中真正常用的快速排序、归并排序，一道题一道题带着你做。题目难度从一星到四星，每题都包含题目描述、思路拆解、参考代码、易错点、复杂度分析五个部分。不管你是准备面试还是备考期末，按这套题单练下来，整个人对排序的整体认知都会有明显提升。

需要说明的是，文中示例代码以通用伪代码风格为主，同时给出贴近主流语言习惯的实现片段。读者完全可以把代码改写成自己常用的语言来练习。我不建议直接背代码，而是建议先看思路、关上答案自己写一遍，再对照参考答案找差距。这样做一轮，比背十遍有效得多。

1. 内容整体设计与思路拆解

1.1 为什么排序算法值得专门刷一套题

很多初学者觉得排序就是“调一个函数”的事，不值得花时间。这其实是误解。排序算法是算法设计思想的微型缩影，它虽然只解决“排一排”这件事，但涉及了几个极其底层、又到处复用的能力：

• 循环不变式：比如插入排序的“左侧已有序”性质，这是很多更复杂算法正确性证明的基础。
• 分治思想：归并排序和快速排序是分治策略最经典的两道开胃菜，理解它们，后面学二分查找、线段树、最近点对都会顺利很多。
• 指针与索引操作：快速排序里的双指针双向扫描，写不写得对直接反映你对数组边界问题的掌控能力。
• 复杂度分析与数据规模估算：什么时候用O(n log n)的算法，什么时候能用O(n²)的暴力解法，这是做工程决策的基本功。

我见过太多“背模板”式学习者，面试时手写快排，边界条件写错直接崩掉。也有在真实项目中拿冒泡排序处理百万级数据的“事故现场”。这些本都可以靠一套有针对性的练习题避免。

这套练习题的设计原则是：每一题都聚焦一个明确的训练目标，题和题之间不重复，但难度梯度清晰。比如第一题只训练“单趟交换逻辑”，第二题开始引入“多趟循环边界”，第三题则要求你处理“元素重复时的稳定性”。这样一题一个坎，练完一遍能力曲线非常实在。

1.2 练习方案的选型逻辑：用什么顺序练

我把八大排序拆成了四个阶段：

1. 基础入门阶段（冒泡、选择、插入）：核心目标是建立“比较-交换”的直觉，理解复杂度最差场景。
2. 进阶结构阶段（希尔、堆）：核心目标是理解“减少逆序对”和“利用树结构”这两个优化思路。
3. 分治攻坚阶段（快速、归并）：核心目标是掌握递归拆分、合并、边界控制，这是面试手撕的重点。
4. 工程应用与综合（非比较排序如计数、桶、基数，以及排序稳定性应用）：核心目标是了解数据特征如何影响算法选型。

之所以不直接上快排，是因为快排里下标边界控制本身就是很多初学者最头疼的环节。如果先通过冒泡和插入建立了“循环边界感”，再上快排的双指针，大脑会更自然地处理那些+1、-1的问题。

1.3 这套题解决了什么问题

这套练习题想解决三个具体痛点：

• 碎片化学习——今天看一个视频，明天翻一篇博客，学了一堆但没串成网。这套题单把“排序”相关的核心能力点全部串在了一起。
• 眼高手低——看得懂代码但写不出代码。每个题我都给了“从零推导过程”，而不是甩一个答案让你背。
• 忽视边界与退化——很多题海战术只关注正常输入，一遇到空数组、单元素、全部相同就翻车。这套题里的陷阱题专门训练这类边缘情况。

对于一个希望系统掌握排序算法的学习者，我的建议是：不要跳题，哪怕你觉得自己已经会了冒泡排序，也要尝试不借助任何资料，徒手把它写出来，再对照下面的参考答案检查。

2. 核心细节解析与实操要点

在进入题目之前，先梳理几个所有排序题都会涉及的基础要点。这些点看起来“太基础”，但实战手写时栽跟头的往往就栽在这里。

2.1 比较器与稳定性：很多练习题没讲透的坑

排序的核心操作是“比较”和“交换”。在练习题里，比较通常就是数值大小比较，但真实场景里往往是对象排序。比如按年龄排学生，或按价格排商品。这时候你需要理解一个概念：比较器（Comparator）。

在大多数主流语言里，比较器是一个返回整数的函数：compare(a, b)。返回负数表示a应该在b前面，正数表示a应该在b后面，0表示“相等”。很多初学者在这里犯的第一个错误是：把返回值写成只返回0或1，而不是负数、正数的完整语义。这会导致某些语言的标准排序函数行为异常。

另一个概念是稳定性：排序后值相等的两个元素，其相对顺序是否保持不变。排序算法的稳定性在一些场景非常重要，比如先按班级排序，再按成绩排序，如果第二次排序不稳定，班级的顺序会被打乱。练习题中我会专门安排一道检测稳定性的题目。

2.2 原地排序与额外空间：为什么有的题要求“原地”

练习题中经常出现“请用原地算法实现”的要求。所谓原地排序，就是额外空间复杂度控制在O(1)或者O(log n)级别。这不仅是理论概念，实际工程中，当数据量大到几个GB甚至几十GB，任何“复制一份再排序”的写法都会直接把内存打爆。所以面试官常喜欢在快排、堆排这类题的追问环节里问一句：“你的解法额外空间是多少？能不能优化到原地？”

这里需要区分两个概念：递归调用栈空间和辅助数组空间。归并排序的辅助数组是O(n)，而快速排序的递归栈深度平均是O(log n)，最坏O(n)。为了压低快排最坏情况，练习题里有题目专门引导你优化“基准值选取”策略。

2.3 大O复杂度分析：不要死记结论，要会推演

排序算法复杂度，很多人是背下来的：“冒泡O(n²)、快排平均O(n log n)、堆排O(n log n)”。但如果追问一句“为什么快排平均是O(n log n)”，不少人就哑了。

一套好的练习题，要逼着你从代码推导复杂度，而不是背结论。比如冒泡排序两重循环，外层n趟，内层平均n/2次交换，合起来O(n²)。快排每次划分把问题分成两个规模大约一半的子问题，递归层数log n，每层总工作量O(n)，整体O(n log n)。推导一遍，比背结论牢固十倍。

3. 实操过程与核心环节实现

下面进入正题。我把这套排序练习题按难度梯度排列，每道题给出完整解答。为了避免读者产生“看一眼答案就觉得会了”的虚假掌握感，我在题干部分刻意做了限制，建议读者先自己写，再对照。

3.1 入门第一题：用“冒泡排序”把数组升序排列

题目描述： 给定一个整数数组，请使用冒泡排序将其按升序排列。原地修改，不要返回新数组。

思路拆解： 冒泡排序的核心行为是“相邻比较，逆序就交换”。每一趟都会把当前未排序部分的最大值“冒泡”到末尾。所以外层循环表示“需要进行多少趟”，内层循环表示“当前趟要比较到哪个位置”。著名的优化点是“如果一整趟都没有发生交换，说明已经有序，提前终止”。

参考代码：

python复制def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        # 每趟结束后，末尾i个元素已经就位
        for j in range(0, n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

易错点： 内层循环的上界必须是n - 1 - i，而不是n - 1。如果固定为n - 1，每一趟都会去比较已经就位的尾部元素，虽然不影响正确性，但大大降低效率。还有一个隐蔽问题是“比较符号”：如果题目要求升序，那就是arr[j] > arr[j + 1]时才交换，写成>=虽然结果一样，但会破坏稳定性，在专项训练中不可取。

复杂度分析： 最坏和平均情况都是O(n²)，最好情况（数组已经有序）在加入swapped标志后为O(n)。空间复杂度O(1)。这是一个稳定排序。

3.2 入门第二题：用“选择排序”找出每轮最小元素

题目描述： 用选择排序对整数数组进行升序排列。要求每轮从剩余元素中选出最小值，放到当前轮起始位置。

思路拆解： 选择排序把数组看作“左侧已有序区”和“右侧未排序区”。每一轮线性扫描未排序区，找到最小值下标，然后与未排序区的第一个元素交换。这个算法和冒泡的区别在于：冒泡是“边比较边交换”，选择排序是“比较完了再交换”，因此选择排序的交换次数少，但比较次数依然是O(n²)。

参考代码：

python复制def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

易错点： 必须记录最小值下标而不是最小值本身，否则交换时会丢失原位置的元素。另一个细节是，当min_idx == i时，可以跳过交换，虽然交换自己也不会出错，但写程序时显式判断能体现对边界情况的意识。

复杂度分析： 无论数据好坏，比较次数恒为n(n-1)/2，时间复杂度O(n²)。交换次数最多n-1次。空间O(1)。特别提醒：选择排序是不稳定的，因为交换时可能把相同值的相对顺序打乱。

进一步追问： 面试官常在这里追问：“选择排序为什么不稳定？能不能举个例子？”一个经典例子是数组[5, 5, 2]，第一轮扫描时找到最小值2在下标2，然后与下标0的5交换，原本在前面的第一个5就跑到了第二个5后面。这个例子建议亲手走一遍，会对稳定性问题有更深的体感。

3.3 进阶第三题：用“插入排序”对近乎有序的数组提速

题目描述： 实现插入排序。并在一个“只有少量元素错位”的数组上比较插入排序与冒泡排序的实际耗时。

思路拆解： 插入排序的核心思想是“像整理扑克牌一样”。处理第i个元素时，认为前i个元素已经有序，把它往左移动到正确位置。它的最佳时间复杂度O(n)让它非常适合处理“几乎有序”的数据。很多高级排序算法（如Timsort）在递归到最后阶段时，会切换到插入排序来加速。

参考代码：

python复制def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

易错点： 这个题的经典错误是交换式实现while j >= 0 and arr[j] > arr[j+1]: swap(...)。这样做虽然结果对，但增加了赋值次数，性能不如“移位式”写法。另一个细节是内层循环的边界判断，必须同时满足j >= 0，否则访问arr[-1]在大多数语言里会越界或产生错误结果。

经验心得： 插入排序是最适合手写练习的入门算法，因为它和“冒泡、选择”有本质区别：它的内层行为不是冒泡式的“把最大数漂到末尾”，而是“把新元素插入有序区”。很多面试者混淆了插入排序和冒泡排序的代码结构，建议用扑克牌实物模拟一遍，感受两者的操作差异。

3.4 分治第四天题：实现“快速排序”并处理边界

题目描述： 实现快速排序，要求不使用额外数组，原地完成排序。分别测试三种输入：完全随机数组、已经升序数组、全部相同元素的数组。

思路拆解： 快速排序的核心是分区。选一个基准值（pivot），把数组分成“小于等于基准”和“大于等于基准”两部分，然后递归排序两部分。它的平均性能极好，是很多语言标准库sort函数的默认实现思路。

参考代码（使用Lomuto分区或Hoare分区，这里给出更常见的Lomuto写法）：

python复制def quick_sort(arr, low, high):
    if low >= high:
        return
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    p = i + 1
    quick_sort(arr, low, p - 1)
    quick_sort(arr, p + 1, high)

易错点： 递归基条件low >= high很容易被漏掉等号。如果数组只有两个元素且已经有序（如[1, 2]），缺少等号会导致无限递归或函数调用栈溢出。另外，这个写法选择arr[high]作为基准值，在数组已经升序的情况下，每次分区很不平衡，复杂度退化到O(n²)，递归深度变成n，数据量大时会栈溢出。这个练习题就在逼你思考“基础版快排的局限性”，并为下一个题做铺垫。

复杂度分析： 平均O(n log n)，最好O(n log n)，最坏O(n²)。空间复杂度在递归栈维度平均O(log n)，最坏O(n)。

追问引申： 在实际工程中，为了规避有序数组下的退化，通常会使用“三数取中法”选取基准值，把low、mid、high三个位置的中位数作为基准。这也是很多公司面试中从“手写快排”进阶到“优化快排”的经典考察点。

3.5 进阶第五题：用“三路快排”解决大量重复元素

题目描述： 实现三路快速排序，专门处理数组中存在大量重复元素的情况，要求相同元素不需要重复交换。

思路拆解： 二路快排遇到大量重复元素时会做很多无意义的交换和分区。三路快排的理念是：把数组分成三块——“小于基准”、“等于基准”、“大于基准”。递归时只处理小于区和大于区，等于区直接跳过。这个思路在很多真实业务场景中非常有用，因为现实数据经常带有大量的重复值（如评分、状态码等）。

参考代码：

python复制def quick_sort_3way(arr, low, high):
    if low >= high:
        return
    lt = low
    i = low
    gt = high
    pivot = arr[low]
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    quick_sort_3way(arr, low, lt - 1)
    quick_sort_3way(arr, gt + 1, high)

易错点： 三路快排的指针移动逻辑是这道题的灵魂。当arr[i] > pivot时，把arr[i]和arr[gt]交换后，i不能自增，因为交换过来的arr[gt]还没和pivot比较过。很多第一次写三路快排的人在这里卡住。建议拿一个实际例子，比如[3, 1, 3, 2, 3]，在纸上手动走一遍交换过程，理解三个区间的边界如何动态维护。

复杂度分析： 在全部元素都相同的极端情况下，时间复杂度退化优化为O(n)，而不是普通快排的O(n²)。

3.6 综合第六题：用“归并排序”实现稳定排序，并处理链表

题目描述： 用归并排序对数组进行升序排列，要求稳定且空间复杂度为O(n)。进阶要求：对单链表进行归并排序，空间复杂度O(1)。

思路拆解： 归并排序是典型的分治算法。分解到单个元素，然后两两合并有序区间。它的稳定性和稳定复杂度使得它在处理“对稳定性有要求的大规模数据”时无可替代。链表版本的归并排序更是一个经典中的经典——因为链表不能随机访问，很多算法直接失效，而归并排序只需要从头到尾遍历，与链表结构天然吻合。

参考代码（数组版本）：

python复制def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

易错点： 数组切片的写法在每个递归层级都复制了一遍数组，实际空间占用高于O(n)。如果追求严格的O(n)额外空间，需要维护一个统一的辅助数组，每次合并复用。另一个隐藏错误是合并时比较符号写成<而不是<=，这会破坏稳定性——当左右两边的值相等时，要让左边元素先被取出，才能保证稳定性。

链表版本思路： 先用快慢指针找到链表中点，断开链表，递归排序两段，然后做有序链表合并。链表版本不需要辅助数组，但递归栈仍占用O(log n)空间，如果要严格的O(1)空间，需要改写为自底向上的迭代归并。

3.7 数据结构第七题：用“堆排序”找出第K大元素

题目描述： 先用堆排序实现数组升序排列，再用堆实现函数find_kth_largest，返回数组中第K大的元素。

思路拆解： 堆排序分两个阶段：建堆和逐个弹出堆顶。建堆用自底向上的下沉（sift down）方法，时间复杂度O(n)。弹出堆顶时，把堆顶和最后一个元素交换，堆大小减一，再下沉调整。

参考代码：

python复制def sift_down(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        sift_down(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, i, 0)
    return arr

易错点： 建堆的起始下标是n // 2 - 1，这是因为叶子节点不需要下沉。很多初学者写成n // 2或n - 1，前者漏掉边界，后者重复操作。另一个细节：弹出的循环中，每一次交换后，arr[i]位置上的元素已经“永久脱离堆结构”，所以sift_down作用的数组长度是i而不是n。

第K大解法： 维护一个大小为K的小顶堆，遍历数组时不断往堆里塞元素，堆超过K就弹出堆顶。遍历结束后，堆顶就是第K大元素，时间复杂度O(n log K)。如果K远小于n，这比“先完全排序再取下标”划算得多。

3.8 挑战第八题：手写“计数排序”处理有限整数范围

题目描述： 给定一个数组，元素取值在0到100之间，使用计数排序实现线性时间排序。

思路拆解： 计数排序突破O(n log n)的关键前提是数据范围已知且有限。它的核心是统计每个数值出现的次数，再生成前缀和，最后根据前缀和把元素放到输出数组的正确位置。这个算法是后续所有非比较排序的基石。

参考代码：

python复制def counting_sort(arr, max_val=100):
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    n = len(arr)
    output = [0] * n
    for num in reversed(arr):
        count[num] -= 1
        output[count[num]] = num
    return output

易错点： 第二次遍历必须从原数组末尾向前处理，这样相等元素才能保持相对顺序，保证稳定性。如果贪省事从前往后遍历，那么计数排序就变成了不稳定排序。另外，如果max_val设定小于实际数组最大值，会越界访问，所以使用前需要动态检查。

复杂度分析： 时间复杂度O(n + k)，其中k是数值范围。当k远大于n时，计数排序反而不划算，这也是理解后续基数排序的切入点。

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

4.1 写了快排老是死循环或栈溢出，怎么排查

这是练习中出现频率最高的一类问题。死循环和栈溢出往往是同一个原因：基准值分区后，两个子问题的规模没有变小。

排查步骤：

1. 打印基准值和mid位置：手写快排时，在分区后打印p的值，检查它是否严格位于low和high之间。
2. 检查分区函数的返回值语义：Lomuto分区返回的是基准值的最终位置，pivot本身已经在正确的位置上，递归区间应该是[low, p-1]和[p+1, high]，不能把p包含进去。
3. 检查边界条件：low >= high时必须终止。如果写成low == high，在只有两个元素的递归场景下会漏终止。

4.2 归并排序结果正确但空间超限，如何优化

数组切片式写法虽然易懂，但每层递归都产生新数组，总空间占用为O(n log n)，而不是理论上的O(n)。排查方式为：统计递归调用过程中创建的列表长度总和。优化方法是声明一个全局辅助数组，合并时用辅助数组暂存结果，最后按区间复制回原数组。这种“用一个辅助数组”的做法，是所有工程级归并排序的标准实现。

4.3 插入排序和冒泡排序的边界老写错，如何记忆

一个实用的记忆技巧是想象自己手上有一排数字卡片：

• 冒泡排序：内层循环从左到右扫，比较的是j和j+1，每次都关心“右边那个会不会更小”。
• 插入排序：外层循环从第二个元素开始，内层循环向左反向扫，关心“当前key能不能往左钻”。

写错边界多半是对“比较对象”的记忆偏差。建议在草稿纸上把一次普通比较的索引变化画出来：冒泡写arr[j] > arr[j+1]，插入写arr[j] > key。记住这两个标志性表达式，边界就不会再混淆。

4.4 题目要求“输出前K个最小元素”，该用什么排序策略

千万别一上来就全排序。这里有一个非常实用的工程决策过程：

• 如果K非常小（比如1到100），用最大堆维护前K个最小元素，每次处理新元素时和堆顶比较，如果更小就替换。时间复杂度O(n log K)。
• 如果K和n接近，直接排序或快速选择。
• 如果数据可以离线处理且范围有限，考虑计数排序或桶排序。

这一题考察的是“根据数据特征选择算法”的能力，它比“手写一个堆排序”更接近真实工作场景。

4.5 手写排序算法时，如何避免“思路对，代码崩”的窘境

我自己的练习习惯是：先写注释再写代码。 把算法的每一步用中文注释写出来，比如“从i+1到n之间找最小值下标”，然后再逐行填代码。这样可以避免大脑在“编码”和“算法逻辑”两个层面来回切换导致的错乱。写完代码后，用三个固定测试用例验证：

• 空数组[]
• 单元素数组[1]
• 倒序数组[5,4,3,2,1]
• 全部相同元素的数组[3,3,3,3]
• 已经有序的数组[1,2,3,4,5]

能一次通过这五个用例，再讨论优化和进阶。这套“最小验证集”是我面试前热身时的固定流程，推荐给所有读者。

5. 实践反思：排序算法练习题的后续扩展方向

按前面这套题单练完，你已经具备对八大排序代码级的基本掌控能力。但要继续往深走，还有几个方向值得拓展。

• 反向训练：给定一个有序数组，要求输出“构成排序过程的每次交换序列”。这个训练逼你从结果反推过程，对理解排序机制很有帮助。
• 多路归并：归并排序从二路扩展到多路，用于外部排序场景。练习题可以设计为“合并k个有序数组”，这是面试常客。
• 排序稳定性在业务中的应用：设计一个场景，要求“先按优先级排序，再按序号排序”，用不稳定的快速排序实现，并观察输出结果如何失真，从而体会稳定性在实际应用中的价值。
• 并行排序：尝试把归并排序的左右部分拆分并发执行，再合并。这个练习虽然简单，但能让你对多线程并行分治产生直观理解，为后续学习MapReduce等框架打下基础。

我在实际练习中感受最深的一点是：排序算法的学习曲线不是线性的。你可能一周练会了所有代码，但对复杂度和边界问题的理解要到几个月后、碰到实际项目中的大数据量时，才真正内化。所以不要急，也不要觉得“练完一遍就毕业了”。留一套题单隔几个月重做一次，每次重做，你都会发现自己上一次没注意到的东西。比如我第一次重做三路快排时，才真正理解了为什么那个i在某些分支下不能自增；第三次重做堆排序时，才彻底搞懂了n // 2 - 1的推导过程。这本身就是一道持续迭代的练习题。