企业官网建设流程全解析

简介：面向算法初学者、备考者及编程开发者的排序算法学习资料，系统梳理了七种基于比较的排序算法：选择排序、插入排序、归并排序、快速排序、堆排序、冒泡排序与希尔排序。内容涵盖每种算法的核心思想、执行步骤、时间复杂度与稳定性分析，并结合 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，最后当 gap=1 时，相当于做一次插入排序。

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, low=0, high=None): 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)，而选择排序不是？”能答出“内层循环是否受有序性影响”的人，基本都是真的理解过。

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 秒左右。这个结果很直观地说明了一个道理：在数据量很小时，常数因子比时间复杂度重要；数据量一大，复杂度等级直接决定生死。

我个人在维护一个内部数据清洗工具时，就吃过这个亏。最初为了“代码简单”用了冒泡排序，数据只有几千条还行，后来业务量涨到几十万条，直接卡成瓶颈。换成快排后，同样的任务秒级完成。从那以后，我写任何带排序的代码都会先问一句：“这份数据以后会长多大？”

排序算法这个主题，表面上是“背代码”，实际上是在训练一种计算思维：怎么评价方案、怎么处理边界、怎么在多个约束之间做取舍。把这七种排序吃透了，你对复杂度分析、递归思想、数据结构这些基础能力的理解也会跟着上一个台阶。

本文还有配套的精品资源，点击获取