作为一个常年跟数据结构和算法打交道的开发者我越来越觉得排序算法不只是一堆需要背下来的代码模板它背后是一整套关于怎么高效地整理数据的思考方式。很多人学排序时容易陷入一种误区看视频觉得懂了合上书全忘了再看到代码又觉得似曾相识。根本原因在于大多数教程只讲了怎么实现没讲为什么这样设计。这篇是十大排序算法系列的第一篇先把最常用的五种——冒泡排序、选择排序、插入排序、快速排序、希尔排序一次讲透不仅给出多语言实现还会把每种算法的设计动机、复杂度成因、稳定性来源以及实战中的踩坑点都拆开讲明白。无论你是刚接触算法的初学者还是准备面试想系统复习的开发者这篇都能给你提供一个足够清晰的坐标系。我见过太多人面试时手写快排翻车也见过有人在小数据集上用冒泡排到怀疑人生。归根结底排序算法是数据结构与算法中最基础也最能体现思路差异的内容。同一个排序需求五种算法走了五条完全不同的路有的靠反复交换有的靠挑选最值有的靠逐张插入有的靠大步跳跃有的靠分而治之。把这些差异理解透远比背下十种写法更有价值。1. 冒泡排序最直观的交换思想与两处关键优化1.1 核心原理为什么叫冒泡冒泡排序是所有排序算法里最容易理解的一个也是很多人编程生涯写出的第一个排序。它的思路翻译成人话就是从头到尾两两比较相邻元素顺序不对就交换。这样每一轮结束时当前未排序部分里最大的那个数就像气泡一样慢慢浮到了数组末尾。这个比喻虽然老套但非常准确。你可以想象一个水池底部有一堆大小不一的石头大气泡上升得快一路上不断和旁边的小气泡交换位置最后到达水面。数组里每轮冒泡就是让当前范围内的最大值走到它该待的位置。没排序的数组区域会逐轮收缩。第一轮结束后数组最后一个元素一定是全局最大值第二轮就不用再管它了。这就是为什么内层循环的边界是j n - 1 - ii代表已经完成冒泡的轮数同时也是已经沉底的元素个数。很多人第一次写冒泡时容易把外层循环写成for (int i 0; i n; i)内层写成for (int j 0; j n - 1; j)逻辑上也能排出结果但做了大量无用比较。外层只需要跑n-1轮当n-1个元素都到了正确位置剩下的那一个自然也就位了。1.2 多语言实现与逐行解读C实现如下void bubbleSort(vectorint 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[j1]。1.3 优化提前终止与鸡尾酒排序纯基础的冒泡有个显而易见的问题如果数组本来就有序它依然会傻乎乎地跑完所有轮次。解决办法是加一个交换标志void bubbleSortOptimized(vectorint 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(vectorint 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个元素看成已经排好序的左手牌第i1个元素是刚摸上来的新牌。操作分两步先从右往左在一手牌里找插入位置然后把牌插入。在数组中插入意味着把比新牌大的元素逐个右移一格腾出位置。移动和交换的区别很关键。交换一次需要三次赋值而移动只需要一次赋值。插入排序在找位置的过程中用的是移动而不是交换这个细节让它在数据移动次数上比冒泡少得多。3.2 代码实现与边界条件void insertionSort(vectorint 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直到gap1此时整个数组做一次标准的插入排序。gap1的那一轮至关重要它保证了排序的完备性。之前的每一轮不管分组怎么排都不能保证全局有序只能保证宏观上越来越接近有序。等gap缩到1插入排序面对的是一个已经大体有序的数组效率很高。4.2 代码实现与增量序列的讲究void shellSort(vectorint arr) { int n arr.size(); // 从 n/2 开始每次折半直到 gap1 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, ... 1O(n²)Hibbard序列2^k - 1O(n^(3/2))Sedgewick序列4^k 3×2^(k-1) 1O(n^(4/3))增量序列的选择直接决定希尔排序的上限。同一个数组用希尔原始序列可能跑得比插入排序还慢但换Sedgewick序列后明显好转。如果你在项目中手写希尔排序优先考虑Sedgewick序列或至少用Hibbard序列别用朴素折半。4.3 希尔排序的不稳定性来源希尔排序是不稳定的。原因在于分组操作会把原本相邻的相等元素拆散到不同组内组内排序时它们可能发生跨越式移动导致相对顺序改变。举个具体例子。数组初始为[6a, 5, 6b, 4, 1]取gap3。分组情况是组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(vectorint 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(vectorint 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次在写耗尽型存储介质时是最安全的选择。如果业务上要求稳定排序且数据规模较大这五种里没有合适答案请直接选择归并排序。这也是我为什么一直强调十大排序算法要当成一个整体来学——每种算法都有它的生态位单摆在一个维度上比高低没有意义。我在实际项目中见过太多拿着锤子看什么都是钉子的案例。一排序就上快排完全不管数据规模和数据特征。其实选择排序在写密集型场景的价值、插入排序在近乎有序数据上的效率、希尔排序在嵌入式环境里的实用性都值得在合适的场合被想起来。排序算法的价值不在名字本身而在你能不能为当前的问题挑到最合适的那个方案。这也是我写这系列文章最想传达的东西。
精讲五大排序算法：冒泡、选择、插入、希尔与快排的原理与实战
作为一个常年跟数据结构和算法打交道的开发者我越来越觉得排序算法不只是一堆需要背下来的代码模板它背后是一整套关于怎么高效地整理数据的思考方式。很多人学排序时容易陷入一种误区看视频觉得懂了合上书全忘了再看到代码又觉得似曾相识。根本原因在于大多数教程只讲了怎么实现没讲为什么这样设计。这篇是十大排序算法系列的第一篇先把最常用的五种——冒泡排序、选择排序、插入排序、快速排序、希尔排序一次讲透不仅给出多语言实现还会把每种算法的设计动机、复杂度成因、稳定性来源以及实战中的踩坑点都拆开讲明白。无论你是刚接触算法的初学者还是准备面试想系统复习的开发者这篇都能给你提供一个足够清晰的坐标系。我见过太多人面试时手写快排翻车也见过有人在小数据集上用冒泡排到怀疑人生。归根结底排序算法是数据结构与算法中最基础也最能体现思路差异的内容。同一个排序需求五种算法走了五条完全不同的路有的靠反复交换有的靠挑选最值有的靠逐张插入有的靠大步跳跃有的靠分而治之。把这些差异理解透远比背下十种写法更有价值。1. 冒泡排序最直观的交换思想与两处关键优化1.1 核心原理为什么叫冒泡冒泡排序是所有排序算法里最容易理解的一个也是很多人编程生涯写出的第一个排序。它的思路翻译成人话就是从头到尾两两比较相邻元素顺序不对就交换。这样每一轮结束时当前未排序部分里最大的那个数就像气泡一样慢慢浮到了数组末尾。这个比喻虽然老套但非常准确。你可以想象一个水池底部有一堆大小不一的石头大气泡上升得快一路上不断和旁边的小气泡交换位置最后到达水面。数组里每轮冒泡就是让当前范围内的最大值走到它该待的位置。没排序的数组区域会逐轮收缩。第一轮结束后数组最后一个元素一定是全局最大值第二轮就不用再管它了。这就是为什么内层循环的边界是j n - 1 - ii代表已经完成冒泡的轮数同时也是已经沉底的元素个数。很多人第一次写冒泡时容易把外层循环写成for (int i 0; i n; i)内层写成for (int j 0; j n - 1; j)逻辑上也能排出结果但做了大量无用比较。外层只需要跑n-1轮当n-1个元素都到了正确位置剩下的那一个自然也就位了。1.2 多语言实现与逐行解读C实现如下void bubbleSort(vectorint 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[j1]。1.3 优化提前终止与鸡尾酒排序纯基础的冒泡有个显而易见的问题如果数组本来就有序它依然会傻乎乎地跑完所有轮次。解决办法是加一个交换标志void bubbleSortOptimized(vectorint 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(vectorint 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个元素看成已经排好序的左手牌第i1个元素是刚摸上来的新牌。操作分两步先从右往左在一手牌里找插入位置然后把牌插入。在数组中插入意味着把比新牌大的元素逐个右移一格腾出位置。移动和交换的区别很关键。交换一次需要三次赋值而移动只需要一次赋值。插入排序在找位置的过程中用的是移动而不是交换这个细节让它在数据移动次数上比冒泡少得多。3.2 代码实现与边界条件void insertionSort(vectorint 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直到gap1此时整个数组做一次标准的插入排序。gap1的那一轮至关重要它保证了排序的完备性。之前的每一轮不管分组怎么排都不能保证全局有序只能保证宏观上越来越接近有序。等gap缩到1插入排序面对的是一个已经大体有序的数组效率很高。4.2 代码实现与增量序列的讲究void shellSort(vectorint arr) { int n arr.size(); // 从 n/2 开始每次折半直到 gap1 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, ... 1O(n²)Hibbard序列2^k - 1O(n^(3/2))Sedgewick序列4^k 3×2^(k-1) 1O(n^(4/3))增量序列的选择直接决定希尔排序的上限。同一个数组用希尔原始序列可能跑得比插入排序还慢但换Sedgewick序列后明显好转。如果你在项目中手写希尔排序优先考虑Sedgewick序列或至少用Hibbard序列别用朴素折半。4.3 希尔排序的不稳定性来源希尔排序是不稳定的。原因在于分组操作会把原本相邻的相等元素拆散到不同组内组内排序时它们可能发生跨越式移动导致相对顺序改变。举个具体例子。数组初始为[6a, 5, 6b, 4, 1]取gap3。分组情况是组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(vectorint 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(vectorint 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次在写耗尽型存储介质时是最安全的选择。如果业务上要求稳定排序且数据规模较大这五种里没有合适答案请直接选择归并排序。这也是我为什么一直强调十大排序算法要当成一个整体来学——每种算法都有它的生态位单摆在一个维度上比高低没有意义。我在实际项目中见过太多拿着锤子看什么都是钉子的案例。一排序就上快排完全不管数据规模和数据特征。其实选择排序在写密集型场景的价值、插入排序在近乎有序数据上的效率、希尔排序在嵌入式环境里的实用性都值得在合适的场合被想起来。排序算法的价值不在名字本身而在你能不能为当前的问题挑到最合适的那个方案。这也是我写这系列文章最想传达的东西。