迭代地实现归并排序

Implementing merge sort iteratively

本文关键字：归并排序 实现 迭代      更新时间：2023-09-26

我试图实现归并排序，以便更好地理解它是如何工作的。在下面的代码中，我试图对数字数组进行排序。我目前拥有的代码是错误的，并在无限循环中运行。我现在正试图用非递归的方式解决这个问题:

function mergeSort(arr) {
  var mid = Math.floor(arr.length/2);
  var left = arr.slice(0, mid);
  var right = arr.slice(mid, arr.length);
  if (arr.length === 1) {return arr};
  var sorted = [];
  var i = 0;
  while (left.length || right.length) {
   if (left.length && right.length) {
     if (left[0] < right[0]) {
       sorted.push(left.shift())
     } else {
       sorted.push(right.shift())
     }
   } else if (left) {
     sorted.push(left.shift())
   } else {
     sorted.push(right.shift())
   }
   i++;
  }
  return sorted;
}

如果我有一个数组var nums = [1, 4, 10, 2, 9, 3];调用mergeSort(nums)应该返回[1, 2, 3, 4, 9, 10]

您已经编写了将数组分成两部分并将其合并的代码。这不会产生一个排序的数组，因为这两部分没有排序。合并排序的工作原理是对两部分进行排序，然后合并它们。

有许多方法可以迭代地实现归并排序。我来举个例子。首先合并大小为1的子数组。您知道大小为1的数组已经排序，因此合并两个大小为1的连续子数组是安全的。如果对原始数组中所有大小为1的连续子数组对执行此操作，则最终得到一个由大小为2的连续排序子数组组成的数组。

你知道这是怎么回事吗?现在可以合并两个大小为2的连续子数组。最终得到一个大小为4的连续排序子数组。继续重复这个过程，直到整个数组排序完毕。

下面的代码片段实现了这种方法。 

function mergeSort(arr) {
  var sorted = arr.slice(),
      n = sorted.length,
      buffer = new Array(n);
  for (var size = 1; size < n; size *= 2) {
    for (var leftStart = 0; leftStart < n; leftStart += 2*size) {
      var left = leftStart,
          right = Math.min(left + size, n),
          leftLimit = right,
          rightLimit = Math.min(right + size, n),
          i = left;
      while (left < leftLimit && right < rightLimit) {
        if (sorted[left] <= sorted[right]) {
          buffer[i++] = sorted[left++];
        } else {
          buffer[i++] = sorted[right++];
        }
      }
      while (left < leftLimit) {
        buffer[i++] = sorted[left++];
      }
      while (right < rightLimit) {
        buffer[i++] = sorted[right++];
      }
    }
    var temp = sorted,
        sorted = buffer,
        buffer = temp;
  }
  return sorted;
}
function print(s) {
  document.write(s + '<br />');
}
var data = [1, 4, 10, 2, 9, 3];
print('input: ' + data.join(', '));
print('output: ' + mergeSort(data).join(', '));

相关文章：