使用插入計數比較排序

Question

我負責計數排序數組時的總比較。 給定整數數組{8,2,1,4,3,5}，我從左邊的第二個元素開始，將它與第一個元素進行比較，切換它們，然後將第三個元素與前兩個元素進行比較，以及等等，以確定每個元素應該位於何處。

我計算總共15次比較，但正確的比較計數是10. 我知道通過選擇排序來排序數組是15次比較，所以在此插入排序時如何以及爲什麼比較計數有所不同例？

Answer 1

您對插入排序工作的理解是錯誤的。

使用此僞代碼用於插入排序：

mark first element as sorted 
for each unsorted element 
    'extract' the element 
    for i = lastSortedIndex to 0 
    if currentSortedElement > extractedElement 
     move sorted element to the right by 1 
    else: insert extracted element 

初始陣列：[8, 2, 1, 4, 3, 5]

比較例1：2 < 8陣列：[2, 8, 1, 4, 3, 5]

比較例2：1 < 8陣列：[2, 1, 8, 4, 3, 5]

比較3：1 < 2陣列：[1, 2, 8, 4, 3, 5]

比較例4：4 < 8陣列：[1, 2, 4, 8, 3, 5]

比較例5：4 > 2陣列：[1, 2, 4, 8, 3, 5]

比較例6：3 < 8陣列：[1, 2, 4, 3, 8, 5]

比較例7：3 < 4陣列：[1, 2, 3, 4, 8, 5]

比較8：3 > 2陣列：[1, 2, 3, 4, 8, 5]

比例9：5 < 8陣列：[1, 2, 3, 4, 5, 8]

比例10：5 > 4陣列：[1, 2, 3, 4, 5, 8]

排序！