公告
欢迎来到我的博客喵。
443 字
2 分钟
插入排序
直接插入排序
将待排序的数组分为已排序区和未排序区，初始时已排序区只有第一个元素。然后从未排序区依次取出元素，插入到已排序区的适当位置，直到未排序区为空。
这个比较用的是顺序查找，找到插入位置后，后面的元素需要整体后移一位。
算法步骤
-
从数组的第二个元素开始，依次取出每个元素作为当前元素
key。 -
将
key与已排序区的元素从后向前比较，找到key应该插入的位置：在大于等于key的元素位置停止比较。 -
将
key插入到找到的位置，已排序区里比较过的元素整体后移一位。
代码实现
array<int, 5> insertSort(array<int, 5> arr) { int n = arr.size(); for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // 在已排序区间 arr[0..i-1] 中从后向前查找插入位置 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 元素后移 j--; } arr[j + 1] = key; // 插入 key } return arr;}时间复杂度分析
主要是看比较和移动操作：
-
最好情况：当数组已经有序时，每次比较只需进行一次，时间复杂度为 O(n)。
-
最坏情况：当数组是逆序时，每次插入都需要比较和移动所有已排序区的元素，时间复杂度为 O(n^2)。
-
平均情况：假设每次插入时，
key平均需要比较和移动已排序区的一半元素，时间复杂度仍为 O(n^2)。
稳定性
直接插入排序是稳定的排序算法，因为相等元素的相对顺序不会改变。