- +在此添加单个AI新笔记
插入排序 - 算法原理 - 插入排序的基本思想
插入排序 - 算法原理 - 插入排序的基本思想
在计算机科学的世界里，排序算法就像是一把神奇的梳子，能够将杂乱无章的数据梳理得井井有条。插入排序便是众多排序算法中一种简单且实用的算法，下面我们就来深入探究它的基本思想。
基本思想概述
插入排序的核心思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、长度加一的有序数据。这一过程就如同我们玩扑克牌时整理手中牌的过程。当我们拿到一张新牌时，会将它插入到手中已经排好顺序的牌中的合适位置，使得手中的牌始终保持有序。
具体步骤
插入排序通常从第二个元素开始，依次将每个元素插入到前面已经排好序的子数组中。具体步骤如下：
- 从数组的第二个元素开始，将其作为当前要插入的元素。
- 比较当前元素与前面已排序子数组中的元素，从后往前依次比较。
- 如果当前元素小于已排序子数组中的某个元素，则将该元素后移一位。
- 重复步骤 3，直到找到一个合适的位置，使得当前元素大于或等于该位置之前的元素。
- 将当前元素插入到找到的合适位置。
- 重复步骤 1 - 5，直到整个数组都被排序。
示例演示
为了更直观地理解插入排序的过程，我们来看一个具体的例子。假设有一个数组 [5, 3, 4, 6, 2]，我们将使用插入排序对其进行排序。
第一轮排序
- 当前要插入的元素是
3。 - 比较
3和前面已排序子数组[5]中的元素，从后往前比较。 - 由于
3 < 5，将5后移一位，得到[_, 5]。 - 此时找到合适的位置，将
3插入到该位置，得到[3, 5]。
第二轮排序
- 当前要插入的元素是
4。 - 比较
4和前面已排序子数组[3, 5]中的元素，从后往前比较。 - 由于
4 < 5，将5后移一位，得到[3, _, 5]。 - 再比较
4和3，由于4 > 3，找到合适的位置，将4插入到该位置，得到[3, 4, 5]。
第三轮排序
- 当前要插入的元素是
6。 - 比较
6和前面已排序子数组[3, 4, 5]中的元素，从后往前比较。 - 由于
6 > 5，不需要移动元素，直接将6插入到5后面，得到[3, 4, 5, 6]。
第四轮排序
- 当前要插入的元素是
2。 - 比较
2和前面已排序子数组[3, 4, 5, 6]中的元素，从后往前比较。 - 由于
2 < 6，将6后移一位，得到[3, 4, 5, _, 6]。 - 由于
2 < 5，将5后移一位，得到[3, 4, _, 5, 6]。 - 由于
2 < 4，将4后移一位，得到[3, _, 4, 5, 6]。 - 由于
2 < 3，将3后移一位，得到[_, 3, 4, 5, 6]。 - 此时找到合适的位置，将
2插入到该位置，得到[2, 3, 4, 5, 6]。
整个排序过程结束，数组已经按照升序排列。
下面是用表格总结每一轮排序的结果：
| 轮数 | 已排序子数组 | 待插入元素 | 插入后数组 |
| —— | —— | —— | —— |
| 1 | [5] | 3 | [3, 5] |
| 2 | [3, 5] | 4 | [3, 4, 5] |
| 3 | [3, 4, 5] | 6 | [3, 4, 5, 6] |
| 4 | [3, 4, 5, 6] | 2 | [2, 3, 4, 5, 6] |
代码实现（Python）
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr# 测试代码arr = [5, 3, 4, 6, 2]sorted_arr = insertion_sort(arr)print(sorted_arr)
复杂度分析
- 时间复杂度：在最坏情况下，插入排序的时间复杂度为 $O(n^2)$，其中 $n$ 是数组的长度。这是因为对于每个元素，都需要与前面的元素进行比较和移动。在最好情况下，即数组已经有序时，时间复杂度为 $O(n)$，因为每个元素只需要比较一次。
- 空间复杂度：插入排序只需要常数级的额外空间，因此空间复杂度为 $O(1)$。
总结
插入排序是一种简单易懂的排序算法，它的基本思想是通过不断地将元素插入到已排序的子数组中，最终得到一个有序的数组。虽然插入排序的时间复杂度在最坏情况下较高，但在处理小规模数据或部分有序的数据时，它的性能表现还是比较不错的。同时，插入排序的空间复杂度较低，只需要常数级的额外空间。希望通过本文的介绍，你能对插入排序的基本思想有更深入的理解。