大家好，我是顺亿，今天咱们来聊聊插入排序这个老朋友。是不是有时候看到 LeetCode 上的排序题就头疼？别担心，今天我就来手把手教你如何用插入排序来解决问题。
首先，插入排序的核心思想就是将数组分成两部分：已排序的和未排序的。每次我们从未排序的部分取出一个元素，然后找到它在已排序部分正确的位置，插入进去。这样，未排序的部分就少了一个元素，已排序的部分就多了一个元素。重复这个过程，直到整个数组都被排序。
具体步骤如下：
- 从第二个元素开始，将其视为当前要插入的元素。
- 将当前元素与已排序部分的元素从右到左依次比较。
- 如果已排序部分的元素大于当前元素，则将该元素向右移动一位。
- 重复步骤 2 和 3，直到找到一个小于或等于当前元素的位置。
- 将当前元素插入到该位置。
复杂度分析：
时间复杂度：O(n²)，其中 n 是数组的长度。最坏情况下，需要进行 n(n-1)/2 次比较和移动。
空间复杂度：O(1)，只需要常数级的额外空间。
代码实现：
# 插入排序
def insertion_sort(arr):
n = len(arr)
# 从第二个元素开始遍历
for i in range(1, n):
# 当前要插入的元素
key = arr[i]
# 已排序部分的最后一个元素的索引
j = i - 1
# 将大于 key 的元素向右移动
while j >= 0 and key < arr[j):
arr[j + 1] = arr[j]
j -= 1
# 将 key 插入到正确的位置
arr[j + 1] = key
return arr
# 测试
def test_insertion_sort():
arr = [64, 34, 25, 12, 22, 11, 90]
print(insertion_sort(arr)) # 输出：[11, 12, 22, 25, 34, 64, 90]
arr = [5, 4, 3, 2, 1]
print(insertion_sort(arr)) # 输出：[1, 2, 3, 4, 5]
arr = [1, 2, 3, 4, 5]
print(insertion_sort(arr)) # 输出：[1, 2, 3, 4, 5]
if __name__ == "__main__":
test_insertion_sort()
测试用例：
测试用例 1：基本情况
输入：
[64, 34, 25, 12, 22, 11, 90]输出：
[11, 12, 22, 25, 34, 64, 90]测试用例 2：逆序数组
输入：
[5, 4, 3, 2, 1]输出：
[1, 2, 3, 4, 5]测试用例 3：已排序数组
输入：
[1, 2, 3, 4, 5]输出：
[1, 2, 3, 4, 5]
总结一下，插入排序是一种简单但效率不是特别高的排序算法。对于小规模数据或者基本有序的数据来说，它的效率还是不错的。掌握了插入排序，你对排序算法的理解就又深了一层。
想要了解更多编程知识，记得关注「趣航编程网」（www.vqhf.com）哦，顺亿在这里等你！