【插入排序算法】插入排序是一种简单直观的排序算法，其基本思想是将一个数据元素插入到已经排好序的序列中，从而得到一个新的、更长的有序序列。该算法适用于小规模数据或部分有序的数据集。
一、插入排序的基本原理
插入排序的核心在于“逐个插入”。具体步骤如下：
1. 从数组的第二个元素开始（即索引为1的元素），将其视为待插入的元素。
2. 比较该元素与前面已排序的部分，找到合适的位置进行插入。
3. 将比它大的元素依次后移，为新元素腾出位置。
4. 插入完成后，继续处理下一个元素，直到整个数组有序。
二、插入排序的特点
| 特性 | 说明 |
| 稳定性 | 稳定排序（相同值的元素顺序不变） |
| 时间复杂度 | 最坏：O(n²)，最好：O(n)（当数组已有序时） |
| 空间复杂度 | O(1)（原地排序） |
| 适用场景 | 数据量较小或部分有序的数据集 |
三、插入排序的实现逻辑（伪代码）
```
for i from 1 to length(array) - 1 do
key = array[i
j = i - 1
while j >= 0 and array[j] > key do
array[j + 1] = array[j
j = j - 1
end while
array[j + 1] = key
end for
```
四、插入排序的优缺点
| 优点 | 缺点 |
| 实现简单，易于理解 | 对于大规模数据效率较低 |
| 原地排序，空间消耗低 | 不适合完全无序的数据 |
| 对于部分有序的数据表现较好 | 比较次数较多，时间复杂度较高 |
五、总结
插入排序虽然在大数据量下效率不高，但在实际应用中，特别是在数据量较小或接近有序的情况下，仍然具有较高的实用价值。它是一种基础但重要的排序算法，常用于教学和小型项目中。掌握其原理有助于理解更复杂的排序算法，如希尔排序等。
