折半插入排序实验

好的，折半插入排序是一种优化的插入排序算法。它的基本思想是将待排序的序列分成两个部分：有序部分和无序部分。初始时，有序部分只包含一个元素，无序部分包含除该元素外的所有元素。接着，每次从无序部分取出第一个元素，使用二分查找算法找到该元素在有序部分应该插入的位置，然后将该元素插入到有序部分的相应位置，直到无序部分中的所有元素都被插入到有序部分中。以下是 Python 代码实现折半插入排序算法的过程：

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

我们可以使用以下代码来测试折半插入排序算法的效率：

import random
import time

arr = [random.randint(0, 1000) for i in range(10000)]

start_time = time.time()
sorted_arr = binary_insertion_sort(arr)
end_time = time.time()

print(f"Time taken to sort the array: {end_time - start_time:.6f} seconds")

这样就可以得到折半插入排序算法的执行时间了。