插入排序：修订间差异

2025年5月12日 (一) 00:27的最新版本

插入排序（Insertion Sort）是一种简单直观的排序算法，适用于小规模数据或基本有序的数据集。其核心思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用原地排序（即只需用到O(1)的额外空间），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述[编辑 | 编辑源代码]

插入排序的工作方式类似于整理扑克牌： 1. 从第一个元素开始，该元素可以认为已经被排序。 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。 4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。 5. 将新元素插入到该位置后。 6. 重复步骤2~5，直到所有元素均排序完毕。

时间复杂度分析[编辑 | 编辑源代码]

最坏时间复杂度： $O (n^{2})$ （当输入数组逆序时）
平均时间复杂度： $O (n^{2})$
最好时间复杂度： $O (n)$ （当输入数组已排序时）

代码实现[编辑 | 编辑源代码]

以下是插入排序的Python实现示例：

def insertion_sort(arr):
    # 遍历从1到n-1的元素
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 将arr[0..i-1]中比key大的元素向后移动
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # 插入key到正确位置

# 示例使用
if __name__ == "__main__":
    data = [12, 11, 13, 5, 6]
    print("排序前:", data)
    insertion_sort(data)
    print("排序后:", data)

输出:

排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]

实际应用场景[编辑 | 编辑源代码]

插入排序在以下场景中特别有用： 1. 小规模数据排序：当数据量较小时（通常n<100），插入排序的性能可能优于更复杂的算法如快速排序或归并排序。 2. 基本有序数据：当输入数组"几乎排序"时（即每个元素距离它的最终位置不远），插入排序的效率接近O(n)。 3. 在线算法：插入排序可以一边接收数据一边排序，适用于数据流式的输入场景。 4. 混合排序算法：常被用作快速排序或归并排序等算法的子过程，用于处理小的子数组。

变体与优化[编辑 | 编辑源代码]

二分插入排序[编辑 | 编辑源代码]

通过使用二分查找来找到插入位置，可以将比较次数从O(n^2)减少到O(n log n)，但移动元素的复杂度仍为O(n^2)。

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # 使用二分查找找到插入位置
        left, right = 0, i - 1
        while left <= right:
            mid = (left + right) // 2
            if key < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 移动元素
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]
        arr[left] = key

希尔排序[编辑 | 编辑源代码]

希尔排序是插入排序的高效改进版本，通过将原始列表分成多个子列表来改进插入排序的性能。

算法比较[编辑 | 编辑源代码]

算法	平均时间复杂度	空间复杂度	稳定性
插入排序	$O (n^{2})$	O(1)	稳定
冒泡排序	$O (n^{2})$	O(1)	稳定
选择排序	$O (n^{2})$	O(1)	不稳定

练习题目[编辑 | 编辑源代码]

1. 实现一个降序排列的插入排序版本。 2. 修改插入排序算法，使其同时记录每个元素的原始位置。 3. 分析当输入数组已经排序时，插入排序的性能表现。 4. 比较插入排序和选择排序在相同数据集上的性能差异。

总结[编辑 | 编辑源代码]

插入排序虽然在大规模数据上效率不高，但由于其实现简单、对小规模数据高效、对基本有序数据表现优异等特点，仍然在实际应用中有其一席之地。理解插入排序有助于掌握更复杂的排序算法，也是学习算法设计与分析的良好起点。

