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

Question

while循环使用线性搜索向后扫描.但是,我们知道while循环中的数组已经排序.因此,我们可以用二进制搜索替换线性搜索,以便O(n)将变为O(lg n).但是,我对此的看法是它不会有助于减少总体时间,因为我们仍然需要将元素向前移动一个索引,这将始终采用(向后步骤数(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

insert sort推送数组的元素,以便将空格释放到行中的下一个元素.
因此,如果您使用二进制搜索找到输入新元素的位置,您仍需要将该索引之后的所有元素向前推进一步(向右).
所以给定一个向后排序的数组:10,9,8,7,6,5,4,3,2,1
你需要让i-1向右推动才能插入第i个元素(即使你使用二进制搜索) - 最坏的情况时间:O(n ^ 2)
如果你可以逐个插入元素到一个你不必推送元素的列表,但你必须"支付"搜索列表中的正确位置(因此在此实现中WCT为O(n ^ 2)).

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