插入排序最坏的情况 [英] Insertion sort worst case

问题描述

为什么插入排序n ^ 2最坏的情况?可以用二进制搜索进行nlogn吗?最小化位置搜索到log(n)，然后使用像memmove这样的低级函数来最小化交换?

Why is the worst case for insertion sort n^2? Can it be nlogn with binary search? Minimize the location search to log(n) and then use a low level function like memmove to minimize swaps?

推荐答案

可以使用二进制搜索进行登录吗?

您需要先对数组进行排序才能使用二进制搜索，因为二进制搜索只能在已排序的数组中进行

You will need to sort the array first to use binary search, as binary search is only possible in sorted array

修改 即使数组的第一部分已排序.现在的情况是，您找到了要在登录步骤中插入的位置.然后，您实际上需要在其中插入值.为此，在最坏的情况下，您需要将所有元素向右移动，需要n步.

Edit Even if the first part of the array is sorted. The case now is that, you find the position to insert in logn steps. Then You actually need to insert the value there. For that you will need to move all the elements to right requiring n steps at worst case.

这篇关于插入排序最坏的情况的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！