求助：修改Python插入排序以调用给定的Binary Search函数

没问题，我来帮你搞定这个修改！首先咱们先理清楚核心逻辑：原来的插入排序是通过逐个向前比较来找到元素应该插入的位置，现在要换成用给定的binarySearch函数直接定位插入点，这样能把查找位置的时间复杂度从O(n)降到O(logn)，虽然整体排序的时间复杂度还是O(n²)（因为移动元素的步骤还是O(n)），但确实是个有效的优化。

核心思路拆解 #

1. 原插入排序中，while pos > 0 and aList[pos - 1] > key这段代码的作用有两个：
   • 找到key应该插入的正确位置pos
   • 同时把比key大的元素逐个往后挪一位
2. 现在我们可以用binarySearch直接一步找到这个pos，然后单独处理元素移动的步骤——因为binarySearch只负责找位置，不帮我们移动元素。

修改后的代码实现 #

def binarySearch(aList, start, end, value): #Return the position where value is or should be inserted.
    while start <= end:
        mid = (start + end) // 2
        if aList[mid] == value:
            return mid
        if value < aList[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return start

def insertionSort(aList): #Sort aList in ascending order.
    for index in range(1, len(aList)):
        key = aList[index]
        # 调用binarySearch，在已排序的区间[0, index-1]中找key的插入位置
        pos = binarySearch(aList, 0, index - 1, key)
        # 把pos到index-1的元素都往后移动一位，给key腾出位置
        aList[pos+1:index+1] = aList[pos:index]
        # 把key放到正确的位置
        aList[pos] = key

代码解释 #

• 调用binarySearch时，我们传入的区间是0到index-1，因为插入排序中，前index个元素里，0到index-1已经是排好序的了，index位置是当前要插入的元素。
• 元素移动的部分用了Python的切片赋值：aList[pos+1:index+1] = aList[pos:index]，这段代码会把从pos到index-1的元素，整体复制到pos+1到index的位置，相当于把这些元素都往后挪了一位，比原来的while循环写法更简洁。
• 最后把key放到pos位置，完成这一轮的插入。

测试验证 #

运行你提供的测试代码：

numbers = [71, 32, 22, 19, 18, 1, 15, 40]
insertionSort(numbers)
print(numbers)

输出结果是：[1, 15, 18, 19, 22, 32, 40, 71]，完全符合升序排序的要求。

内容的提问来源于stack exchange，提问作者moonhead