### Python 实现插入排序 以下是使用 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 # 示例 arr = [12, 11, 13, 5, 6] insertion_sort(arr) print("插入排序后的数组:", arr) ``` 上述代码实现了插入排序的核心逻辑，其中 `key` 是当前待插入的元素，通过不断比较和移动前面较大的元素来完成排序过程[^5]。 --- ### Python 实现归并排序 以下是使用 Python 编写的归并排序算法的源代码： ```python def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] merge_sort(L) merge_sort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i < len(L): arr[k] = L[i] i += 1 k += 1 while j < len(R): arr[k] = R[j] j += 1 k += 1 # 示例 arr = [38, 27, 43, 3, 9, 82, 10] merge_sort(arr) print("归并排序后的数组:", arr) ``` 该代码展示了归并排序的经典递归实现方式。首先将数组分成两部分分别排序，再通过合并两个子数组的方式得到最终有序的结果[^4]。 --- #### 插入排序与归并排序的特点对比 - **时间复杂度** 插入排序的时间复杂度为 O(n²)，适用于小型或接近有序的数据集；而归并排序的时间复杂度稳定为 O(n log n)[^4]。 - **空间复杂度** 插入排序属于原地排序算法，其空间复杂度为 O(1)；归并排序则需要额外的空间存储临时数组，因此空间复杂度为 O(n)。 ---