「排序算法」专题 2:插入排序(熟悉)


「排序算法」专题 2:插入排序(熟悉)

思路:每次将一个数字插入一个有序的数组里,成为一个长度更长的有序数组,有限次操作以后,数组整体有序。

结论:稳定排序,在接近有序的情况下,表现优异。

02-insertion-sort-01.png

图片来自「力扣」第 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)$;
  • 由于「插入排序」在「几乎有序」的数组上表现良好,特别地,在「短数组」上的表现也很好。因为「短数组」的特点是:每个元素离它最终排定的位置都不会太远。为此,在小区间内执行排序任务的时候,可以转向使用「插入排序」

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
下一篇 
「排序算法」专题 1:选择排序(了解) 「排序算法」专题 1:选择排序(了解)
「排序算法」专题 1:选择排序(了解) 这里和大家分享一下我学习的「基础排序算法」的知识点。 我从零基础到真正入门算法,就是从学习排序算法开始的,所以「排序算法」是我的初恋,差不多 3 年了。排序算法作为一项需求,它足够简单,是学习基础算
  目录