插入排序

概述

插入排序 是一种简单直观的排序算法，通过逐个将元素插入已排序部分的正确位置来完成排序。它适用于小规模数据或基本有序的输入，体现了增量方法的设计思想。

定义

插入排序

插入排序的工作方式类似于整理手中的扑克牌：对于第 $j$ 个元素（$j=2,3,\dots ,n$），将其与已排序子数组 $A[\mathrm{1..}j-1]$ 中从右到左的元素逐一比较，找到正确位置后插入。该过程通过循环不变式保证正确性。

核心性质

• 原地排序（In-place）：仅需常数个额外存储空间（$O(1)$）。
• 稳定性（Stable）：相等元素的相对顺序在排序后保持不变。
• 自适应（Adaptive）：对基本有序的输入表现优异。
• 最坏情况时间复杂度：$\Theta (n^2)$（输入逆序时）。
• 最好情况时间复杂度：$\Theta (n)$（输入已有序时，内层循环仅执行一次比较）。
• 平均情况时间复杂度：$\Theta (n^2)$。

章节扩展

第2章：入门

• 2.1 插入排序：使用插入排序作为第一个算法示例，引入循环不变式证明方法，并与归并排序进行对比以说明算法效率的重要性。

参见

• 循环不变式
• 排序问题
• 归并排序
• 伪代码