@@ 第1行： / 第1行： @@
-= 插入排序 =
+{{DISPLAYTITLE:插入排序}}
-'''插入排序'''（Insertion Sort）是一种简单直观的[[排序算法]]，适用于小规模数据或部分有序的数据集。其核心思想是通过构建有序序列，逐步将未排序的元素插入到已排序部分的适当位置，最终完成排序。
+'''插入排序'''（Insertion Sort）是一种简单直观的[[排序算法]]，适用于小规模数据或基本有序的数据集。其核心思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用原地排序（即只需用到O(1)的额外空间），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
-== 算法原理 ==
+== 算法描述 ==
-插入排序的工作方式类似于整理扑克牌：每次从无序部分取出一张牌，并将其插入到有序部分的正确位置。具体步骤如下：
+插入排序的工作方式类似于整理扑克牌：
+. 从第一个元素开始，该元素可以认为已经被排序。
-. 将数组分为'''已排序'''和'''未排序'''两部分，初始时已排序部分仅包含第一个元素。
+. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
-. 从未排序部分取出第一个元素，记为'''key'''。
+. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
-. 将'''key'''与已排序部分的元素'''从后向前'''比较，找到合适的插入位置。
+. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
-. 插入'''key'''后，已排序部分长度增加1，未排序部分减少1。
+. 将新元素插入到该位置后。
-. 重复上述过程，直到未排序部分为空。
+. 重复步骤2~5，直到所有元素均排序完毕。
 === 时间复杂度分析 ===
-* 最坏情况（逆序数组）：<math>O(n^2)</math>
+* 最坏时间复杂度：<math>O(n^2)</math>（当输入数组逆序时）
-* 最好情况（已排序数组）：<math>O(n)</math>
+* 平均时间复杂度：<math>O(n^2)</math>
-* 平均情况：<math>O(n^2)</math>
+* 最好时间复杂度：<math>O(n)</math>（当输入数组已排序时）
 == 代码实现 ==
@@ 第22行： / 第22行： @@
 <syntaxhighlight lang="python">
 def insertion_sort(arr):
-     # 遍历数组从第二个元素开始（索引1）
+     # 遍历从1到n-1的元素
      for i in range(1, len(arr)):
-         key = arr[i]  # 当前待插入元素
+         key = arr[i]
-         j = i - 1      # 已排序部分的最后一个元素索引
+         j = i - 1
+         # 将arr[0..i-1]中比key大的元素向后移动
-         # 将大于key的元素向后移动
+         while j >= 0 and key < arr[j]:
-         while j >= 0 and arr[j] > key:
              arr[j + 1] = arr[j]
              j -= 1
+         arr[j + 1] = key  # 插入key到正确位置
-        # 插入key到正确位置
-         arr[j + 1] = key
-# 示例用法
+# 示例使用
 if __name__ == "__main__":
      data = [12, 11, 13, 5, 6]
@@ 第43行： / 第40行： @@
 </syntaxhighlight>
-'''输出结果：'''
+'''输出:'''
 <pre>
 排序前: [12, 11, 13, 5, 6]
@@ 第49行： / 第46行： @@
 </pre>
-== 可视化过程 ==
+== 可视化示例 ==
-以下展示对数组<code>[5, 2, 4, 6, 1, 3]</code>的排序过程：
+以下是插入排序过程的mermaid图示：
 <mermaid>
-graph LR
+graph TD
-     A[初始: 5|2|4|6|1|3] --> B[第1步: 5|2|4|6|1|3]
+     A[初始数组: 12, 11, 13, 5, 6] --> B[第一步: 12|11,13,5,6]
-     B --> C[第2步: 2 5|4|6|1|3]
+     B --> C[11插入到12前: 11,12|13,5,6]
-     C --> D[第3步: 2 4 5|6|1|3]
+     C --> D[13保持位置: 11,12,13|5,6]
-     D --> E[第4步: 2 4 5 6|1|3]
+     D --> E[5插入最前: 5,11,12,13|6]
-     E --> F[第5步: 1 2 4 5 6|3]
+     E --> F[6插入到5后: 5,6,11,12,13]
-    F --> G[最终: 1 2 3 4 5 6]
 </mermaid>
 == 实际应用场景 ==
