编辑“︁插入排序”︁

{{DISPLAYTITLE:插入排序}}

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

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

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

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

<syntaxhighlight lang="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)
</syntaxhighlight>

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

== 可视化示例 ==
以下是插入排序过程的mermaid图示：

<mermaid>
graph TD
    A[初始数组: 12, 11, 13, 5, 6] --> B[第一步: 12|11,13,5,6]
    B --> C[11插入到12前: 11,12|13,5,6]
    C --> D[13保持位置: 11,12,13|5,6]
    D --> E[5插入最前: 5,11,12,13|6]
    E --> F[6插入到5后: 5,6,11,12,13]
</mermaid>

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

== 变体与优化 ==
=== 二分插入排序 ===
通过使用二分查找来找到插入位置，可以将比较次数从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>

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

== 算法比较 ==
{| class="wikitable"
|-
! 算法 !! 平均时间复杂度 !! 空间复杂度 !! 稳定性
|-
| 插入排序 || <math>O(n^2)</math> || O(1) || 稳定
|-
| 冒泡排序 || <math>O(n^2)</math> || O(1) || 稳定
|-
| 选择排序 || <math>O(n^2)</math> || O(1) || 不稳定
|}

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

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

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:排序算法]]