使用插入對幾乎排序的陣列進行排序排序

Question

1. 關於幾乎排序後的數組上的插入排序，它需要線性時間。但是，只有在我們的實現中有一個if條件才能在數組排序後突破循環之後，對嗎？

2. 對於小數據集上的插入排序，爲什麼插入排序更可取？由於comapred到quicksort和mergesort的組合/操作數量較少？

Answer 1

是的，它在幾乎排序後的數組上花費了線性時間，因爲您很早就擺脫了比較循環。一旦將元素插入到正確的位置，就不需要經過排序數組的其餘部分。

我想這是因爲你正在利用關於已排序數組的知識，而在quicksort中，你將每個元素都放到正確的位置，然後對剩餘的元素進行排序。