直接插入排序

简述

假设有一待排序集合 $A = {a_1,a_2,a_3,a_4, ... ,a_n}$ ，采用直接插入排序的排序过程如下

从集合的起始位置出发，将 $a_1$ 视为只有一个元素的有序子集合 $B$
从 $a_2$ 开始，依次将 $a_2$ 到 $a_n$ 按照一定顺序插入到有序子集合 $B$ 中，最终得到的有序子集合 $B$ 就是最终排序后的集合 $A$

时间复杂度

直接插入排序算法直观易懂，但由于每插入一个元素都要与子集合做对比，因此复杂度较高。

直接插入排序法有两个部分：一部分是元素移动，另一部分是元素比较。

元素比较部分，考虑最坏情况，即初始数组是逆序的，那么每插入一个元素到子集合都要与子集合所有元素对比一次。

max=\sum_{i=2}^{n} i = \frac{1}{2}n(n+1)-1=O(n^2)

元素移动部分，最坏情况下，每插入一个元素，子集合所有元素都要向后移动。

max=\sum_{i=2}^{n} i+1=\frac{1}{2}(n+2)(n+1)-3=O(n^2)

总体而言，直接插入法的时间复杂度为 $O(n^2)$ ，是排序算法中时间复杂度最高的算法。

示例代码

Python

from random import randint
from typing import List


def random_list(length: int = 10, start: int = 10, end: int = 100) -> List[int]:
    """生成指定长度的随机整数列表

    Args:
        length (int, optional): 随机数列表长度. Defaults to 10.
        start (int, optional): 范围最小值. Defaults to 10.
        end (int, optional): 范围最大值. Defaults to 100.

    Returns:
        List[int]: 随机数列表
    """
    return [randint(start, end) for _ in range(length)]


def insert_sort(nums: List[int]) -> List[int]:
    """直接插入排序法

    Args:
        nums (List[int]): 待排序的列表

    Returns:
        List[int]: 排序后的列表
    """
    for i in range(1, len(nums)):
        key = nums[i]
        j = i - 1
        while j >= 0 and key < nums[j]:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums


if __name__ == "__main__":
    origin_nums = random_list(10)
    print(origin_nums)  # Example: [30, 26, 13, 97, 65, 49, 66, 42, 39, 60]
    print(insert_sort(origin_nums))  # Example: [13, 26, 30, 39, 42, 49, 60, 65, 66, 97]

简述​

时间复杂度​

示例代码​

Python​

简述

时间复杂度

示例代码

Python