编辑“︁插入排序”︁

= 插入排序 =

'''插入排序'''（Insertion Sort）是一种简单直观的[[排序算法]]，适用于小规模数据或部分有序的数据集。其核心思想是通过构建有序序列，逐步将未排序的元素插入到已排序部分的适当位置，最终完成排序。

== 算法原理 ==
插入排序的工作方式类似于整理扑克牌：每次从无序部分取出一张牌，并将其插入到有序部分的正确位置。具体步骤如下：

1. 将数组分为'''已排序'''和'''未排序'''两部分，初始时已排序部分仅包含第一个元素。
2. 从未排序部分取出第一个元素，记为'''key'''。
3. 将'''key'''与已排序部分的元素'''从后向前'''比较，找到合适的插入位置。
4. 插入'''key'''后，已排序部分长度增加1，未排序部分减少1。
5. 重复上述过程，直到未排序部分为空。

=== 时间复杂度分析 ===
* 最坏情况（逆序数组）：<math>O(n^2)</math>
* 最好情况（已排序数组）：<math>O(n)</math>
* 平均情况：<math>O(n^2)</math>

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

<syntaxhighlight lang="python">
def insertion_sort(arr):
    # 遍历数组从第二个元素开始（索引1）
    for i in range(1, len(arr)):
        key = arr[i]  # 当前待插入元素
        j = i - 1      # 已排序部分的最后一个元素索引
        
        # 将大于key的元素向后移动
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        
        # 插入key到正确位置
        arr[j + 1] = key

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

'''输出结果：'''
<pre>
排序前: [12, 11, 13, 5, 6]
排序后: [5, 6, 11, 12, 13]
</pre>

== 可视化过程 ==
以下展示对数组<code>[5, 2, 4, 6, 1, 3]</code>的排序过程：

<mermaid>
graph LR
    A[初始: 5|2|4|6|1|3] --> B[第1步: 5|2|4|6|1|3]
    B --> C[第2步: 2 5|4|6|1|3]
    C --> D[第3步: 2 4 5|6|1|3]
    D --> E[第4步: 2 4 5 6|1|3]
    E --> F[第5步: 1 2 4 5 6|3]
    F --> G[最终: 1 2 3 4 5 6]
</mermaid>

== 实际应用场景 ==
插入排序在以下场景中表现优异：
1. '''小规模数据'''：当数据量较小时（如n ≤ 10），其常数因子小，实际性能可能优于<math>O(n \log n)</math>的算法。
2. '''部分有序数据'''：如日志文件按时间近乎有序时，插入排序只需<math>O(n)</math>时间。
3. '''在线算法'''：适合数据流式输入场景，可以逐个处理新元素。

=== 优化技巧 ===
* '''二分查找优化'''：用二分查找确定插入位置，减少比较次数（但仍需移动元素，时间复杂度仍为<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 \log n)</math> || <math>O(\log n)</math> || 不稳定 || 通用大规模数据
|-
| 归并排序 || <math>O(n \log n)</math> || <math>O(n)</math> || 稳定 || 需要稳定排序时
|}

== 练习题目 ==
1. 实现一个降序排列的插入排序版本
2. 对链表结构实现插入排序（注意指针操作）
3. 分析插入排序在最好/最坏情况下的元素比较次数

== 总结 ==
插入排序作为基础排序算法，虽然在大数据量时效率不高，但其实现简单、空间效率高（原地排序），在特定场景下仍具有实用价值。理解插入排序有助于学习更高级的算法设计技巧，如希尔排序和自适应排序算法。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:排序算法]]