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

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的数组，是否可以安全地说，合并排序在数组元素之间的比较比在同一数组上进行插入排序的要少

我会说不，这样说是不安全的。在某些情况下，与插入排序相比，合并排序可以执行更多的操作。数组的大小在这里并不重要。在比较插入排序与合并排序的特殊情况下，重要的是您的数组离排序状态有多远。我希望它有帮助:)

顺便说一句，合并排序和插入排序被统一在一个名为蒂姆塞德的混合稳定排序算法中，以获得两者的最佳效果。如果有兴趣的话去看看。