合并排序性能与插入排序相比

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的混合稳定排序算法中，以从两者中获得最佳效果。如果感兴趣，请检查一下。