我已经用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要高得多,所以我想我可能遗漏了一些东西。任何帮助都将不胜感激,提前谢谢你。
2条答案
按热度按时间brc7rcf01#
直接在中的索引处设置值
tmpArray
. 使用slice
将不允许使用与原始数组中相同的索引进行访问。不要在函数中使用全局变量。申报
let
或const
相反这会导致您的sort
函数失败是因为mid
由递归调用更新(因为它是隐式全局的),所以merge
使用错误的参数调用。htrmnn0y2#
我不能说一切都是错的,但这件事马上就跳出来了:
这不是它说的那样。与java一样,它重新分配参数
tmpArr
引用一个新数组。这意味着传入的文件永远不会被修改。如果你想替换
tmpArr
的内容与您列出的内容一样,您需要像在java中那样进行操作(或者使用最终完成相同操作的内置方法,例如tmpArr.length = 0; tmpArr.push(...arr.slice(lo, hi + 1));
).