爲什麼插入排序數組O（n）？

Question

Skiena在「算法設計手冊」中指出插入到排序數組中的是O（n）。然而，在一個有序數組中搜索一個項目是O（log n），因爲你可以進行二分搜索。

無法插入也是O（日誌n），如果我做了二進制搜索比較，找出它應該去哪裏數組？

Answer 1

找到位置只是戰鬥的一半。告訴我如何使用少於五次的移動操作將2置於[1,3,4,5,6,7]中。

Answer 2

您可以對已排序的數組執行O（log n）搜索，但是當插入一個項目時需要移位數據，所以移位爲O（n）。

Answer 3

您可以使用二進制搜索找出元素應該去的地方。 但是，插入元素意味着您必須爲其騰出空間。這是通過將新元素之後的所有元素移動到右側來完成的。這需要O（n）的複雜性。