合併排序性能與插入排序相比

Question

對於任何長度大於10的數組，可以肯定地說合並排序在數組元素之間執行的比較次數少於在相同數組上插入排序的次數，因爲運行時間的最佳情況的合併排序是O（N log N），而對於插入排序，它的O（N）？

Answer 1

我承擔這一點。首先，你正在談論比較，但也有物質交換。

在最壞的情況下插入排序你必須做n^2 - n比較和交換（在相反方向排序的陣列）（11^2 - 11 = 121 - 11 = 110，用於11個元件，例如）。但是，如果數組甚至按照需要的順序進行了部分排序（我的意思是許多元素已經停留在正確的位置或甚至離他們不遠），交換次數可能會顯着下降。元素的正確位置很快就會找到，並且不需要執行與按相反順序排序的數組一樣多的操作。所以，正如你所看到的arr2幾乎排序一樣，動作的數量將變成線性的（相對於輸入大小） - 6。

var arr1 = [11,10,9,8,7,6,5,4,3,2,1]; 
 
var arr2 = [1,2,3,4,5,6,7,8,11,10,9]; 
 

 
function InsertionSort(arr) { 
 
    var arr = arr, compNum = 0, swapNum = 0; 
 
    for(var i = 1; i < arr.length; i++) { 
 
     var temp = arr[i], j = i - 1; 
 
     while(j >= 0) { 
 
      if(temp < arr[j]) { arr[j + 1] = arr[j]; swapNum++; } else break; 
 
      j--; 
 
      compNum++; 
 
     } 
 
     arr[j + 1] = temp; 
 
    } 
 
    console.log(arr, "Number of comparisons: " + compNum, "Number of swaps: " + swapNum); 
 
} 
 
InsertionSort(arr1); // worst case, 11^2 - 11 = 110 actions 
 
InsertionSort(arr2); // almost sorted array, few actions

在歸併排序我們總是這樣aprox的。 n*log n動作 - 輸入數組的屬性無關緊要。所以，你可以在這兩種情況下，看到我們會盡快在39個行動我們兩個數組排序：

var arr1 = [11,10,9,8,7,6,5,4,3,2,1]; 
 
var arr2 = [1,2,3,4,5,6,7,8,11,10,9]; 
 
var actions = 0; 
 
function mergesort(arr, left, right) { 
 
    if(left >= right) return; 
 
    var middle = Math.floor((left + right)/2); 
 
    mergesort(arr, left, middle); 
 
    mergesort(arr, middle + 1, right); 
 
    merge(arr, left, middle, right); 
 
} 
 
function merge(arr, left, middle, right) { 
 
    var l = middle - left + 1, r = right - middle, temp_l = [], temp_r = []; 
 
    for(var i = 0; i < l; i++) temp_l[i] = arr[left + i]; 
 
    for(var i = 0; i < r; i++) temp_r[i] = arr[middle + i + 1]; 
 
    var i = 0, j = 0, k = left; 
 
    while(i < l && j < r) { 
 
    if(temp_l[i] <= temp_r[j]) { 
 
    arr[k] = temp_l[i]; i++; 
 
    } else { 
 
    arr[k] = temp_r[j]; j++; 
 
    } 
 
    k++; actions++; 
 
    } 
 
    while(i < l) { arr[k] = temp_l[i]; i++; k++; actions++;} 
 
    while(j < r) { arr[k] = temp_r[j]; j++; k++; actions++;} 
 
} 
 
mergesort(arr1, 0, arr1.length - 1); 
 
console.log(arr1, "Number of actions: " + actions); // 11*log11 = 39 (aprox.) 
 
actions = 0; 
 
mergesort(arr2, 0, arr2.length - 1); 
 
console.log(arr2, "Number of actions: " + actions); // 11*log11 = 39 (aprox.)

所以，回答你的問題：

對於任何長度大於10的數組，可以肯定地說，合併排序在數組元素之間執行的比較次數比插入排序在同一個數組上要少。

我會說不，這樣說是不安全的。在某些情況下，與插入排序相比，合併排序可以執行更多操作。數組的大小在這裏並不重要。在比較插入排序和合並排序的這種特殊情況下，重要的是距排序狀態距離數組有多遠。我希望它可以幫助:)

順便說一句，合併排序和插入排序已經聯合在一個名爲Timsort的混合穩定排序算法中，以從兩者中獲得最佳效果。如果感興趣，請檢查一下。