2026/8/5 21:44:58
FEATURED · 精选文章 
1. 排序算法入门为什么从这三个开始如果你刚开始接触数据结构与算法或者准备面试那么“冒泡排序”、“选择排序”和“插入排序”这三个名字你一定绕不过去。它们常常被放在一起讲被称为“简单排序算法”或者“基础排序算法”。很多教程一上来就扔给你一堆代码和公式告诉你哪个时间复杂度是O(n²)哪个是稳定的然后就开始讲更“高级”的算法了。但这样学你很可能只记住了结论没理解精髓下次换个马甲出现的问题你还是会懵。今天我们不急着背结论。我想从一个一线开发者的角度和你一起重新“发明”一遍这三个算法。我们会深入它们的每一行逻辑看看它们是怎么“想”的为什么会有那样的性能表现以及在什么情况下那个看似“最笨”的算法反而可能是最合适的选择。理解它们不仅是应付面试更是为了建立对算法最本质的直觉——如何通过比较和交换让一堆无序的数据变得有序。这种直觉是理解所有更复杂排序归并、快排、堆排乃至其他算法的基石。我们今天的讨论会紧紧围绕三个核心维度展开时间复杂度最好、最坏、平均情况、稳定性和内存消耗是否是原地排序。你会发现这三个维度就像三把尺子能量化地衡量一个排序算法的好坏而不仅仅是感觉“快”或“慢”。2. 冒泡排序最直观的“邻里交换”策略让我们先从最符合人类直觉的冒泡排序开始。想象一下你面前有一排高低不一的队员你需要把他们按身高从低到高排好。一个很自然的想法是从左到右看如果相邻的两个人左边比右边高就让他们交换位置。这样一轮下来最高的人是不是就像气泡一样“浮”到了最右边2.1 算法流程与代码实现这个过程就是冒泡排序的核心。我们来看一下它的标准实现步骤第一轮遍历从数组的第一个元素开始比较相邻的两个元素。如果第一个比第二个大假设要升序排序就交换它们。重复遍历对数组的剩余部分每次排除掉最后已排序好的最大元素重复步骤1。终止条件当某一次遍历中没有发生任何交换时说明数组已经完全有序排序结束。这里有一个可以优化的关键点如果某一轮没有发生交换说明数组已经有序。我们可以用一个标志位来记录提前结束排序。这是冒泡排序一个重要的优化手段。def bubble_sort(arr): 冒泡排序 (优化版带提前终止) :param arr: 待排序的列表 :return: 原地排序后的列表 n len(arr) for i in range(n): # 优化标记本轮是否发生交换 swapped False # 每一轮最大的元素会“冒泡”到末尾所以内循环范围是 n-i-1 for j in range(0, n - i - 1): if arr[j] arr[j 1]: # 交换相邻元素 arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果本轮没有交换说明数组已有序提前结束 if not swapped: break return arr # 测试 test_arr [64, 34, 25, 12, 22, 11, 90] print(排序前:, test_arr) bubble_sort(test_arr) print(排序后:, test_arr)2.2 时间复杂度深度剖析有序度的概念时间复杂度是算法的命门。对于冒泡排序我们常听说它是O(n²)。但这个结论是怎么来的它永远都是O(n²)吗这里要引入一个非常重要的概念有序度。有序度指的是数组中具有有序关系的元素对的个数。对于一个完全升序的数组如[1,2,3,4,5]任意两个元素a[i]和a[j](i j) 都满足a[i] a[j]所以它的有序度是n*(n-1)/2我们称之为满有序度。逆序度则相反指具有逆序关系的元素对个数。三者关系逆序度 满有序度 - 有序度。排序的过程就是增加有序度、减少逆序度的过程。现在我们来分析冒泡排序的时间复杂度最坏时间复杂度 O(n²)当数组完全逆序时逆序度满有序度。每一对相邻元素都需要交换。对于长度为n的数组需要(n-1) (n-2) ... 1 n*(n-1)/2次比较并且也接近这么多次交换。所以是严格的O(n²)。最好时间复杂度 O(n)当数组已经完全有序时有序度满有序度。在优化版的代码中我们第一轮遍历就会因为swapped始终为False而提前退出。我们只进行了一轮n-1次比较没有交换。所以是O(n)。这是优化带来的巨大收益但很多资料在讲时间复杂度时忽略了这一点直接说最好情况也是O(n²)那指的是未优化的版本。平均时间复杂度 O(n²)对于随机顺序的数组我们可以估算其平均逆序度约为n*(n-1)/4。冒泡排序的交换次数约等于逆序度比较次数则固定约为n²/2量级。因此平均情况下的时间复杂度仍然是O(n²)级别。注意这里的时间复杂度分析主要关注比较和交换的次数它们是与数据规模n相关的核心操作。实际的运行时间还受常数因子、内存访问模式等影响但大O表示法抓住了主要矛盾。2.3 稳定性与内存消耗分析稳定性冒泡排序是稳定的排序算法。稳定性是指如果待排序的序列中存在值相等的元素经过排序之后相等元素之间原有的先后顺序不变。在冒泡排序的代码中只有当arr[j] arr[j 1]时才交换。对于相等的元素不会进行交换。因此相等元素的相对位置不会改变。内存消耗原地排序冒泡排序是原地排序算法。原地排序是指空间复杂度为O(1)的排序算法即算法运行过程中只需要常数级别的额外存储空间如几个临时变量i,j,swapped,temp。它直接在输入的数组上进行元素交换没有申请与数据规模n成正比的新数组。2.4 实战心得与使用场景虽然冒泡排序在效率上名声不佳但它并非一无是处。优点代码极其简单逻辑清晰是教学和理解排序思想的绝佳范例。对于几乎已经有序有序度很高的小规模数据集比如n50优化后的冒泡排序可能因为提前终止而表现得不错并且代码的简单性降低了出错风险。缺点效率低下尤其是对于逆序或随机的大规模数据。大量的交换操作每次交换需要三次赋值比单纯比较更耗时。一个容易踩的坑内层循环的边界是n - i - 1。这里的-1至关重要因为比较的是arr[j]和arr[j1]如果j跑到最后一个元素j1就会索引越界。我见过不少新手在这里出错。那么在实际开发中会用冒泡排序吗几乎不会。在99%的场景下语言内置的排序函数如Python的list.sort()或sorted()底层是Timsort一种混合排序算法或者快速排序、归并排序是更好的选择。冒泡排序的价值主要在于教育意义和特殊约束场景比如嵌入式设备内存极小且数据量固定且非常小需要最简单可靠的代码。3. 选择排序朴素的“按需索取”策略如果说冒泡排序是在“勤勤恳恳地交换”那么选择排序的思路就更“精明”一些。它的核心思想是分已排序区间和未排序区间。每次从未排序区间中找到最小或最大的元素将其放到已排序区间的末尾。3.1 算法流程与代码实现这个过程就像我们打牌时把手里的牌摊开每次挑出最小的一张放到一边直到挑完。初始时已排序区间为空未排序区间为整个数组。在未排序区间中遍历找到最小的元素。将该最小元素与未排序区间的第一个元素交换位置。此时未排序区间第一个元素就加入了已排序区间在末尾。重复步骤2和3直到未排序区间为空。def selection_sort(arr): 选择排序 :param arr: 待排序的列表 :return: 原地排序后的列表 n len(arr) for i in range(n): # 假设当前未排序部分的第一个元素是最小的 min_idx i # 在 i1 到 n-1 的范围内寻找真正的最小值 for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j # 将找到的最小元素与当前位置i的元素交换 arr[i], arr[min_idx] arr[min_idx], arr[i] return arr # 测试 test_arr [64, 25, 12, 22, 11] print(排序前:, test_arr) selection_sort(test_arr) print(排序后:, test_arr)3.2 时间复杂度分析与数据状态无关选择排序的时间复杂度分析起来比冒泡排序更“单纯”因为它数据移动的次数很少。比较次数无论数组初始状态如何完全有序、完全逆序、随机选择排序都必须执行完所有比较。第一轮找最小需要比较n-1次第二轮需要n-2次...最后一轮需要1次。总比较次数为(n-1) (n-2) ... 1 n*(n-1)/2。这是一个固定值。交换次数最好情况下是0次数组已经有序且最小值就在当前位置但算法依然会执行交换arr[i], arr[i] arr[i], arr[i]这通常算作一次交换但实际无操作。最坏情况下是n-1次每次找到的最小值都不在当前位置。但无论怎样交换次数是O(n)级别的远小于比较次数。因此选择排序的最好、最坏、平均时间复杂度都是 O(n²)。它的性能与数据的初始有序度无关显得非常“稳定”指性能曲线平稳非算法稳定性。3.3 稳定性与内存消耗分析稳定性选择排序是不稳定的排序算法。这是它一个重要的缺陷。我们来看一个例子数组[5, 8, 5, 2, 9]。第一轮我们会找到最小值2与第一个元素5交换得到[2, 8, 5, 5, 9]。注意原本在前面的那个5索引0被交换到了后面索引2而原本在后面的5索引2留在了前面。两个相等元素5的相对顺序被破坏了。内存消耗原地排序选择排序是原地排序算法。和冒泡排序一样它只使用了常数级别的额外空间如i,j,min_idx,temp空间复杂度为O(1)。3.4 实战心得与使用场景选择排序的优缺点非常鲜明。优点交换次数少。在那些交换成本非常高的场景下比如要排序的元素是非常庞大的对象交换操作涉及大量内存拷贝选择排序可能比冒泡排序有优势。它的思路简单代码也容易写。缺点时间复杂度固定为O(n²)且不稳定。对于大规模数据效率低下。一个关键细节内层循环for j in range(i1, n)是从i1开始的因为arr[i]是当前未排序区间的第一个元素我们默认它最小然后去后面找更小的。如果写成for j in range(i, n)虽然不影响结果但会多一次无意义的自己和自己比较。使用场景和冒泡排序类似选择排序的实际应用场景非常有限。它偶尔会用于对交换开销敏感且数据量极小的场合或者作为更复杂算法如堆排序可以看作是一种优化的选择排序的引子。在面试中理解其不稳定的原因是一个高频考点。4. 插入排序高效的“局部整理”策略插入排序是我们今天要讲的三个算法中在实际小规模数据排序中最有用、最高效的一个。它的思想非常贴近我们整理扑克牌的过程左手拿着的牌是已排序好的右手从牌堆里拿一张新牌插入到左手牌中正确的位置。4.1 算法流程与代码实现将数组的第一个元素视为一个已排序的序列。取出下一个元素在已排序的序列中从后向前扫描。如果该元素已排序大于新元素则将该元素移到下一位置向后移动一位。重复步骤3直到找到已排序的元素小于或等于新元素的位置。将新元素插入到该位置后。重复步骤2~5直到所有元素都处理完毕。def insertion_sort(arr): 插入排序 :param arr: 待排序的列表 :return: 原地排序后的列表 n len(arr) # 从第二个元素开始索引1因为第一个元素默认已排序 for i in range(1, n): key arr[i] # 当前待插入的元素 j i - 1 # 已排序序列的末尾索引 # 从后向前扫描已排序序列寻找插入位置 # 如果已排序部分的元素大于key就将其后移 while j 0 and key arr[j]: arr[j 1] arr[j] j - 1 # 找到插入位置放入key arr[j 1] key return arr # 测试 test_arr [12, 11, 13, 5, 6] print(排序前:, test_arr) insertion_sort(test_arr) print(排序后:, test_arr)4.2 时间复杂度分析与有序度强相关插入排序的性能与数据的初始有序度密切相关这一点和优化后的冒泡排序类似但通常表现更好。最坏时间复杂度 O(n²)当数组完全逆序时。每次插入操作都需要将已排序序列的所有元素向后移动一位。总比较和移动次数约为n*(n-1)/2即O(n²)。最好时间复杂度 O(n)当数组已经完全有序时。每次我们取新元素key它都比已排序序列的最后一个元素大或等于所以while循环的条件key arr[j]立即为假循环一次都不执行。我们只需要进行n-1次比较和0次数据移动除了赋值key因此是O(n)。平均时间复杂度 O(n²)对于随机数组平均每次插入需要移动已排序部分的一半元素。因此平均时间复杂度仍然是O(n²)级别。但是它的常数项比冒泡和选择排序要小因为它的操作以赋值为主而冒泡排序是大量的交换三次赋值。这里有一个非常重要的洞见对于部分有序的数组插入排序的效率可以非常高接近O(n)。这也是为什么很多高级排序算法如Timsort在底层对小规模或基本有序的子序列使用插入排序的原因。4.3 稳定性与内存消耗分析稳定性插入排序是稳定的排序算法。在代码中我们移动元素的条件是key arr[j]严格小于。当遇到一个等于key的元素arr[j]时循环停止我们将key插入到arr[j]的后面。这样就保证了相等元素的原始相对顺序。内存消耗原地排序插入排序是原地排序算法。它只需要一个额外的临时变量key来存储待插入元素以及循环变量空间复杂度为O(1)。4.4 实战心得、优化与使用场景插入排序是我个人在需要手写排序逻辑时最可能考虑的基础算法尤其是在数据量小或基本有序的情况下。优势对小规模数据极其高效当 n 很小比如小于50时O(n²)的常数项很小插入排序简单快速的特性使其性能往往优于需要递归或复杂数据结构的O(n log n)算法。这就是“算法常数项”的重要性。对部分有序数组高效如前所述这是它的杀手锏。自适应它的运行时间对输入数据的特性敏感能利用已有的有序性。在线排序插入排序可以一边接收数据一边排序即数据流式输入因为它只需要维护一个已排序的序列。而像归并排序、堆排序通常需要所有数据一次性到位。优化技巧——二分查找插入在寻找插入位置时我们使用的是线性搜索从后往前比。由于已排序部分是有序的我们可以使用二分查找来快速定位插入点将比较次数从O(n)降到O(log n)。但是这并不能改变整体时间复杂度为O(n²)的事实因为元素的移动arr[j1] arr[j]仍然是O(n)的。不过在比较成本远高于移动成本的特殊场景下比如比较两个字符串很耗时二分查找插入排序是有价值的。def binary_insertion_sort(arr): 使用二分查找优化的插入排序比较次数减少但移动次数不变 n len(arr) for i in range(1, n): key arr[i] # 使用二分查找找到key应该插入的位置 left, right 0, i - 1 while left right: mid (left right) // 2 if arr[mid] key: left mid 1 else: right mid - 1 # left 就是key应该插入的位置 # 将 left..i-1 的元素整体后移一位 for j in range(i-1, left-1, -1): arr[j 1] arr[j] arr[left] key return arr一个常见的实现错误在内部的while循环中必须同时检查j 0和key arr[j]。如果先检查key arr[j]当j -1时会发生数组越界错误。使用场景小数组排序许多标准库的排序算法在递归到小子数组时如长度小于16会切换使用插入排序。几乎有序的数组比如一个已经排序好的数组只有少数几个元素位置不对插入排序会非常快。链表排序插入排序在链表数据结构上可以很高效地实现因为链表插入是O(1)操作而移动元素在数组中需要批量后移在链表中只是修改指针。对于链表插入排序可能是最优的简单排序算法。5. 终极对比与抉择何时用哪个学完了三个算法我们来一个面对面的终极对比并回答那个最实际的问题我到底该用哪个特性维度冒泡排序 (优化版)选择排序插入排序最好时间复杂度O(n)(数组已有序)O(n²)O(n)(数组已有序)最坏时间复杂度O(n²)O(n²)O(n²)平均时间复杂度O(n²)O(n²)O(n²)时间复杂度常数项大 (交换多)中 (比较固定交换少)小(移动为主比较可优化)空间复杂度O(1) (原地)O(1) (原地)O(1) (原地)稳定性稳定不稳定稳定对数据有序性敏感度高(有序时很快)低 (无感)极高(有序时极快)核心操作比较与交换比较与选择比较与移动如何选择永远的首选在需要自己实现排序时插入排序。除非你有特殊理由否则在需要手写简单排序时插入排序通常是更好的选择。它对部分有序数据友好常数项小实现简单且稳定。对于小规模数据n 50它的性能常常是最好的。当交换成本极高时考虑选择排序。如果你排序的元素是包含大量数据的复杂结构体交换两个元素意味着拷贝大量内存那么选择排序固定的、最少n-1次的交换次数可能成为优势。当需要稳定性且数据可能已有序时优化后的冒泡排序是一个选项但插入排序几乎在所有这些方面都优于它。冒泡排序的主要价值在于教学和极简场景。实际开发中的黄金法则使用语言或库内置的排序函数。例如Python的sorted()和list.sort()Java的Arrays.sort()和Collections.sort()C的std::sort。这些函数由顶尖专家优化针对不同数据规模和类型采用了混合策略如IntroSort, Timsort在绝大多数情况下都是最优选择。自己重新造轮子不仅容易出错而且效率低下。理解这三个基础排序算法真正的目的不是为了在项目里用它们而是为了建立算法思维。你理解了比较、交换、移动这些基本操作的成本理解了时间复杂度的分析方法理解了稳定性和原地排序这些概念。当你再学习快速排序、归并排序、堆排序时你会清楚地知道它们是在哪些方面做了优化和权衡从而能更深刻地掌握它们。这才是学习基础算法的最大意义。
从冒泡、选择、插入排序入门算法：时间复杂度、稳定性与实战场景解析
1. 排序算法入门为什么从这三个开始如果你刚开始接触数据结构与算法或者准备面试那么“冒泡排序”、“选择排序”和“插入排序”这三个名字你一定绕不过去。它们常常被放在一起讲被称为“简单排序算法”或者“基础排序算法”。很多教程一上来就扔给你一堆代码和公式告诉你哪个时间复杂度是O(n²)哪个是稳定的然后就开始讲更“高级”的算法了。但这样学你很可能只记住了结论没理解精髓下次换个马甲出现的问题你还是会懵。今天我们不急着背结论。我想从一个一线开发者的角度和你一起重新“发明”一遍这三个算法。我们会深入它们的每一行逻辑看看它们是怎么“想”的为什么会有那样的性能表现以及在什么情况下那个看似“最笨”的算法反而可能是最合适的选择。理解它们不仅是应付面试更是为了建立对算法最本质的直觉——如何通过比较和交换让一堆无序的数据变得有序。这种直觉是理解所有更复杂排序归并、快排、堆排乃至其他算法的基石。我们今天的讨论会紧紧围绕三个核心维度展开时间复杂度最好、最坏、平均情况、稳定性和内存消耗是否是原地排序。你会发现这三个维度就像三把尺子能量化地衡量一个排序算法的好坏而不仅仅是感觉“快”或“慢”。2. 冒泡排序最直观的“邻里交换”策略让我们先从最符合人类直觉的冒泡排序开始。想象一下你面前有一排高低不一的队员你需要把他们按身高从低到高排好。一个很自然的想法是从左到右看如果相邻的两个人左边比右边高就让他们交换位置。这样一轮下来最高的人是不是就像气泡一样“浮”到了最右边2.1 算法流程与代码实现这个过程就是冒泡排序的核心。我们来看一下它的标准实现步骤第一轮遍历从数组的第一个元素开始比较相邻的两个元素。如果第一个比第二个大假设要升序排序就交换它们。重复遍历对数组的剩余部分每次排除掉最后已排序好的最大元素重复步骤1。终止条件当某一次遍历中没有发生任何交换时说明数组已经完全有序排序结束。这里有一个可以优化的关键点如果某一轮没有发生交换说明数组已经有序。我们可以用一个标志位来记录提前结束排序。这是冒泡排序一个重要的优化手段。def bubble_sort(arr): 冒泡排序 (优化版带提前终止) :param arr: 待排序的列表 :return: 原地排序后的列表 n len(arr) for i in range(n): # 优化标记本轮是否发生交换 swapped False # 每一轮最大的元素会“冒泡”到末尾所以内循环范围是 n-i-1 for j in range(0, n - i - 1): if arr[j] arr[j 1]: # 交换相邻元素 arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果本轮没有交换说明数组已有序提前结束 if not swapped: break return arr # 测试 test_arr [64, 34, 25, 12, 22, 11, 90] print(排序前:, test_arr) bubble_sort(test_arr) print(排序后:, test_arr)2.2 时间复杂度深度剖析有序度的概念时间复杂度是算法的命门。对于冒泡排序我们常听说它是O(n²)。但这个结论是怎么来的它永远都是O(n²)吗这里要引入一个非常重要的概念有序度。有序度指的是数组中具有有序关系的元素对的个数。对于一个完全升序的数组如[1,2,3,4,5]任意两个元素a[i]和a[j](i j) 都满足a[i] a[j]所以它的有序度是n*(n-1)/2我们称之为满有序度。逆序度则相反指具有逆序关系的元素对个数。三者关系逆序度 满有序度 - 有序度。排序的过程就是增加有序度、减少逆序度的过程。现在我们来分析冒泡排序的时间复杂度最坏时间复杂度 O(n²)当数组完全逆序时逆序度满有序度。每一对相邻元素都需要交换。对于长度为n的数组需要(n-1) (n-2) ... 1 n*(n-1)/2次比较并且也接近这么多次交换。所以是严格的O(n²)。最好时间复杂度 O(n)当数组已经完全有序时有序度满有序度。在优化版的代码中我们第一轮遍历就会因为swapped始终为False而提前退出。我们只进行了一轮n-1次比较没有交换。所以是O(n)。这是优化带来的巨大收益但很多资料在讲时间复杂度时忽略了这一点直接说最好情况也是O(n²)那指的是未优化的版本。平均时间复杂度 O(n²)对于随机顺序的数组我们可以估算其平均逆序度约为n*(n-1)/4。冒泡排序的交换次数约等于逆序度比较次数则固定约为n²/2量级。因此平均情况下的时间复杂度仍然是O(n²)级别。注意这里的时间复杂度分析主要关注比较和交换的次数它们是与数据规模n相关的核心操作。实际的运行时间还受常数因子、内存访问模式等影响但大O表示法抓住了主要矛盾。2.3 稳定性与内存消耗分析稳定性冒泡排序是稳定的排序算法。稳定性是指如果待排序的序列中存在值相等的元素经过排序之后相等元素之间原有的先后顺序不变。在冒泡排序的代码中只有当arr[j] arr[j 1]时才交换。对于相等的元素不会进行交换。因此相等元素的相对位置不会改变。内存消耗原地排序冒泡排序是原地排序算法。原地排序是指空间复杂度为O(1)的排序算法即算法运行过程中只需要常数级别的额外存储空间如几个临时变量i,j,swapped,temp。它直接在输入的数组上进行元素交换没有申请与数据规模n成正比的新数组。2.4 实战心得与使用场景虽然冒泡排序在效率上名声不佳但它并非一无是处。优点代码极其简单逻辑清晰是教学和理解排序思想的绝佳范例。对于几乎已经有序有序度很高的小规模数据集比如n50优化后的冒泡排序可能因为提前终止而表现得不错并且代码的简单性降低了出错风险。缺点效率低下尤其是对于逆序或随机的大规模数据。大量的交换操作每次交换需要三次赋值比单纯比较更耗时。一个容易踩的坑内层循环的边界是n - i - 1。这里的-1至关重要因为比较的是arr[j]和arr[j1]如果j跑到最后一个元素j1就会索引越界。我见过不少新手在这里出错。那么在实际开发中会用冒泡排序吗几乎不会。在99%的场景下语言内置的排序函数如Python的list.sort()或sorted()底层是Timsort一种混合排序算法或者快速排序、归并排序是更好的选择。冒泡排序的价值主要在于教育意义和特殊约束场景比如嵌入式设备内存极小且数据量固定且非常小需要最简单可靠的代码。3. 选择排序朴素的“按需索取”策略如果说冒泡排序是在“勤勤恳恳地交换”那么选择排序的思路就更“精明”一些。它的核心思想是分已排序区间和未排序区间。每次从未排序区间中找到最小或最大的元素将其放到已排序区间的末尾。3.1 算法流程与代码实现这个过程就像我们打牌时把手里的牌摊开每次挑出最小的一张放到一边直到挑完。初始时已排序区间为空未排序区间为整个数组。在未排序区间中遍历找到最小的元素。将该最小元素与未排序区间的第一个元素交换位置。此时未排序区间第一个元素就加入了已排序区间在末尾。重复步骤2和3直到未排序区间为空。def selection_sort(arr): 选择排序 :param arr: 待排序的列表 :return: 原地排序后的列表 n len(arr) for i in range(n): # 假设当前未排序部分的第一个元素是最小的 min_idx i # 在 i1 到 n-1 的范围内寻找真正的最小值 for j in range(i 1, n): if arr[j] arr[min_idx]: min_idx j # 将找到的最小元素与当前位置i的元素交换 arr[i], arr[min_idx] arr[min_idx], arr[i] return arr # 测试 test_arr [64, 25, 12, 22, 11] print(排序前:, test_arr) selection_sort(test_arr) print(排序后:, test_arr)3.2 时间复杂度分析与数据状态无关选择排序的时间复杂度分析起来比冒泡排序更“单纯”因为它数据移动的次数很少。比较次数无论数组初始状态如何完全有序、完全逆序、随机选择排序都必须执行完所有比较。第一轮找最小需要比较n-1次第二轮需要n-2次...最后一轮需要1次。总比较次数为(n-1) (n-2) ... 1 n*(n-1)/2。这是一个固定值。交换次数最好情况下是0次数组已经有序且最小值就在当前位置但算法依然会执行交换arr[i], arr[i] arr[i], arr[i]这通常算作一次交换但实际无操作。最坏情况下是n-1次每次找到的最小值都不在当前位置。但无论怎样交换次数是O(n)级别的远小于比较次数。因此选择排序的最好、最坏、平均时间复杂度都是 O(n²)。它的性能与数据的初始有序度无关显得非常“稳定”指性能曲线平稳非算法稳定性。3.3 稳定性与内存消耗分析稳定性选择排序是不稳定的排序算法。这是它一个重要的缺陷。我们来看一个例子数组[5, 8, 5, 2, 9]。第一轮我们会找到最小值2与第一个元素5交换得到[2, 8, 5, 5, 9]。注意原本在前面的那个5索引0被交换到了后面索引2而原本在后面的5索引2留在了前面。两个相等元素5的相对顺序被破坏了。内存消耗原地排序选择排序是原地排序算法。和冒泡排序一样它只使用了常数级别的额外空间如i,j,min_idx,temp空间复杂度为O(1)。3.4 实战心得与使用场景选择排序的优缺点非常鲜明。优点交换次数少。在那些交换成本非常高的场景下比如要排序的元素是非常庞大的对象交换操作涉及大量内存拷贝选择排序可能比冒泡排序有优势。它的思路简单代码也容易写。缺点时间复杂度固定为O(n²)且不稳定。对于大规模数据效率低下。一个关键细节内层循环for j in range(i1, n)是从i1开始的因为arr[i]是当前未排序区间的第一个元素我们默认它最小然后去后面找更小的。如果写成for j in range(i, n)虽然不影响结果但会多一次无意义的自己和自己比较。使用场景和冒泡排序类似选择排序的实际应用场景非常有限。它偶尔会用于对交换开销敏感且数据量极小的场合或者作为更复杂算法如堆排序可以看作是一种优化的选择排序的引子。在面试中理解其不稳定的原因是一个高频考点。4. 插入排序高效的“局部整理”策略插入排序是我们今天要讲的三个算法中在实际小规模数据排序中最有用、最高效的一个。它的思想非常贴近我们整理扑克牌的过程左手拿着的牌是已排序好的右手从牌堆里拿一张新牌插入到左手牌中正确的位置。4.1 算法流程与代码实现将数组的第一个元素视为一个已排序的序列。取出下一个元素在已排序的序列中从后向前扫描。如果该元素已排序大于新元素则将该元素移到下一位置向后移动一位。重复步骤3直到找到已排序的元素小于或等于新元素的位置。将新元素插入到该位置后。重复步骤2~5直到所有元素都处理完毕。def insertion_sort(arr): 插入排序 :param arr: 待排序的列表 :return: 原地排序后的列表 n len(arr) # 从第二个元素开始索引1因为第一个元素默认已排序 for i in range(1, n): key arr[i] # 当前待插入的元素 j i - 1 # 已排序序列的末尾索引 # 从后向前扫描已排序序列寻找插入位置 # 如果已排序部分的元素大于key就将其后移 while j 0 and key arr[j]: arr[j 1] arr[j] j - 1 # 找到插入位置放入key arr[j 1] key return arr # 测试 test_arr [12, 11, 13, 5, 6] print(排序前:, test_arr) insertion_sort(test_arr) print(排序后:, test_arr)4.2 时间复杂度分析与有序度强相关插入排序的性能与数据的初始有序度密切相关这一点和优化后的冒泡排序类似但通常表现更好。最坏时间复杂度 O(n²)当数组完全逆序时。每次插入操作都需要将已排序序列的所有元素向后移动一位。总比较和移动次数约为n*(n-1)/2即O(n²)。最好时间复杂度 O(n)当数组已经完全有序时。每次我们取新元素key它都比已排序序列的最后一个元素大或等于所以while循环的条件key arr[j]立即为假循环一次都不执行。我们只需要进行n-1次比较和0次数据移动除了赋值key因此是O(n)。平均时间复杂度 O(n²)对于随机数组平均每次插入需要移动已排序部分的一半元素。因此平均时间复杂度仍然是O(n²)级别。但是它的常数项比冒泡和选择排序要小因为它的操作以赋值为主而冒泡排序是大量的交换三次赋值。这里有一个非常重要的洞见对于部分有序的数组插入排序的效率可以非常高接近O(n)。这也是为什么很多高级排序算法如Timsort在底层对小规模或基本有序的子序列使用插入排序的原因。4.3 稳定性与内存消耗分析稳定性插入排序是稳定的排序算法。在代码中我们移动元素的条件是key arr[j]严格小于。当遇到一个等于key的元素arr[j]时循环停止我们将key插入到arr[j]的后面。这样就保证了相等元素的原始相对顺序。内存消耗原地排序插入排序是原地排序算法。它只需要一个额外的临时变量key来存储待插入元素以及循环变量空间复杂度为O(1)。4.4 实战心得、优化与使用场景插入排序是我个人在需要手写排序逻辑时最可能考虑的基础算法尤其是在数据量小或基本有序的情况下。优势对小规模数据极其高效当 n 很小比如小于50时O(n²)的常数项很小插入排序简单快速的特性使其性能往往优于需要递归或复杂数据结构的O(n log n)算法。这就是“算法常数项”的重要性。对部分有序数组高效如前所述这是它的杀手锏。自适应它的运行时间对输入数据的特性敏感能利用已有的有序性。在线排序插入排序可以一边接收数据一边排序即数据流式输入因为它只需要维护一个已排序的序列。而像归并排序、堆排序通常需要所有数据一次性到位。优化技巧——二分查找插入在寻找插入位置时我们使用的是线性搜索从后往前比。由于已排序部分是有序的我们可以使用二分查找来快速定位插入点将比较次数从O(n)降到O(log n)。但是这并不能改变整体时间复杂度为O(n²)的事实因为元素的移动arr[j1] arr[j]仍然是O(n)的。不过在比较成本远高于移动成本的特殊场景下比如比较两个字符串很耗时二分查找插入排序是有价值的。def binary_insertion_sort(arr): 使用二分查找优化的插入排序比较次数减少但移动次数不变 n len(arr) for i in range(1, n): key arr[i] # 使用二分查找找到key应该插入的位置 left, right 0, i - 1 while left right: mid (left right) // 2 if arr[mid] key: left mid 1 else: right mid - 1 # left 就是key应该插入的位置 # 将 left..i-1 的元素整体后移一位 for j in range(i-1, left-1, -1): arr[j 1] arr[j] arr[left] key return arr一个常见的实现错误在内部的while循环中必须同时检查j 0和key arr[j]。如果先检查key arr[j]当j -1时会发生数组越界错误。使用场景小数组排序许多标准库的排序算法在递归到小子数组时如长度小于16会切换使用插入排序。几乎有序的数组比如一个已经排序好的数组只有少数几个元素位置不对插入排序会非常快。链表排序插入排序在链表数据结构上可以很高效地实现因为链表插入是O(1)操作而移动元素在数组中需要批量后移在链表中只是修改指针。对于链表插入排序可能是最优的简单排序算法。5. 终极对比与抉择何时用哪个学完了三个算法我们来一个面对面的终极对比并回答那个最实际的问题我到底该用哪个特性维度冒泡排序 (优化版)选择排序插入排序最好时间复杂度O(n)(数组已有序)O(n²)O(n)(数组已有序)最坏时间复杂度O(n²)O(n²)O(n²)平均时间复杂度O(n²)O(n²)O(n²)时间复杂度常数项大 (交换多)中 (比较固定交换少)小(移动为主比较可优化)空间复杂度O(1) (原地)O(1) (原地)O(1) (原地)稳定性稳定不稳定稳定对数据有序性敏感度高(有序时很快)低 (无感)极高(有序时极快)核心操作比较与交换比较与选择比较与移动如何选择永远的首选在需要自己实现排序时插入排序。除非你有特殊理由否则在需要手写简单排序时插入排序通常是更好的选择。它对部分有序数据友好常数项小实现简单且稳定。对于小规模数据n 50它的性能常常是最好的。当交换成本极高时考虑选择排序。如果你排序的元素是包含大量数据的复杂结构体交换两个元素意味着拷贝大量内存那么选择排序固定的、最少n-1次的交换次数可能成为优势。当需要稳定性且数据可能已有序时优化后的冒泡排序是一个选项但插入排序几乎在所有这些方面都优于它。冒泡排序的主要价值在于教学和极简场景。实际开发中的黄金法则使用语言或库内置的排序函数。例如Python的sorted()和list.sort()Java的Arrays.sort()和Collections.sort()C的std::sort。这些函数由顶尖专家优化针对不同数据规模和类型采用了混合策略如IntroSort, Timsort在绝大多数情况下都是最优选择。自己重新造轮子不仅容易出错而且效率低下。理解这三个基础排序算法真正的目的不是为了在项目里用它们而是为了建立算法思维。你理解了比较、交换、移动这些基本操作的成本理解了时间复杂度的分析方法理解了稳定性和原地排序这些概念。当你再学习快速排序、归并排序、堆排序时你会清楚地知道它们是在哪些方面做了优化和权衡从而能更深刻地掌握它们。这才是学习基础算法的最大意义。 
