单词列表的Binary insertion sort实现失效问题排查求助

你的增强插入排序（二分插入排序）无法正常工作，主要有三个核心错误：

错误1：二分查找范围错误 #

你的binarySearch函数在整个列表中查找插入位置，但二分插入排序的逻辑是：遍历到第i个元素时，前i-1个元素已经是有序的，只需在这个已排序子范围内查找插入位置，而不是包含未排序的后半部分。错误的查找范围会导致计算出的插入位置完全错误。

错误2：列表insert方法参数顺序颠倒 #

Python列表的insert方法语法是list.insert(索引位置, 要插入的元素)，但你写的是self.words.insert(current_value, position)——把元素和位置参数写反了，这会尝试将position作为元素插入，而把current_value当作索引（字符串无法作为索引，必然报错）。

错误3：未移除原位置的元素 #

处理当前元素时，直接插入新位置会导致原元素仍留在列表中，造成重复元素，同时打乱列表长度和后续遍历的索引逻辑。

修正后的完整代码 #

def insert(self, word, position=None):
    if position is None:
        self.words.append(word)
    else:
        self.words.insert(position, word)

def binarySearch(self, word, end):
    # 仅在0到end的已排序子范围内查找
    first = 0
    last = end
    while first <= last:
        mid = (first + last) // 2
        if word == self.words[mid]:
            return mid
        elif word < self.words[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return first

def enhancedInsertionSort(self):
    for i in range(1, len(self.words)):
        # 先移除当前位置的元素，避免重复
        current_value = self.words.pop(i)
        # 在已排序的前i-1个元素中找插入位置
        position = self.binarySearch(current_value, i-1)
        # 按正确顺序插入元素
        self.words.insert(position, current_value)

补充说明 #

• 修改binarySearch增加了end参数，用于限定查找的右边界，确保只在已排序的子列表中计算位置。
• 使用pop(i)先移除当前元素，再插入到正确位置，避免了重复元素和索引混乱的问题。
• 严格遵循insert方法的参数顺序，确保元素插入到正确索引位置。

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