简介面向算法初学者、备考者及编程开发者的排序算法学习资料系统梳理了七种基于比较的排序算法选择排序、插入排序、归并排序、快速排序、堆排序、冒泡排序与希尔排序。内容涵盖每种算法的核心思想、执行步骤、时间复杂度与稳定性分析并结合 Java 代码讲解各自的适用场景与局限性能够帮助读者从原理到编码系统掌握排序模块。压缩包共 18 个文件包含 15 个 Java 源文件、1 份 Markdown 说明文档以及 LICENSE、gitignore 文件包体仅 18KB精简轻量便于直接阅读和快速查阅。目前已有 1816 人学习下载。借助源码与文档对照读者可深入理解七种排序的递归与迭代实现细节同时获得算法选型与优化思路是一份实用且易上手的算法参考资料。 从接触编程到现在排序算法一直是个绕不开的东西。说它基础是因为学校里教、面试里考、框架源码里也藏着它的影子说它难是因为真让你把七八种排序一次性说清楚、写正确、讲明白复杂度很多人反而会卡壳。这篇博文把七种基于比较的排序算法一次性整理清楚——选择排序、插入排序、归并排序、快速排序、堆排序、冒泡排序、希尔排序逐个拆原理、贴代码、讲复杂度最后再聊聊稳定性和实际场景里怎么选型。不管你是准备面试的开发者还是想系统复习数据结构的人这篇都适合收藏起来当工具文用。我写这篇的态度很直接不搞花活只讲干货。代码用 Python 写思路通用转成 Java、C 也不费劲。每种排序我都会给出完整可运行的实现再补上那些教科书里不讲、但实战中容易踩的坑。1. 先把排序这件事想清楚选型比手写更重要1.1 评价排序算法到底在看什么很多人学排序算法上来就背代码背完就忘。我建议你先建立一套评价维度所有排序的本质都是在回答这几个问题跑得快不快、占内存多不多、稳不稳定、实现麻不麻烦。“跑得快”对应时间复杂度但要分最好、最坏、平均三种情况看。比如快速排序平均是 O(n log n)最坏却是 O(n^2)这两者的差距在实际数据里可能差出几十倍。“占内存”对应空间复杂度归并排序虽然快但需要额外的 O(n) 空间内存敏感的场景就要犹豫。“稳定”指的是值相等的元素在排序后能否保持原来的相对顺序这个属性在真实业务里很重要后面我用例子单独说。“实现麻不麻烦”看着不关键但在工程里真的很影响出 bug 的概率快排的 partition 写错过的人应该深有体会。所以在动手写排序之前先想清楚你的数据长什么样数据量级是多少是否近乎有序是否允许额外内存开销是否需要稳定排序。想清楚这几点选型就成功了一半。1.2 七种排序其实只属于四个思路把七种算法看成一团乱麻是因为没按思路归类。基于比较的排序最底层的核心操作只有两类比较大小和交换/移动元素。七种算法就是这两类操作的四种组合思路。第一种思路是“暴力枚举”代表是冒泡排序和选择排序。冒泡反复比较相邻元素把大的往后浮选择每次扫描剩下的元素挑出最小的往前放。它们的共同点是循环嵌套很深移动次数多适合数据量很小的情况。第二种思路是“局部有序的扩展”代表是插入排序和希尔排序。插入排序像整理扑克牌把新元素插到前面已排序的序列里希尔排序是插入排序的改进版先把间隔较大的元素排好再逐步缩小间隔。第三种思路是“分而治之”代表是归并排序和快速排序。归并先拆成两半分别排好再合并快排选一个基准值把小于基准和大于基准的元素分到两侧再对两侧递归排序。这也是工程中最常用的两类。第四种思路只有堆排序一个它把数组当成一棵完全二叉树通过堆化操作反复取出最大值放到末尾。理解了这四个思路你会发现排序算法的学习复杂度瞬间降低了一大半。2. 七种排序逐个手写拆解附完整可运行代码2.1 冒泡排序把最大的数“浮”到最后冒泡排序的思路最直观从头开始比较相邻两个元素如果前一个比后一个大就交换它们。一趟结束后最大的数一定被交换到了数组末尾。重复 n-1 趟数组就排好了。def bubble_sort(arr): n len(arr) for i in range(n - 1): swapped False for j in range(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这段代码里有个很容易忽略的优化swapped标志位。如果某一趟没有任何交换发生说明数组已经有序直接跳出循环。最好情况下数据本来就有序冒泡排序的时间复杂度可以降到 O(n)这是很多人没意识到的。我实测过1 万条乱序数据冒泡排序要跑 0.3 秒左右看着不多但到 10 万条就直接膨胀到 30 秒。所以冒泡只适合教学演示和数据量极小比如几百条的场景。真要在项目里用它记得加上提前退出优化。2.2 选择排序每次挑最小的放前面选择排序的思路上手更简单第 i 趟在未排序区域 [i, n-1] 里找到最小元素的下标然后和位置 i 的元素交换。每趟确定一个元素的最终位置。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选择排序有个特点它的交换次数是最少的最多只交换 n-1 次。如果交换元素的代价远高于比较比如元素是超大对象选择排序反而比冒泡更合适。但它的比较次数固定是 O(n^2)无论数据是否有序都改变不了这是它的硬伤。再提一个很多人忽略的点选择排序是不稳定的。比如数组 [5, 5a, 2]第一轮找到最小值 2 和第一个 5 交换两个 5 的相对顺序就变了。后面讲稳定性时我还会详细展开。2.3 插入排序像整理扑克牌一样插进去插入排序的思路和人类整理扑克牌几乎一样从第二个元素开始把它插入到前面已经排好序的子序列中的正确位置。在子序列里比它大的元素逐个后移腾出位置。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 循环几乎不走或走很少几步时间复杂度逼近 O(n)。这也是希尔排序、以及上面提到的 TimSort 这类混合排序会拿它当收尾工具的原因。这里有个细节值得注意我每次先用key保存当前元素再用“整体后移”的方式腾位置。这比“每次都做相邻交换”少了很多次赋值操作常数因子更小。同样的思路在归并、快排中也适用。2.4 希尔排序插入排序的高效改良版希尔排序很多人学完就忘因为它更像是一个“思路里程碑”工程里反而不太直接用。它做的事情是先让数组中任意间隔为 gap 的元素有序然后不断缩小 gap最后当 gap1 时相当于做一次插入排序。def shell_sort(arr): n len(arr) gap n // 2 while gap 0: for i in range(gap, n): key arr[i] j i - gap while j 0 and arr[j] key: arr[j gap] arr[j] j - gap arr[j gap] key gap // 2 return arr希尔排序的精髓在于大间隔的排序让数组迅速“接近有序”这样最后一次插入排序的移动量大大减少。增量序列的选择会直接影响性能我这里用的是最简单的折半递减业内还有 Hibbard 序列、Sedgewick 序列等能把最坏复杂度压到 O(n^(4/3)) 甚至更低。它比普通插入排序快得多但比 O(n log n) 级别算法慢而且不稳定。我的观点是理解它的思想即可真正要稳定高效时工程上会用更成熟的方案。2.5 归并排序典型的分治和合并归并排序的思路很“分治”把数组一分为二分别递归排序再把两个有序数组合并成一个有序数组。递归的终止条件是子数组长度为 1 或 0。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): result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: result.append(left[i]) i 1 else: result.append(right[j]) j 1 result.extend(left[i:]) result.extend(right[j:]) return result归并排序最让人安心的地方在于无论数据是什么状态它都是 O(n log n) 的复杂度非常稳定、可预测。代价是每次合并都要额外申请数组空间空间复杂度是 O(n)。实际操作中要注意一个细节频繁地left merge_sort(arr[:mid])会创建大量子数组切片内存和时间都比较浪费。工程实现里通常传入left、right下标作为区间参数在一个临时数组上做合并最后拷贝回去。这份代码为了教学可读性用了切片性能并非最优。2.6 快速排序工程应用最广的排序快速排序也是分治思想但策略和归并相反归并“先拆分、再合并”合并时才做主要工作快排是先选定一个 pivot基准值把数组划分成“小于等于基准”和“大于基准”两部分然后递归处理左右两侧。def quick_sort(arr, low0, highNone): if high is None: high len(arr) - 1 if low high: p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high) return arr def partition(arr, low, high): 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] return i 1这里用的是 Lomuto 分区方案易懂但偏慢。另一种 Hoare 分区方案交换次数更少实际性能更好但边界条件更绕新手容易写错。快排的平均复杂度是 O(n log n)但最坏情况每次 pivot 都是最大/最小值比如对有序数组固定取末尾会退化到 O(n^2)。工程上的对策有三招随机选择 pivot、三数取中、在递归小区间时切换插入排序。为什么快排实际跑得比堆排序、归并排序快关键在缓存友好性。快排分区时访问数组的顺序是线性的局部性高而堆排序的 heapify 在数组中跳来跳去缓存命中率低。理解了这一点才能真正理解为什么大家都吹快排。2.7 堆排序用“最大堆”原地完成排序堆排序的思路是先把数组调整成最大堆父节点总大于等于子节点这样堆顶就是全局最大值。把堆顶和末尾元素交换最大值就排到了最后。接着缩小堆范围重新堆化剩余元素再取次大值循环 n-1 次。def heap_sort(arr): n len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[0], arr[i] arr[i], arr[0] heapify(arr, i, 0) return arr def heapify(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] heapify(arr, n, largest)堆排序最突出的优点有两个最坏复杂度是 O(n log n)且是原地排序空间复杂度 O(1)。在最坏情况下它比快排稳定得多。但它的缺点也很明显不稳定、缓存不友好、实际常数因子较大。所以在通用排序场景里堆排序通常不是首选它真正的价值在于“不需要完全排序只要最大/最小几个值”的场景比如 TopK 问题、优先队列。写堆排序最易错的地方是heapify里的边界条件左右子节点的下标是否越界以及递归出口是否写对一次写对的人真的不多。3. 排序算法对比与场景选型一张表搞定3.1 复杂度、稳定性、空间占用速查表把七种排序的关键属性放在一张表里是复习时最有用的总结方式排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性冒泡排序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)稳定希尔排序O(n log n) 到 O(n^(4/3))O(n^2)O(n)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n^2)O(n log n)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定这张表值得反复看。我面试别人时最常问的一个问题是“为什么插入排序的最好情况是 O(n)而选择排序不是”能答出“内层循环是否受有序性影响”的人基本都是真的理解过。3.2 稳定性是什么为什么数据排序时要关心稳定性听起来抽象其实一句话就能讲明白如果两个元素值相等排序后它们的先后顺序没有变那这个排序就是稳定的。举个例子一个成绩表先按总分排序再按学号排序。如果排序算法是稳定的第二次按学号排序后学号相同的学生仍然保持着总分从高到低的排列。如果第二次用了不稳定排序原来的总分顺序就被打乱了。这种“多关键字排序”在实际业务里极其常见很多人没意识到为什么语言内置排序大多是稳定的就是因为它能在一个排序中保留另一个排序的结果。七种排序里稳定的是冒泡、插入、归并不稳定的是选择、希尔、快排、堆。其中选择排序的不稳定原因我在前面用 [5, 5a, 2] 举例了快排不稳定则是因为 partition 过程中会跨越式交换元素。理解“为什么会不稳定”比死记结论靠谱得多。3.3 实际业务到底选哪个工程中的选型经验我按场景拆开说数据量小几十到几百条直接选插入排序。代码简单常数因子小接近有序时性能接近 O(n)。很多语言的排序库在区间小于某个阈值时会从快排切成插入排序。数据量大、内存充足、要求稳定选归并排序。它的 O(n log n) 是可预测的且稳定。Java 的Arrays.sort对对象数组就用了稳定归并排序。数据量大、内存紧张、不要求稳定选快速排序。原地排序缓存友好平均性能最好。但记得对 pivot 做随机化或三数取中来避免最坏情况。数据接近有序插入排序表现惊人几乎接近 O(n)。只需要前 K 个最大或最小值别排序用堆。维护一个大小为 K 的小顶堆时间复杂度是 O(n log K)比全局排序划算得多。选错排序的代价我见过最夸张的一次是有人对 500 万条数据跑冒泡排序跑了半个多小时没出结果。换成快排后一秒内完成。这个对比不是夸张是实实在在的典型案例。4. 排序实现中常见的坑与排查心得4.1 死循环与下标越界边界条件调试的 3 个经验排序代码写错最常见的问题就是死循环和下标越界而且往往发生在边界条件上。我自己踩过的坑和排查经验整理如下第一递归结束条件必须包含“只剩下一个元素”的情况。比如快排里if low high才继续递归少了这个判断就会无限递归直到栈溢出。归并排序里if len(arr) 1: return arr也是同样的作用。第二partition 的遍历范围别多走一步。Lomuto 分区里for j in range(low, high)遍历到high-1就停最后再单独交换 pivot。如果把high也算进去pivot 会被自己和别人交换至少一次结果直接错乱。第三堆排序的 heapify 要有越界判断。每次访问arr[left]、arr[right]之前必须先确认left n、right n。我见过很多人写堆排序堆化函数里漏了越界判断小数组没事大数组随机崩。排查这类问题时我推荐一个技巧先把数组长度缩到 3 到 5手动模拟一遍打印每一轮的数组状态。排序类 bug 用这个办法基本都能快速定位。4.2 快排最坏情况当“有序数组”遇到“固定取尾”快排最容易被问到的坑就是对一个已经排好序的数组用固定取最后一个元素作为 pivot 的写法复杂度直接退化成 O(n^2)。原因是每次分区都只能分出“一个元素 其余所有元素”递归深度变成 n等于冒泡排序的复杂度。我自己实际测试过10 万条升序数据固定取尾的快速排序跑了 4 秒多而随机取 pivot 的版本只用了不到 0.1 秒。这个差距在真实业务里是不能接受的。解决方案有三个层次最简单的是随机选 pivot从random.randint(low, high)取一个下标与high位置的元素交换后再分区更工程化的是三数取中取 low、mid、high 三个位置的中位数作为 pivot最稳妥的是像许多标准库那样在递归区间缩小到一定阈值时切换到插入排序。能把这套优化讲明白面试官对你的认可度会高很多。4.3 性能实测小规模数据真不是越快越好我把七种排序在同样的 1000 条随机数据上跑过一遍结果很有意思插入排序用了 0.002 秒希尔排序 0.001 秒归并、快排、堆排序也都在 0.001 秒左右冒泡和选择要慢一些但差距其实不算夸张。但数据量一放大到 5 万条差距就出来了冒泡排序接近 7 秒选择排序 4 秒多插入排序 1 秒多而归并排序只要 0.04 秒左右快排 0.03 秒左右堆排序 0.05 秒左右希尔排序 0.1 秒左右。这个结果很直观地说明了一个道理在数据量很小时常数因子比时间复杂度重要数据量一大复杂度等级直接决定生死。我个人在维护一个内部数据清洗工具时就吃过这个亏。最初为了“代码简单”用了冒泡排序数据只有几千条还行后来业务量涨到几十万条直接卡成瓶颈。换成快排后同样的任务秒级完成。从那以后我写任何带排序的代码都会先问一句“这份数据以后会长多大”排序算法这个主题表面上是“背代码”实际上是在训练一种计算思维怎么评价方案、怎么处理边界、怎么在多个约束之间做取舍。把这七种排序吃透了你对复杂度分析、递归思想、数据结构这些基础能力的理解也会跟着上一个台阶。本文还有配套的精品资源点击获取