python 二分查找的插入排序

二分查找的插入排序是在插入排序算法中，使用二分查找来寻找插入位置的方法。该算法通过比较要插入的元素与已排序序列的中间元素的大小关系，以缩小插入位置的搜索范围，从而提高插入的效率。

以下是使用二分查找的插入排序的Python代码示例：

import time

def binary_insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        left = 0
        right = i - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid < key:
                left = mid + 1
            else:
                right = mid - 1
        for j in range(i, left, -1):
            arr[j = arr[j - 1]
        arr[left = key
    return arr

if __name__ == '__main__':
    input_list = [5, 13, 23, 17, 9, 3, 0, 2, 11, 10]
    print('排序前：',input_list)
    t = time.perf_counter()
    sorted_list = binary_insertion_sort(input_list)
    print('插入排序后：', sorted_list)
    print(f'耗时:{time.perf_counter() - t:.8f}s')

该算法的时间复杂度为O(n^2)，在最坏情况下，即待排序序列为降序时，每次插入的位置都需要通过二分查找来确定，因此需要进行n次二分查找，每次二分查找的时间复杂度为O(log n)。因此总的时间复杂度为O(n^2)。

注意：在代码中，二分查找的插入位置是通过将大于插入元素的元素依次后移来实现的，而不是像传统的插入排序一样逐个比较并交换元素。