-插入排序在以下场景中表现优异：
+插入排序在以下场景中特别有用：
-. '''小规模数据'''：当数据量较小时（如n ≤ 10），其常数因子小，实际性能可能优于<math>O(n \log n)</math>的算法。
+. '''小规模数据排序'''：当数据量较小时（通常n<100），插入排序的性能可能优于更复杂的算法如快速排序或归并排序。
-. '''部分有序数据'''：如日志文件按时间近乎有序时，插入排序只需<math>O(n)</math>时间。
+. '''基本有序数据'''：当输入数组"几乎排序"时（即每个元素距离它的最终位置不远），插入排序的效率接近O(n)。
-. '''在线算法'''：适合数据流式输入场景，可以逐个处理新元素。
+. '''在线算法'''：插入排序可以一边接收数据一边排序，适用于数据流式的输入场景。
+. '''混合排序算法'''：常被用作快速排序或归并排序等算法的子过程，用于处理小的子数组。
+== 变体与优化 ==
+=== 二分插入排序 ===
+通过使用二分查找来找到插入位置，可以将比较次数从O(n^2)减少到O(n log n)，但移动元素的复杂度仍为O(n^2)。
+<syntaxhighlight lang="python">
+def binary_insertion_sort(arr):
+    for i in range(1, len(arr)):
+        key = arr[i]
+        # 使用二分查找找到插入位置
+        left, right = 0, i - 1
+        while left <= right:
+            mid = (left + right) // 2
+            if key < arr[mid]:
+                right = mid - 1
+            else:
+                left = mid + 1
+        # 移动元素
+        for j in range(i - 1, left - 1, -1):
+            arr[j + 1] = arr[j]
+        arr[left] = key
+</syntaxhighlight>
-=== 优化技巧 ===
+=== 希尔排序 ===
-* '''二分查找优化'''：用二分查找确定插入位置，减少比较次数（但仍需移动元素，时间复杂度仍为<math>O(n^2)</math>）
+希尔排序是插入排序的高效改进版本，通过将原始列表分成多个子列表来改进插入排序的性能。
-* '''希尔排序'''：通过分组插入排序实现改进，平均复杂度可达<math>O(n^{1.25})</math>
-== 与其他排序算法对比 ==
+== 算法比较 ==
 {| class="wikitable"
 |-
-! 算法 !! 平均时间复杂度 !! 空间复杂度 !! 稳定性 !! 适用场景
+! 算法 !! 平均时间复杂度 !! 空间复杂度 !! 稳定性
 |-
-| 插入排序 || <math>O(n^2)</math> || <math>O(1)</math> || 稳定 || 小规模/部分有序数据
+| 插入排序 || <math>O(n^2)</math> || O(1) || 稳定
 |-
-| 快速排序 || <math>O(n \log n)</math> || <math>O(\log n)</math> || 不稳定 || 通用大规模数据
+| 冒泡排序 || <math>O(n^2)</math> || O(1) || 稳定
 |-
-| 归并排序 || <math>O(n \log n)</math> || <math>O(n)</math> || 稳定 || 需要稳定排序时
+| 选择排序 || <math>O(n^2)</math> || O(1) || 不稳定
 |}
 == 练习题目 ==
-. 实现一个降序排列的插入排序版本
+. 实现一个降序排列的插入排序版本。
-. 对链表结构实现插入排序（注意指针操作）
+. 修改插入排序算法，使其同时记录每个元素的原始位置。
-. 分析插入排序在最好/最坏情况下的元素比较次数
+. 分析当输入数组已经排序时，插入排序的性能表现。
+. 比较插入排序和选择排序在相同数据集上的性能差异。
 == 总结 ==
-插入排序作为基础排序算法，虽然在大数据量时效率不高，但其实现简单、空间效率高（原地排序），在特定场景下仍具有实用价值。理解插入排序有助于学习更高级的算法设计技巧，如希尔排序和自适应排序算法。
+插入排序虽然在大规模数据上效率不高，但由于其实现简单、对小规模数据高效、对基本有序数据表现优异等特点，仍然在实际应用中有其一席之地。理解插入排序有助于掌握更复杂的排序算法，也是学习算法设计与分析的良好起点。
 [[Category:计算机科学]]
-[[Category:数据结构与算法]]
+[[Category:面试技巧]]
 [[Category:排序算法]]