「排序算法」专题 2:插入排序(熟悉)
思路:每次将一个数字插入一个有序的数组里,成为一个长度更长的有序数组,有限次操作以后,数组整体有序。
结论:稳定排序,在接近有序的情况下,表现优异。
图片来自「力扣」第 147 题:对链表进行插入排序。
Java 代码:
public class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
// 循环不变量:将 nums[i] 插入到区间 [0, i) 使之成为有序数组
for (int i = 1; i < len; i++) {
// 先暂存这个元素,然后之前元素逐个后移,留出空位
int temp = nums[i];
int j = i;
// 注意边界 j > 0
while (j > 0 && nums[j - 1] > temp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = temp;
}
return nums;
}
}
Python 代码:
from sorting.sorting_util import SortingUtil
from sorting.examples import GenerateRandomArrayStrategy
from sorting.examples import GenerateNearlySortedArrayStrategy
from sorting.selecting_sort import SelectionSort
class InsertionSort:
def __str__(self):
return "插入排序"
@SortingUtil.cal_time
def sort(self, arr):
"""
插入排序第 1 版:相比选择排序而言,插入排序的内层循环可以提前终止。
但是这个版本有个缺点,交换次数太多,每一次交换做了 3 次赋值。
"""
size = len(arr)
for i in range(1, size):
for j in range(i, 0, -1):
# 只要前面的比后面的“严格”大,就要交换它们的位置
if arr[j - 1] > arr[j]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
else:
break
class InsertionSortOptimizer:
def __str__(self):
return "插入排序(优化)"
@SortingUtil.cal_time
def sort(self, arr):
size = len(arr)
for i in range(1, size):
# 每一轮先让这个元素去别的地方休息一下
temp = arr[i]
# 从 i 的前一个元素开始看
j = i
while j > 0 and arr[j - 1] > temp:
arr[j] = arr[j - 1]
j -= 1
# 因为已经看到索引 j 的值小于等于 temp 了
# 因此空出来的位置是 j,要把 temp 放在这里
arr[j] = temp
if __name__ == '__main__':
# 测试插入排序算法的正确性
# SortingUtil.test_sorting_algorithm(InsertionSort(), GenerateRandomArrayStrategy(5000))
# 比较插入排序算法与选择排序
# SortingUtil.compare_sorting_algorithms(GenerateRandomArrayStrategy(5000),
# SelectionSort(),
# InsertionSort())
# 验证插入排序算法对于几乎有序的数组,越有序越好
SortingUtil.test_sorting_algorithm(InsertionSortOptimizer(), GenerateRandomArrayStrategy(5000))
SortingUtil.compare_sorting_algorithms(GenerateRandomArrayStrategy(5000),
SelectionSort(),
InsertionSort(),
InsertionSortOptimizer())
SortingUtil.compare_sorting_algorithms(GenerateNearlySortedArrayStrategy(5000),
SelectionSort(),
InsertionSort(),
InsertionSortOptimizer())
复杂度分析:
时间复杂度:$O(N^2)$,这里 $N$ 是数组的长度;
空间复杂度:$O(1)$,使用到常数个临时变量。
总结
- 优化:「将一个数字插入一个有序的数组」这一步,可以不使用逐步交换,使用先赋值给「临时变量」,然后「适当的元素」后移,空出一个位置,最后把「临时变量」赋值给这个空位的策略(就是上面那张图的意思)。编码的时候如果不小心,可能会把数组的值修改,建议多调试;
- 特点:「插入排序」可以提前终止内层循环(体现在
nums[j - 1] > temp
不满足时),在数组「几乎有序」的前提下,「插入排序」的时间复杂度可以达到 $O(N)$; - 由于「插入排序」在「几乎有序」的数组上表现良好,特别地,在「短数组」上的表现也很好。因为「短数组」的特点是:每个元素离它最终排定的位置都不会太远。为此,在小区间内执行排序任务的时候,可以转向使用「插入排序」。
(本节完)