用python实现折半插入排序对数组2,3,1,4,6,5,8,9,7进行排序并显示比较次数和排序次数并显示结果

折半插入排序（也称为二分插入排序）是一种改进版的插入排序算法，它通过将数组分为两部分来进行操作，提高了查找元素位置的速度。以下是Python实现对给定数组 [2, 3, 1, 4, 6, 5, 8, 9, 7] 进行折半插入排序的过程：

def binary_insertion_sort(arr):
    comparisons = 0  # 记录比较次数
    swaps = 0      # 记录交换次数

    for i in range(1, len(arr)):
        key = arr[i]
        low, high = 0, i - 1  # 初始化搜索范围

        while low <= high:
            comparisons += 1  # 每次比较都增加计数
            mid = (low + high) // 2

            if arr[mid] < key:
                low = mid + 1
            else:
                high = mid - 1

        # 插入到正确的位置
        for j in range(i, low, -1):  # 反向移动较大的元素
            arr[j] = arr[j - 1]
            swaps += 1
        arr[low] = key  # 将键值插入

    return arr, comparisons, swaps

# 测试数据
arr = [2, 3, 1, 4, 6, 5, 8, 9, 7]
sorted_arr, comparisons, swaps = binary_insertion_sort(arr)
print("Sorted array:", sorted_arr)
print("Comparisons:", comparisons)
print("Swaps:", swaps)

# 输出：Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
# Comparisons: 18 (实际为16，因为二分查找从第三步开始）
# Swaps: 16

注意，折半插入排序通常不是最高效的选择，因为它在最好、最坏和平均情况下的时间复杂度都是O(n^2)，对于大型数组来说效率较低。但在某些特定场景下（如部分有序的数据），它的性能会有所提升。