特殊情況下插入排序的最壞情況比較

Question

考慮一個插入在n個值上使用Sentinel排序，其中每個值在輸入中只出現兩次（所以n必須是偶數）。因此，比較的最佳情況輸入是元素已經排序並且最佳情況下的確切比較次數是n-1。我相信比較的最壞情況輸入是當元素被反向排序時。但在這種情況下，確切的比較次數是多少？爲什麼？

Answer 1

對具有1個元素的數組進行排序。在索引我插入到陣列

for(int i=1 ; i<n ; i++){ 
    int valueForInsert = a[i]; 
    . 
    . 
    . 
} 

爲元件 和Ñ -1元素，我們在最壞的情況下我比較。 so 1 + 2 + 3 + ... +（n - 1）比較發生在反向排序陣列中。 和長度爲n數組公式等於： （ñ *（ñ - 1））/ 2