我正在尝试实现合并排序，以便更好地理解它是如何工作的。在下面的代码中，我尝试对数字数组进行排序。我目前拥有的代码有错误并且在无限循环中运行。我现在正在尝试以非递归方式解决这个问题：
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(', '));
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
