Python插入排序详解（从零开始掌握插入排序算法）

插入排序的工作原理

假设我们有一个数组 [5, 2, 4, 6, 1, 3]，插入排序会这样工作：

1. 从第二个元素（索引为1）开始，因为第一个元素可视为已排序。
2. 将当前元素与已排序部分从右往左比较。
3. 如果当前元素小于已排序中的某个元素，则将该元素右移。
4. 重复步骤3，直到找到合适位置，插入当前元素。
5. 继续处理下一个元素，直到整个数组有序。

Python插入排序代码实现

下面是一个清晰、易懂的Python排序教程中的插入排序实现：

def insertion_sort(arr):    # 从第二个元素开始遍历    for i in range(1, len(arr)):        key = arr[i]  # 当前要插入的元素        j = i - 1     # 已排序部分的最后一个索引        # 将大于key的元素向右移动        while j >= 0 and arr[j] > key:            arr[j + 1] = arr[j]            j -= 1        # 插入key到正确位置        arr[j + 1] = key    return arr# 示例使用numbers = [5, 2, 4, 6, 1, 3]print("原始数组:", numbers)sorted_numbers = insertion_sort(numbers.copy())print("排序后数组:", sorted_numbers)

代码逐行解析

• for i in range(1, len(arr)):：从索引1开始，因为索引0默认已排序。
• key = arr[i]：保存当前要插入的值。
• while j >= 0 and arr[j] > key:：只要已排序部分还有元素且比key大，就右移。
• arr[j + 1] = key：找到位置后插入key。

时间与空间复杂度

- 最好情况：数组已排序，时间复杂度为 O(n)。
- 最坏情况：数组逆序，时间复杂度为 O(n²)。
- 平均情况：O(n²)。
- 空间复杂度：O(1)，属于原地排序。

为什么学习插入排序？

虽然插入排序在大数据集上效率不高，但它是理解更复杂算法（如快速排序、归并排序）的基础。对于小规模数据或部分有序的数据，插入排序非常高效。这也是每个初学者排序算法学习者必学的内容。

总结

通过本教程，你已经掌握了Python插入排序的核心思想和实现方法。记住：算法学习贵在理解与实践。试着自己动手写几遍代码，并用不同数据测试它。你会发现，排序其实没那么难！

关键词回顾：Python插入排序、插入排序算法、Python排序教程、初学者排序算法。