折半插入排序

简述

折半插入排序是直接插入排序的改进版，通过采用二分法思想，在插入过程中减少比较次数，比较过程的时间复杂度降低到 $O(log_{2}n)$，但因为元素移动的时间复杂度没变，所以总体的时间复杂度还是 $O(n^2)$

折半插入与直接插入的唯一区别在于，当一个元素向前面的子集合中插入时，由于子集合已经有序，因此在寻找该元素应该插入的位置时，可以折半查找。

折半插入过程

假设有元素25需要插入到有序子集合[12,36,50,66,76,95]。采用双指针，low、high为有序子集合的上下界，初始low=0, high=5。增加一个变量mid作为子集合中间位置的指针，mid等于(low+high)/2向下取整。

1. 初始，mid等于(0+5)/2向下取整，即2。由于A[2] > 25，说明 25 应该在 low 所指位置和 mid 所指位置之间，即 mid 的左侧。下一轮判断时，high = mid-1 = 1
2. 此时low=1, high=1, mid=0。A[mid] = 12 < 25，说明 25 的位置在 mid 右侧， low = mid+1 = 1
3. 此时low=1, high=1, mid=1。A[mid] = 36 > 25，说明 25 的位置在 mid 左侧，high = mid-1 = 0
4. 此时low=1, high=0, low > high，停止比较。25应该插入的位置就是 low 所指的位置。

示例代码

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 insert2_sort(nums: List[int]) -> List[int]:
    """折半插入排序法"""
    for i in range(1, len(nums)):
        key = nums[i]
        high = i - 1
        low = 0
        while low <= high:  # 折半查找元素应该插入的位置
            mid = int((low + high) / 2)
            if key >= nums[mid]:
                low = mid + 1
            if key < nums[mid]:
                high = mid - 1

        j = i - 1
        while j >= low:  # 移动元素的过程
            nums[j+1] = nums[j]
            j -= 1
        nums[low] = key

    return nums


if __name__ == "__main__":
    origin_nums = random_list(10)
    print(origin_nums)  # Example: [12, 100, 32, 46, 19, 43, 74, 25, 16, 70]
    print(insert2_sort(origin_nums))  # Example: [12, 16, 19, 25, 32, 43, 46, 70, 74, 100]