什麼是最好的算法來排序在圖書館幾乎排序的書籍

Question

如果有一個圖書館所有書籍已經排序，除了只有一本書沒有存儲在它應該是的地方。我應該使用哪種算法以最短的時間對這個庫進行排序？目前我認爲它將與O（nlogn）合併排序。任何比這更快的算法？

Answer 1

1. 找到圖書（索引i）的位置 - 線性掃描
2. j>i一個地方篩所有的書與指數權
3. 將書籍在新的自由空間

這是在O（n）中完成的，數據只有2次通過，並且可以通過將步驟（1）和（2）組合在一起完成而優化爲僅在一次通過中完成。

還要注意：

這基本上是做歸併兩個陣列，（但是具有O（1）額外的空間，該變型）：

1. 原件（排序陣列）
2. 新書（也是大小爲1的排序陣列）

由於array（1） - Original已經排序，所以可以跳過rec ursive調用它，然後直接進入mergesort的合併步驟。

Answer 2

如果您確定它幾乎已排序，那麼插入算法甚至泡泡將是最好的......實際上，合併不會是最好的，因爲它會進行太多的訂單檢查。

看看this gif，它可能會幫助你:)