一、直接插入排序
算法逻辑：通过将待排序元素逐个插入到已排序序列的合适位置来实现排序。代码中通常使用一个临时变量tmp暂存当前待插入元素，然后从后向前在已排序部分比较并移动元素，找到插入位置后完成插入。
性能分析：
- 最好情况（原序列已有序）：
- 比较次数：$ n - 1 $
- 移动次数：0
- 最坏情况（原序列逆序）：
- 比较次数：$ \sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} $
- 移动次数：$ \sum_{i=2}^{n} (i+1) = \frac{(n+3)(n-2)}{2} $
- 平均情况：比较和移动次数均约为 $ \frac{n^2}{4} $
- 时间复杂度：$ O(n^2) $
- 空间复杂度：$ O(1) $（仅需一个辅助变量）
- 稳定性：稳定（相同元素不会改变相对顺序）
definsertion_sort(arr):foriinrange(1,len(arr)):tmp=arr[i]# 暂存待插入元素j=i-1# 向前查找插入位置whilej>=0andarr[j]>tmp:arr[j+1]=arr[j]j-=1arr[j+1]=tmp# 插入正确位置returnarr二、冒泡排序
算法逻辑：通过相邻元素两两比较，若逆序则交换，每一趟遍历将最大元素“沉”到最后。最多进行 $ n-1 $ 趟，若某趟未发生交换，则说明序列已有序，可提前结束。
性能特点：
- 最好情况（序列已有序）：
- 比较次数：$ n - 1 $
- 交换次数：0
- 可通过标志位优化提前退出
- 最坏情况（完全逆序）：
- 比较次数：$ \frac{n(n-1)}{2} $
- 交换次数：$ \frac{n(n-1)}{2} $
- 时间复杂度：$ O(n^2) $
- 空间复杂度：$ O(1) $
- 稳定性：稳定
defbubble_sort(arr):n=len(arr)foriinrange(n-1):swapped=Falseforjinrange(n-1-i):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]swapped=Trueifnotswapped:# 无交换说明已有序breakreturnarr这类排序算法属于简单排序算法，适用于小规模数据或教学场景，是数据结构与算法的基础内容，广泛应用于编程考试、面试题及软件设计基础知识体系中。
在实际应用中，直接插入排序的效率通常高于冒泡排序，主要原因如下：
1.比较和交换次数更少
- 插入排序：每趟只需将当前元素插入到已排序部分的正确位置，过程中只进行必要的比较和移动（不涉及频繁交换）。
- 在最好情况下（已有序），仅需 $ n-1 $ 次比较，0 次移动。
- 平均情况下，比较和移动次数约为 $ \frac{n^2}{4} $。
- 冒泡排序：每趟都要对相邻元素两两比较，并在逆序时进行交换。
- 即使数据已经有序，若未加优化仍会执行全部趟数；虽然可通过标志位优化提前退出，但最坏情况下的交换次数高达 $ \frac{n(n-1)}{2} $，远高于插入排序的数据移动量。
⚠️ 注意：插入排序中的“移动”是赋值操作（通过
tmp和后移实现），而冒泡排序中的“交换”是三个赋值完成一次 swap，代价更高。
2.实际运行性能更优
- 插入排序具有更好的缓存局部性（访问连续内存），适合现代计算机架构。
- 更少的写操作使其在嵌入式系统或写入成本高的存储中更具优势。
3.适应性强
- 插入排序对接近有序的数据表现极好，时间复杂度趋近于 $ O(n) $。
- 冒泡排序即使经过优化，在部分有序情况下也难以达到同样响应速度。
4.代码执行效率对比示例
对于相同输入[5, 1, 2, 3, 4]：
- 插入排序：只需将
5向右移动一位，其余元素前移一格，整体移动较少。 - 冒泡排序：需要多次交换才能将
5“冒泡”到最后，中间产生大量冗余交换。
✅结论：
虽然两者时间复杂度均为 $ O(n^2) $，但插入排序的实际执行效率显著优于冒泡排序。因此，在简单排序算法中，插入排序是更推荐使用的方案，尤其适用于小规模或基本有序的数据集。
# 示例：插入排序比冒泡排序更快地处理接近有序数据arr1=[2,1,3,4,5]print("原数组:",arr1)print("插入排序结果:",insertion_sort(arr1.copy()))print("冒泡排序结果:",bubble_sort(arr1.copy()))
