在插入排序過程中，在16個元素的數組中會發生多少次比較？

我試圖瞭解當我們嘗試實現插入排序時總共會出現多少次比較。我知道它是如何工作的，它比較前兩個數字，然後是前三個數字，依此類推。當這個數組按順序排列並且顛倒順序時，比較次數會有什麼不同？在插入排序過程中，在16個元素的數組中會發生多少次比較？

爲什麼不通過逐步增大紙張的算法流程來幫助自己理解和可視化結果？我敢打賭，你已經知道它在16歲之前是如何擴展的。 – doynax

https://en.wikipedia.org/wiki/Insertion_sort - 請參閱右上方的圖形表示方塊，並閱讀該圖像下方的文本。 –

假定最壞情況的順序，每一步的比較數是1,2,3，... n-1，並且比較的總數是（n-1）（n）/ 2 =（ n^2 -n）/ 2。

2016-03-10 01:51:36 rcgldr

回答