如果使用雙向鏈表而不是陣列，是否可以提高插入排序演算法的運行時間？
謝謝你。
uj5u.com熱心網友回復：
不，無論如何都不是大 O 意義上的。插入排序有幾種變體，所以讓我們談談串列左側按升序排序而右側未排序的一種。在每次迭代中，我們找到未排序串列中的第一個（最左側）元素，呼叫 that x，然后向后遍歷排序串列以查看該元素所屬的位置。如果串列是一個陣列，我們拉出我們的新元素并將排序串列中的專案向右移動，直到我們找到該專案所屬的位置并將其放在那里。因此，我們遍歷n串列中的專案，對于每個專案，我們遍歷排序串列中的專案，第一次迭代為 0 個專案，下一個為 1 個專案，之后為 2 個專案，......直到n平均而言，我們正在n/2為我們的每個人進行比較/交換n總運行時間的迭代O(n^2)。
如果你把它變成一個雙向鏈表，唯一改變的是，當你遍歷排序串列時，不是將專案向右移動，而是將它們留在原處，然后將新專案放到適當的位置修復串列反而。但它仍然是n/2平均比較和指標取消參考（以查找串列中的下一個節點），因此 big-O 運行時是相同的。在現實生活中它實際上可能更慢，因為指標取消參考可能不是快取友好的，并且需要更多的時間將陣列中的專案向右移動。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/346800.html