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
最佳答案
插入排序插入数组的元素，以便为行中的下一个元素释放空间。
因此，如果您使用二分查找找到输入新元素的位置，您仍然需要将该索引之后的所有元素向前推一步(向右)。
所以给定一个向后排序的数组:10,9,8,7,6,5,4,3,2,1
您需要向右推 i-1 次才能插入第 i 个元素(即使您使用二分查找)——最坏情况时间:O(n^2)
如果您可以将元素一个接一个地插入到列表中，则不必推送元素，但您必须“付费”以搜索列表中的正确位置(因此在此实现中 W.C.T 是 O (n^2))。
这个问题的解决方案是列表和数组之间的某种协同作用，这样你就可以在 O(1) 时间内到达第 i 个元素(就像在数组中一样)，并且可以将一个新元素推送到给定位置(在 O(1) 时间(如列表)中在索引 j) 之后说 - 如果你成功了，我相信你会赢得永恒的荣耀!
关于algorithm - 使用二进制搜索改进插入排序的最坏情况运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9467731/