作为一个常年跟数据结构和算法打交道的开发者，我越来越觉得排序算法不只是一堆需要背下来的代码模板，它背后是一整套关于"怎么高效地整理数据"的思考方式。很多人学排序时容易陷入一种误区：看视频觉得懂了，合上书全忘了，再看到代码又觉得似曾相识。根本原因在于，大多数教程只讲了"怎么实现"，没讲"为什么这样设计"。这篇是十大排序算法系列的第一篇，先把最常用的五种——冒泡排序、选择排序、插入排序、快速排序、希尔排序一次讲透，不仅给出多语言实现，还会把每种算法的设计动机、复杂度成因、稳定性来源以及实战中的踩坑点都拆开讲明白。无论你是刚接触算法的初学者，还是准备面试想系统复习的开发者，这篇都能给你提供一个足够清晰的坐标系。
我见过太多人面试时手写快排翻车，也见过有人在小数据集上用冒泡排到怀疑人生。归根结底，排序算法是数据结构与算法中最基础也最能体现"思路差异"的内容。同一个排序需求，五种算法走了五条完全不同的路，有的靠反复交换，有的靠挑选最值，有的靠逐张插入，有的靠大步跳跃，有的靠分而治之。把这些差异理解透，远比背下十种写法更有价值。
1. 冒泡排序：最直观的交换思想与两处关键优化
1.1 核心原理：为什么叫"冒泡"
冒泡排序是所有排序算法里最容易理解的一个，也是很多人编程生涯写出的第一个排序。它的思路翻译成人话就是：从头到尾，两两比较相邻元素，顺序不对就交换。这样每一轮结束时，当前未排序部分里最大的那个数，就像气泡一样慢慢"浮"到了数组末尾。
这个比喻虽然老套，但非常准确。你可以想象一个水池底部有一堆大小不一的石头，大气泡上升得快，一路上不断和旁边的小气泡交换位置，最后到达水面。数组里每轮冒泡，就是让当前范围内的最大值走到它该待的位置。
没排序的数组区域会逐轮收缩。第一轮结束后，数组最后一个元素一定是全局最大值，第二轮就不用再管它了。这就是为什么内层循环的边界是j < n - 1 - i，i代表已经完成冒泡的轮数，同时也是已经"沉底"的元素个数。
很多人第一次写冒泡时容易把外层循环写成for (int i = 0; i < n; i++)，内层写成for (int j = 0; j < n - 1; j++)，逻辑上也能排出结果，但做了大量无用比较。外层只需要跑n-1轮：当n-1个元素都到了正确位置，剩下的那一个自然也就位了。
1.2 多语言实现与逐行解读
C++实现如下：
void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { // 内层循环每轮缩短：后面 i 个元素已经有序 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); } } } }Python版本更简洁，适合快速理解：
def bubble_sort(arr): n = len(arr) for i in range(n - 1): for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j]Java和C语言的写法几乎一样，只是数组获取长度的方式不同。核心逻辑完全一致：双重循环，内层做比较和交换。边界条件是这段代码里唯一的陷阱，n-1-i少写一个-1就会导致数组越界，因为内层要访问arr[j+1]。
1.3 优化：提前终止与鸡尾酒排序
纯基础的冒泡有个显而易见的问题：如果数组本来就有序，它依然会傻乎乎地跑完所有轮次。解决办法是加一个交换标志：
void bubbleSortOptimized(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; } } // 一整轮没有任何交换，说明已经有序 if (!swapped) break; } }加了这段之后，最坏情况（完全逆序）依然是O(n²)，但最好情况从O(n²)直接降到了O(n)。对已经有序的数组，第一轮扫完发现没交换就退出了，只做了n-1次比较。
还有一个进阶变体叫鸡尾酒排序，也叫定向冒泡排序。它每轮先从左到右把最大值送到末尾，再从右到左把最小值送到开头。在大部分元素已经有序、只有少数元素位置错乱的场景下，能明显减少轮数。不过日常开发中冒泡本身用得就少，这个变体更多是用来开拓思路。
冒泡排序是稳定的排序算法。因为相邻元素只有在前一个大于后一个时才交换，相等的元素不会互相跨越，所以相对顺序得以保留。
我自己的习惯是，把冒泡当作一种"热身运动"。写它不是为了用它，而是为了理解"交换排序"这个家族的基本盘——每一轮通过交换让一个元素归位。后面学快速排序时你会发现，快排在本质上也是交换排序，只是它交换的效率高得多。
2. 选择排序：最"省心"的排序逻辑与代价分析
2.1 思路拆解：每轮锁定一个最小值
选择排序的思路比冒泡更直白：把数组看成两部分，左边是已排好序的区域，右边是待排序区域。每一轮扫描待排序区域，找出最小的元素，把它和待排序区域的第一个元素交换。下一轮，这个元素就归入已排序区了。重复这个过程，直到全部归位。
这就好比剥洋葱，一层层地剥，每次剥出来的都是当前最小的那个。冒泡排序是"边走边换"，一路上遇到逆序就换，换了很多次才把一个元素送到位置；选择排序是"先看后换"，每轮只交换一次，直接把这个范围内的最小值放到它最终的归宿。
如果说冒泡像气泡不断上浮，那选择就像"挑苹果"。一堆苹果里先挑出最大的放到篮子里，再从剩下的里面挑最大，如此反复，最终整堆苹果按大小排列好。
2.2 代码实现与复杂度特征
C++实现：
void selectionSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { int minIdx = i; // 在未排序区间找最小元素的下标 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } // 把找到的最小元素放到未排序区首位 if (minIdx != i) { swap(arr[i], arr[minIdx]); } } }有一个细节值得注意：选择排序的比较次数是固定的，不管输入数据是有序、无序还是完全逆序，内层比较次数永远是n(n-1)/2。这意味着它的时间复杂度稳定在O(n²)，没有最好最坏之分。
拿数据量来感受一下：对10万个元素排序，选择排序需要执行大约50亿次比较。这个数字在今天的机器上虽然没有夸张到跑不完，但也已经能明显感受到卡顿。而快速排序处理同样规模的数据，比较次数的量级在百万级别，差距是两到三个数量级。
2.3 为什么选择排序的交换次数最少
选择排序有一个冷门但重要的特性：它是所有排序算法中交换次数最少的之一，最多只需要n-1次交换。因为每轮最多交换一次，而总共只有n-1轮。
这个特性在特定场景下非常值钱。有些存储介质的写入寿命有限，比如EEPROM、Flash，频繁写入会加速磨损。如果输入数据存储在这样介质上，排序时尽量减少"写"操作就成了一等大事。这时候选择排序的交换次数优势就体现出来了——比较随便做，不耗寿命，但交换涉及写入，能省则省。
不过选择排序是不稳定的。举个例子，数组[5a, 5b, 3]，第一轮扫描发现最小值是3，直接把它和第一个5a交换，结果变成[3, 5b, 5a]。本来5a在5b前面，排序后5a跑到了5b后面，两个相等元素的相对顺序被打破了。
这是选择排序最容易被面试官追问的点。很多人会混淆"稳定"和"排序正确"这两个概念——不稳定不代表排序结果错误，只是相等元素的原始先后顺序无法保留。但在某些业务场景中，比如先按时间排再按优先级排，稳定性就非常关键。所以这个特性必须记得清楚。
3. 插入排序：像整理扑克牌一样，以及它的隐藏价值
3.1 基本思想：新牌插入有序区
打过扑克的人都会有一种肌肉记忆：摸到一张新牌后，会在手里已经排好序的牌中找个合适位置把它插进去。插入排序就是这个过程的程序化表达。
在数组层面，插入排序把前i个元素看成已经排好序的"左手牌"，第i+1个元素是刚摸上来的"新牌"。操作分两步：先从右往左在一手牌里找插入位置，然后把牌插入。在数组中，插入意味着把比新牌大的元素逐个右移一格，腾出位置。
移动和交换的区别很关键。交换一次需要三次赋值，而移动只需要一次赋值。插入排序在"找位置"的过程中用的是移动，而不是交换，这个细节让它在数据移动次数上比冒泡少得多。
3.2 代码实现与边界条件
void insertionSort(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // 从右往左找插入位置，同时把较大元素右移 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }Python版本：
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key这里有个新手特别容易错的地方：while条件里必须先判断j >= 0，再去访问arr[j]。如果顺序反了，当j变成-1时程序会尝试访问arr[-1]，这在某些语言里是隐秘的逻辑错误，在另一些语言里直接越界崩溃。
3.3 近乎有序数据的杀手锏
插入排序最迷人的地方在于：面对近乎有序的数据时，它的效率接近O(n)。因为内层while循环可能根本进不去，或者只移动一两次就找到位置了。最极端的情况——数组已经完全有序——每一轮只需要做一次比较，然后直接结束，总比较次数是n-1，线性时间。
这个特性不是无关紧要的"理论上限"。现实世界里有大量数据天然是"近似有序"的。比如一个按时间追加日志的数组，只有偶尔几条数据乱序；一个基本排好序的名单，偶尔新增了几条记录。在这些场景中插入排序的表现异常优秀。
很多高级排序算法正是看中了这一点。你经常能在工程代码里看到一个混合策略：当递归处理的子数组规模足够小时，不再继续递归，而是改用插入排序处理这个"小碎片"。因为小规模数组的常数开销小，插入排序的性能往往比继续递归分裂更快。
3.4 为什么说插入排序是高级排序的"地基"
以C++标准库的std::sort为例，它的核心实现是内省排序（introsort），主体是快速排序，但当递归深度过深时会切换到堆排序，而在处理元素个数少于某个阈值（通常是16或32）的子数组时，又会退化成插入排序。Python的TimSort同样大量依赖插入排序来处理短片段。
插入排序在最优情况下是O(n)，这是它最大的本钱。其他排序算法要么是O(n log n)——做不到线性；要么是O(n²)但常数很大——碎片场景下拼不过插入。所以它既是独立的排序方案，又是其他排序算法补强短板的关键零件。
它的稳定性也让它在实际工程中很受欢迎。相等元素的顺序不会被打乱，这在需要多关键字排序的场景中是刚需。
我把插入排序看作"低配却不低级"的典型。它的思路简单到可以口述，但把它放进高级排序里去做局部优化，效果立竿见影。学排序如果只能真正吃透一个算法，我会推荐优先吃透插入排序，因为它是理解后续希尔排序、TimSort这些复杂算法的基础。
4. 希尔排序：插入排序的"跨步"升级与增量序列选择
4.1 从gap到分组插入：一次移动多步
插入排序有一个天生短板：它一次只能把元素移动一格。假设最小的元素在数组最末尾，而它应该去的位置是数组开头，那插入排序需要慢慢把它往前挪n-1次。对逆序数组来说，这代价太沉重了。
希尔排序的思路是"先宏观后微观"。既然一次移动一格太慢，那就先跳着移动，让元素在一次操作中跨越一大段距离。具体做法是引入一个增量gap，把数组中相隔gap个位置的元素看作一组，组内做插入排序。然后不断缩小gap，直到gap=1，此时整个数组做一次标准的插入排序。
gap=1的那一轮至关重要，它保证了排序的完备性。之前的每一轮，不管分组怎么排，都不能保证全局有序，只能保证"宏观上越来越接近有序"。等gap缩到1，插入排序面对的是一个已经大体有序的数组，效率很高。
4.2 代码实现与增量序列的讲究
void shellSort(vector<int>& arr) { int n = arr.size(); // 从 n/2 开始，每次折半，直到 gap=1 for (int gap = n / 2; gap > 0; gap /= 2) { // 对每个分组做插入排序 for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }gap从n/2开始逐步减半是最常见的写法，实现简单，但性能并非最优。按这个序列，最坏情况依然是O(n²)。工程上讨论希尔排序时，重点往往落在"用哪种增量序列"上。
常见序列有三种：
| 增量序列 | 递推方式 | 最坏时间复杂度 |
|---|---|---|
| 希尔原始序列 | gap = n/2, n/4, ... 1 | O(n²) |
| Hibbard序列 | 2^k - 1 | O(n^(3/2)) |
| Sedgewick序列 | 4^k + 3×2^(k-1) + 1 | O(n^(4/3)) |
增量序列的选择直接决定希尔排序的上限。同一个数组，用希尔原始序列可能跑得比插入排序还慢，但换Sedgewick序列后明显好转。如果你在项目中手写希尔排序，优先考虑Sedgewick序列或至少用Hibbard序列，别用朴素折半。
4.3 希尔排序的不稳定性来源
希尔排序是不稳定的。原因在于分组操作会把原本相邻的相等元素拆散到不同组内，组内排序时它们可能发生跨越式移动，导致相对顺序改变。
举个具体例子。数组初始为[6a, 5, 6b, 4, 1]，取gap=3。分组情况是：
- 组1：位置0、3、4，元素为6a、4、1
- 组2：位置1、2，元素为5、6b
组1内做插入排序后，位置0、3、4上的元素变为1、4、6a。此时整个数组变成[1, 5, 6b, 4, 6a]。原本6a在6b前面，现在6b跑到了6a前面，相等元素的相对顺序被打破了。
这个例子也清楚地展示了希尔排序"跨步移动"的本质——元素从位置0直接跳到了位置4，一步跨越了四个位置，这正是它比插入排序快的原因，也是它丧失稳定性的原因。速度和稳定往往是鱼与熊掌。
希尔排序适合中等规模数据、内存极度受限的嵌入式场景。它的空间复杂度是O(1)，不需要额外的数组；算法本身不涉及递归，不存在递归栈溢出的风险；代码短，容易移植到C语言或汇编环境。在单片机、微控制器这类资源紧张的环境中，O(n²)级别的算法可能太慢，完整的快排又太重，希尔排序往往是一个平衡点很好的选择。
5. 快速排序：分治思想的极致体现与pivot选法
5.1 分区逻辑：Lomuto与Hoare
快速排序是教科书级别的高效算法，也是工程实践中最常用的排序算法之一。它的核心只有三步：选一个基准值pivot，把数组分成"小于pivot"和"大于pivot"两个区域，然后递归对两个区域分别重复这个过程。
每次分区操作完成后，pivot都会落到它最终该待的位置上。左边全是比它小的，右边全是比它大的。这个"一锤定音"的特性，让快速排序平均只需要O(n log n)次比较。
分区有两大经典实现。Lomuto分区法逻辑简单，适合教学和快速书写，思路是维护一个"较小元素区间的右边界"指针i，用另一个指针j扫描整个数组，发现比pivot小的元素就把i右移一位然后把新元素换过来。
对比之下，Hoare分区法用两个指针从数组两头向内逼近：左指针找比pivot大的，右指针找比pivot小的，找到就交换。Hoare分区法平均交换次数更少，但实现细节容易出错，循环结束条件和左右指针的交叉判断都需要谨慎处理，新手手写时经常在这里写崩。
5.2 快排的代码实现
Lomuto分区版本的C++实现：
int partition(vector<int>& arr, int low, int high) { // 这里选最后一个元素作为 pivot int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } } // pivot 归位 swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); // 递归处理左右两个子区间 quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }Python版本：
def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[-1] left = [x for x in arr[:-1] if x <= pivot] right = [x for x in arr[:-1] if x > pivot] return quick_sort(left) + [pivot] + quick_sort(right)Python这个版本虽然简洁好懂，但空间效率差，每轮递归都会创建新数组，属于教学简化版。要真正追求性能，还是要像C++版那样做原地分区。
5.3 pivot选法与退化陷阱
快排最怕什么？最怕分区极不平衡。理想情况是每轮都把数组分成两半，递归深度log n。但如果pivot选得糟糕，比如每次都选到最大值或最小值，那分区结果就是一边0个元素，另一边n-1个元素，递归深度变成n，时间复杂度退化成O(n²)。
最典型的退化场景是：数组本身已经有序，pivot固定取最后一个元素。第一轮分区，pivot是最大值，左边有n-1个元素，右边0个；第二轮又是这样，一直沿着一条很深的递归链走下去。对10万、100万这种规模的有序数组，递归深度会直接爆掉调用栈。
解决办法有两个方向。方向一是随机选pivot，用随机性规避"数据恰好让pivot每次都最坏"的情况，从概率上保证期望时间复杂度接近O(n log n)。方向二是三数取中法，取数组首位、中间位、末位三个元素的中位数作为pivot。三数取中在数据近乎有序时效果非常好，能有效规避常见的退化场景，是工程中最常见的选法。
手写快排时，如果你只写一个固定选最后一个元素的版本，面试官大概率会追问这个退化问题。这个追问不是刁难，而是考察是否理解算法背后的边界条件。
5.4 工程中的快排优化：从快排到内省排序
工业级排序库很少直接用裸快排。C++标准库的std::sort采用的是内省排序，本质是快排的"加强版"，它额外加了两道保险：
第一道保险是递归深度检查。算法跟踪当前递归深度，如果深度超过2×log n就切换为堆排序，用堆排序稳定的O(n log n)保底性能来防止快排退化。
第二道保险是小数组回退。当递归处理的子数组长度小于16或32时，停止递归，改用插入排序。这个过程就是前面提到过的——利用插入排序在"小规模 + 近乎有序"场景下的线性效率，避免递归带来的函数调用开销。
C库里的qsort虽然底层实现不同，但思路一脉相承，也是快排加各种防退化策略的组合。所以你在项目里直接用库函数就可以获得接近最优的性能，手写快排更多是学习意义和面试意义。
快排像武侠小说里的"七伤拳"：用得好所向披靡，用不好伤及自身。理解它的分区逻辑、pivot选法和退化条件，才算真正掌握了这套拳法。
6. 五种排序横向对比与选型参考
6.1 核心指标对照表
把五种排序的关键指标集中在一张表里，随时可以对照查阅：
| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n) | O(n²) | O(1) | 稳定 |
| 希尔排序 | 取决于增量序列 | O(n log n)左右 | 取决于增量序列 | O(1) | 不稳定 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 |
这张表值得花时间仔细琢磨。有几个细节容易被忽略：
冒泡和插入的最好情况都是O(n)，因为它们都能检测到"数组已经有序"并提前结束。选择排序则不行，它无论如何都要做满n(n-1)/2次比较。
希尔排序和快速排序都是不稳定的。只有冒泡和插入是稳定的，而这两者又都是O(n²)级别的算法。所以在需要稳定排序且数据规模较大时，通常考虑归并排序——那是系列下一篇的主角。
6.2 实战选型：什么时候用哪个
结合多年的实际经验，我给出一套比较务实的选型建议，按场景划分比按算法名气划分要靠谱得多：
数据量很小（几十到几百），代码简单排在第一位时，用插入排序。它的实现简短，不会出错，在近乎有序的数据上表现又特别好。很多系统自带的排序函数内部对小规模片段也是这么处理的。
数据在嵌入式、单片机等内存极小的环境，且数据量属于中等规模，用希尔排序。它不需要额外的数组空间，不递归，代码可控性强，在内存寸土寸金的环境里是兼顾性能与资源的好方案。
数据规模大，追求综合性能，直接用系统库的sort或qsort。它们底层已经实现了快排、堆排、插入排序的混合策略，普通开发者自己手写快排很难超过库函数的工程优化水平。手写快排主要用于理解原理和面试场景。
对写操作成本极端敏感的场景，比如持久化存储介质排序，不妨用选择排序。它每轮只交换一次，整体交换次数只有n-1次，在写耗尽型存储介质时是最安全的选择。
如果业务上要求稳定排序且数据规模较大，这五种里没有合适答案，请直接选择归并排序。这也是我为什么一直强调"十大排序算法"要当成一个整体来学——每种算法都有它的生态位，单摆在一个维度上比高低没有意义。
我在实际项目中见过太多"拿着锤子看什么都是钉子"的案例。一排序就上快排，完全不管数据规模和数据特征。其实选择排序在写密集型场景的价值、插入排序在近乎有序数据上的效率、希尔排序在嵌入式环境里的实用性，都值得在合适的场合被想起来。排序算法的价值不在名字本身，而在你能不能为当前的问题挑到最合适的那个方案。这也是我写这系列文章最想传达的东西。
