单词列表的二进制插入排序

Question

我正在做一种增强的插入排序，它与称为字典的单词列表的二进制插入排序基本相同，但由于某种原因，我的列表没有排序，我似乎不知道原因。

我创建了 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):
        first = 0
        last = len(self.words)-1
        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[i]
            position = self.binarySearch(current_value)
            self.words.insert(current_value, position)
            

我尝试使用 pop 函数，但仍然不断出现错误。任何帮助将不胜感激

Answer 1

有几个问题会导致您的代码出现故障：

• 您以错误的顺序向

  insert

  方法提供了参数。检查文档

• 循环的一次迭代仅inserts一个值，但不会从其来源位置删除该值，因此此循环将增加

  words

  列表的长度，这不是插入排序所应该的去做。列表的大小不应改变。

• insert

  将从给定的 position 开始移动

  all

  值，但同样，这不是插入排序应该做的。相反，它应该只移动两个索引（

  position

  和

  i

  ）之间的值，并将

  i

  处的值写入索引

  position

  ，从而执行旋转。由于您不希望列表的长度发生变化，因此

  insert

  不是您需要的方法。你可以使用切片。

• 为了让

  binarySearch

  正确工作，必须假设 整个 列表已排序，但您暂时调用它时，仅对索引

  i

  之前的分区进行排序，因此这并不总是正确工作。您确实需要一个仅考虑排序分区来执行二分搜索的函数。为了实现这一点，您的

  binarySearch

  可以获得一个额外的参数，该参数提供排序分区的 size。

这是您的代码，其中包含对上述几点的更正：

    def binarySearch(self, word, length): # Added parameter
        first = 0
        last = length-1 # Use the argument to set the scope of the search
        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[i]
            # Indicate the size of the sorted partition:
            position = self.binarySearch(current_value, i)
            # Don't use a method (insert or pop) that changes the size:
            self.words[position+1:i+1] = self.words[position:i]
            self.words[position] = current_value

其他备注

• Python 有一个原生的

  sort

  方法，它优于这种自定义排序实现。
• Python 有

  bisect

  库用于进行二分搜索，这将再次优于您的函数。
• 不要使用

  for i in range(1, len(self.words))

  和单独阅读

  self.words[i]

  ，而是使用

  enumerate

  和

  islice

  （跳过第一个元素）

考虑到最后两点，您的代码可能具有以下内容：

import itertools
import bisect

# ...

    def enhancedInsertionSort(self):
        # get value and index in one go using enumerate, and skip first with islice
        for i, current_value in itertools.islice(enumerate(self.words), 1, None):
            # use bisect for binary search
            position = bisect.bisect_left(self.words, current_value, hi=i)
            self.words[position+1:i+1] = self.words[position:i]
            self.words[position] = current_value