定义
插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将未排序数据插入到已排序序列的合适位置，就像我们整理扑克牌一样，每次从桌上拿起一张牌，插入到手中已排好序的牌堆里。
算法步骤：
- 初始状态：把数组的第一个元素看作是已排序序列，其余元素构成未排序序列。
- 取出元素：从未排序序列中取出第一个元素，将其标记为当前元素。
- 寻找插入位置：在已排序序列中从后往前扫描，找到比当前元素小（升序排序）或大（降序排序）的元素的位置。
- 插入元素：将当前元素插入到该位置之后，同时将已排序序列中比当前元素大的元素依次向后移动一位。
- 重复步骤 2 - 4：不断重复上述操作，直到未排序序列为空。
示例说明
假设有数组 [5, 2, 4, 6, 1, 3]，下面是插入排序每一步的详细过程：
初始状态
已排序序列：[5]
未排序序列：[2, 4, 6, 1, 3]
第一轮插入
- 取出未排序序列的第一个元素 2 作为当前元素。
- 在已排序序列 [5] 中从后往前扫描，发现 2 < 5，将 5 向后移动一位。
- 将 2 插入到 5 原来的位置，此时：
- 已排序序列：[2, 5]
- 未排序序列：[4, 6, 1, 3]
第二轮插入
- 取出未排序序列的第一个元素 4 作为当前元素。
- 在已排序序列 [2, 5] 中从后往前扫描，4 < 5，将 5 向后移动一位；4 > 2，找到插入位置。
- 将 4 插入到 2 之后，此时：
- 已排序序列：[2, 4, 5]
- 未排序序列：[6, 1, 3]
第三轮插入
- 取出未排序序列的第一个元素 6 作为当前元素。
- 在已排序序列 [2, 4, 5] 中从后往前扫描，6 > 5，直接将 6 插入到 5 之后，此时：
- 已排序序列：[2, 4, 5, 6]
- 未排序序列：[1, 3]
第四轮插入
- 取出未排序序列的第一个元素 1 作为当前元素。
- 在已排序序列 [2, 4, 5, 6] 中从后往前扫描，1 < 6，将 6 向后移动一位；1 < 5，将 5 向后移动一位；1 < 4，将 4 向后移动一位；1 < 2，将 2 向后移动一位。
- 将 1 插入到最前面，此时：
- 已排序序列：[1, 2, 4, 5, 6]
- 未排序序列：[3]
第五轮插入
- 取出未排序序列的第一个元素 3 作为当前元素。
- 在已排序序列 [1, 2, 4, 5, 6] 中从后往前扫描，3 < 6，将 6 向后移动一位；3 < 5，将 5 向后移动一位；3 < 4，将 4 向后移动一位；3 > 2，找到插入位置。
- 将 3 插入到 2 之后，此时：
- 已排序序列：[1, 2, 3, 4, 5, 6]
- 未排序序列：[]
排序完成。
复杂度分析
插入排序的时间复杂度取决于数组的初始状态，最好情况下是已排序的数组，此时时间复杂度为 O(n)，最坏情况下是逆序的数组，此时时间复杂度为 O(n^2)。平均情况下的时间复杂度为 O(n^2)。