迭代地实现合并排序 [英] Implementing merge sort iteratively

问题描述

我正在尝试实现合并排序，以便更好地了解它的工作方式.在下面的代码中，我尝试对数字数组进行排序.我目前拥有的代码有错误，并且在无限循环中运行.我现在正尝试以非递归方式解决此问题:

I'm trying to implement merge sort in order to get a better understanding of how it works. In the following code I am attempting to sort an array of numbers. The code I currently have is buggy and runs in an infinite loop. I'm trying to solve this non-recursively for now:

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].

So if I have an array var nums = [1, 4, 10, 2, 9, 3]; calling mergeSort(nums) should return [1, 2, 3, 4, 9, 10].

推荐答案

您已编写了将数组拆分为两个并合并两半的代码.这不会导致排序数组，因为这两个半部分没有排序. Mergesort的工作方式是将两个半部分排序，然后将它们合并.

You've written code that splits an array in two and merges the halves. This doesn't result in a sorted array because the two halves are not sorted. Mergesort works by sorting the two halves, then merging them.

有很多方法可以迭代地实现mergesort.我提供一个.首先合并大小为1的子数组.您知道大小为1的数组已经排序，因此可以安全合并两个大小为1的连续子数组.如果对原始数组中所有大小为1的子对连续数组进行合并，您最终得到一个由大小为2的连续排序子数组组成的数组.

There are many ways to implement mergesort iteratively. Let me offer one. Start by merging subarrays of size 1. You know that an array of size 1 is already sorted, so it's safe to merge two consecutive subarrays of size 1. If you do this to all consecutive pairs of subarrays of size 1 in the original array, you end up with an array consisting of consecutive sorted subarrays of size 2.

你知道这是怎么回事吗?现在，您可以合并大小为2的每两个连续的子数组.最后得到大小为4的连续排序的子数组的数组.继续重复此过程，直到对整个数组进行排序.

Do you see where this is going? Now you can merge every two consecutive subarrays of size 2. You end up with an array of consecutive sorted subarrays of size 4. Keep on repeating this procedure until the whole array is sorted.

以下代码段实现了这种方法.

The following snippet implements this approach.

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(', '));

这篇关于迭代地实现合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！