我的合并排序函数在Java中工作，但在JavaScript中不工作，我缺少什么

Question

我已经在Java中实现了合并排序，它似乎工作正常。为了创建合并排序算法的可视化表示，我试图将这些代码转移到JavaScript中，但我无法使相同的代码发挥作用。

以下是我的Java实现的代码：

''

public class MergeSort {
public void merge(int[] arr, int[] tmpArr, int lo, int mid, int hi) {
for (int k = lo; k <= hi; k++) {  // first we copy over the array to our tmp array
tmpArr[k] = arr[k];
}
int left = lo;         // keeps index of left side of tmp array
int right = mid + 1;    // keeps index of right side of tmp array
for (int l = lo; l <= hi; l++) {  // l keeps the index of the sorted array
if (left > mid) {               // will merge remaining values in right side of array
arr[l] = tmpArr[right];
right++;
} else if (right > hi) {         // will merge remaining values in left side of array
arr[l] = tmpArr[left];
left++;
} else if (tmpArr[left] < tmpArr[right]) {  // checks if value in left array is less than value in right array
arr[l] = tmpArr[left];
left++;
} else {
arr[l] = tmpArr[right];
right++;
}
}
}
public void sort(int[] arr) {
int[] tmpArr = new int[arr.length];
sort(arr, tmpArr, 0, arr.length - 1);
}
public void sort(int[] arr, int[] tmpArr, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = lo + ((hi - lo) / 2);
sort(arr, tmpArr, lo, mid);
sort(arr, tmpArr, mid + 1, hi);
merge(arr, tmpArr, lo, mid, hi);
}
}

''

这是我的JavaScript实现：

''

function merge(arr, tmpArr, lo, mid, hi) {
tmpArr = arr.slice(lo, hi + 1); // copy array over to tmp array
left = lo; // keeps index of left side of tmp array
right = mid + 1; // keeps index of right side of tmp array
for (index = lo; index <= hi; index++) { // index keeps the index of the sorted array
if (left > mid) { // will merge remaining values in right side of array
arr[index] = tmpArr[right];
right++;
} else if (right > hi) { // will merge remaining values in left side of array
arr[index] = tmpArr[left];
left++;
} else if (tmpArr[left] < tmpArr[right]) { // checks if value in left array is less than value in right array
arr[index] = tmpArr[left];
left++;
} else if (tmpArr[right] < tmpArr[left]) {
arr[index] = tmpArr[right];
right++;
}
}
}
function sort(arr, tmpArr, lo, hi) {
if (lo >= hi) { // gets rid of edge case where array has 1 element
return;
}
mid = Math.floor(lo + ((hi - lo) / 2));
sort(arr, tmpArr, lo, mid);
sort(arr, tmpArr, (mid + 1), hi);
merge(arr, tmpArr, lo, mid, hi);
}
function mergeSort(arr) {
tmpArr = [];
sort(arr, tmpArr, 0, arr.length - 1);
}

''

我花了几个小时来调整这段代码，并在代码中插入print语句，但我似乎不明白为什么它能在Java中工作，而不能在JavaScript中工作。我对Java比JavaScript更精通，所以我想我可能错过了什么。如有任何帮助，我们将不胜感激，提前感谢。

Answer 1

我不能说一切都错了，但这一点很快就跳了出来：

tmpArr = arr.slice(lo, hi + 1); // copy array over to tmp array

这并不像它说的那样。与Java一样，它重新分配参数tmpArr以引用新数组。这意味着传递的那个永远不会被修改。

如果你想用你列出的内容替换tmpArr的内容，你需要用Java中的方法(或者用内置的方法，比如tmpArr.length = 0; tmpArr.push(...arr.slice(lo, hi + 1));(。

Answer 2

1. 直接在tmpArray中的索引处设置值。使用slice将不允许使用与原始数组中相同的索引进行访问

for(let i = lo; i <= hi; i++) tmpArr[i] = arr[i];

2. 不要在函数中使用全局变量。请改用let或const声明它们。这会导致sort函数失败，因为mid是由递归调用更新的(因为它是隐式全局的(，所以merge会使用错误的参数进行调用

function sort(arr, tmpArr, lo, hi) {
if (lo >= hi) {
return;
}
let mid = lo + Math.floor((hi - lo) / 2);
sort(arr, tmpArr, lo, mid);
sort(arr, tmpArr, mid + 1, hi);
merge(arr, tmpArr, lo, mid, hi);
}

function merge(arr, tmpArr, lo, mid, hi) {
for (let k = lo; k <= hi; k++) {
tmpArr[k] = arr[k];
}
let left = lo;         // keeps index of left side of tmp array
let right = mid + 1;    // keeps index of right side of tmp array
for (let l = lo; l <= hi; l++) {  // l keeps the index of the sorted array
if (left > mid) {               // will merge remaining values in right side of array
arr[l] = tmpArr[right];
right++;
} else if (right > hi) {         // will merge remaining values in left side of array
arr[l] = tmpArr[left];
left++;
} else if (tmpArr[left] < tmpArr[right]) {  // checks if value in left array is less than value in right array
arr[l] = tmpArr[left];
left++;
} else {
arr[l] = tmpArr[right];
right++;
}
}
}
function mergeSort(arr) {
tmpArr = [];
sort(arr, tmpArr, 0, arr.length - 1);
}
function sort(arr, tmpArr, lo, hi) {
if (lo >= hi) {
return;
}
let mid = lo + Math.floor((hi - lo) / 2);
sort(arr, tmpArr, lo, mid);
sort(arr, tmpArr, mid + 1, hi);
merge(arr, tmpArr, lo, mid, hi);
}
let arr = [3, -1, 5, 6, 8, 2, 2, 1];
mergeSort(arr);
console.log(arr);