插入排序
**插入排序**
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
### 插入排序的基本步骤
1. **从第一个元素开始**，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5，直到所有元素均排序完毕。
### 插入排序的时间复杂度
* 最好情况：当输入的数据已经是正序时，每次插入操作只需要比较一次，不需要移动元素，因此时间复杂度为O(n)。
* 最坏情况：当输入的数据是反序时，每次插入操作需要比较和移动n次，因此时间复杂度为O(n^2)。
* 平均情况：时间复杂度也是O(n^2)。
### 插入排序的空间复杂度
插入排序是原地排序，不需要额外的存储空间，因此空间复杂度为O(1)。
### 插入排序的应用场景
插入排序适用于少量数据的排序，特别是当这些数据已经部分有序时。例如，在数据库查询优化中，插入排序可以用于对索引进行排序，以提高查询效率。此外，插入排序也常用于教学和演示排序算法的基本概念。
### 插入排序的优缺点
* 优点：插入排序在实现上，只需要用到O(1)的额外空间，且不需要额外的存储空间来进行排序；在处理部分有序的数据时，插入排序的性能优于其他复杂的排序算法。
* 缺点：插入排序的时间复杂度较高，特别是在处理大量数据时，性能不如快速排序、归并排序等高效的排序算法。
### 示例代码（Python）
```python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 测试
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array is:", sorted_arr)
```
输出结果：
```
Sorted array is: [5, 6, 11, 12, 13]
```
通过上述示例代码，我们可以看到插入排序的基本实现过程和效果。在实际应用中，可以根据数据的特性和需求选择合适的排序算法。