利用二进制搜索改进插入排序的最坏情况运行时间

Question

while循环使用线性搜索向后扫描。但是，我们知道while循环中的数组已经排序。因此，我们可以用二进制搜索代替线性搜索，这样O(n)将变为O(lg )。然而，我对此的看法是，它不会有助于减少总体时间，因为我们仍然必须将元素向前移动一个索引，这将总是需要(倒退步数(N))次。因此，总的来说，运行时间仍然是O(n^2)，对于这种情况，没有办法达到O(n lg n)。如果我以错误的方式来处理这个问题，请告诉我。

INSERTION-SORT(A)

 for j = 2 to length[A]
  do key = A[j]
     i = j - 1

  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1

  A[i+1] = key

Answer 1

插入排序将数组中的元素推入，以便为行中的下一个元素释放空间。

因此，如果您使用二进制搜索找到了输入新元素的位置，则仍然需要将索引之后的所有元素向前推一步(向右)。

给定一个向后排序的数组: 10,9,8,7,6,5,4,3,2,1

为了插入第i个元素，您需要向右推i-1个元素(即使您使用二进制搜索)-最坏情况时间: O(n^2)

如果您可以一个接一个地将元素插入到列表中，您就不必推送这些元素，但是您必须为在列表中搜索适当的位置而“付费”(因此在这个实现中，W.C.T是O(n^2))。

这个问题的解决方案是列表和数组之间的某种协同，这样你就可以在O(1)时间内(如在数组中)到达第i个元素，并在O(1)时间内(如在列表中)将一个新元素推送到给定的位置(比如在索引j之后)--如果你成功了，我相信你将赢得永恒的荣耀！

Answer 2

对插入点进行二进制搜索可以提供略微的改进，主要是通过从向上移动元素的循环中删除键比较。除非您对大量数据进行排序，否则差异不会很大。当然，如果你有一个很大的数据集，你应该使用更好的排序算法...

Answer 3

基本上，插入排序所需的时间由三个因素组成。

1. 遍历源数组中的每个元素
2. 找到正确的位置将其插入目标数组
3. 执行插入。

您正在讨论的内容涉及到步骤2。一种简单的方法是遍历完整的目标数组来查找插入位置，该位置采用O(n)。但是，您可以执行二进制搜索，这只会占用您的O(log(n))。

您仍然需要执行插入操作，但其成本取决于数据结构。如果你使用一个链表，它总是会花费你固定的时间。如果你使用一个简单的数组，你可以只做一个memcpy()，它应该有同样好的伸缩性。您在伪代码中使用的方法是一种非常幼稚的方法，在真正的实现中永远不会有效。有关数组的插入的实际示例，请参见http://www.docjar.com/html/api/java/util/ArrayList.java.html#421。System.arraycopy()是O(1)。