插入排序

插入排序（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]

可视化示例

以下是插入排序过程的mermaid图示：

实际应用场景

插入排序在以下场景中特别有用： 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. 比较插入排序和选择排序在相同数据集上的性能差异。

总结

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