我的合并排序函数在java中工作,但在javascript中不工作,我缺少什么?

7qhs6swi  于 2021-08-20  发布在  Java
关注(0)|答案(2)|浏览(344)

我已经用java实现了合并排序,它似乎工作正常。为了创建合并排序算法的可视化表示,我尝试将这段代码转换为javascript,但我无法让这段代码正常工作。
以下是我的java实现的代码:
'''

  1. public class MergeSort {
  2. public void merge(int[] arr, int[] tmpArr, int lo, int mid, int hi) {
  3. for (int k = lo; k <= hi; k++) { // first we copy over the array to our tmp array
  4. tmpArr[k] = arr[k];
  5. }
  6. int left = lo; // keeps index of left side of tmp array
  7. int right = mid + 1; // keeps index of right side of tmp array
  8. for (int l = lo; l <= hi; l++) { // l keeps the index of the sorted array
  9. if (left > mid) { // will merge remaining values in right side of array
  10. arr[l] = tmpArr[right];
  11. right++;
  12. } else if (right > hi) { // will merge remaining values in left side of array
  13. arr[l] = tmpArr[left];
  14. left++;
  15. } else if (tmpArr[left] < tmpArr[right]) { // checks if value in left array is less than value in right array
  16. arr[l] = tmpArr[left];
  17. left++;
  18. } else {
  19. arr[l] = tmpArr[right];
  20. right++;
  21. }
  22. }
  23. }
  24. public void sort(int[] arr) {
  25. int[] tmpArr = new int[arr.length];
  26. sort(arr, tmpArr, 0, arr.length - 1);
  27. }
  28. public void sort(int[] arr, int[] tmpArr, int lo, int hi) {
  29. if (lo >= hi) {
  30. return;
  31. }
  32. int mid = lo + ((hi - lo) / 2);
  33. sort(arr, tmpArr, lo, mid);
  34. sort(arr, tmpArr, mid + 1, hi);
  35. merge(arr, tmpArr, lo, mid, hi);
  36. }
  37. }

'''
以下是我的javascript实现:
'''

  1. function merge(arr, tmpArr, lo, mid, hi) {
  2. tmpArr = arr.slice(lo, hi + 1); // copy array over to tmp array
  3. left = lo; // keeps index of left side of tmp array
  4. right = mid + 1; // keeps index of right side of tmp array
  5. for (index = lo; index <= hi; index++) { // index keeps the index of the sorted array
  6. if (left > mid) { // will merge remaining values in right side of array
  7. arr[index] = tmpArr[right];
  8. right++;
  9. } else if (right > hi) { // will merge remaining values in left side of array
  10. arr[index] = tmpArr[left];
  11. left++;
  12. } else if (tmpArr[left] < tmpArr[right]) { // checks if value in left array is less than value in right array
  13. arr[index] = tmpArr[left];
  14. left++;
  15. } else if (tmpArr[right] < tmpArr[left]) {
  16. arr[index] = tmpArr[right];
  17. right++;
  18. }
  19. }
  20. }
  21. function sort(arr, tmpArr, lo, hi) {
  22. if (lo >= hi) { // gets rid of edge case where array has 1 element
  23. return;
  24. }
  25. mid = Math.floor(lo + ((hi - lo) / 2));
  26. sort(arr, tmpArr, lo, mid);
  27. sort(arr, tmpArr, (mid + 1), hi);
  28. merge(arr, tmpArr, lo, mid, hi);
  29. }
  30. function mergeSort(arr) {
  31. tmpArr = [];
  32. sort(arr, tmpArr, 0, arr.length - 1);
  33. }

'''
我花了几个小时来调整这段代码,并在代码中插入print语句,但我似乎不明白为什么它可以在java而不是javascript中工作。我对java的精通程度比javascript要高得多,所以我想我可能遗漏了一些东西。任何帮助都将不胜感激,提前谢谢你。

brc7rcf0

brc7rcf01#

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

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

不要在函数中使用全局变量。申报 letconst 相反这会导致您的 sort 函数失败是因为 mid 由递归调用更新(因为它是隐式全局的),所以 merge 使用错误的参数调用。

  1. function sort(arr, tmpArr, lo, hi) {
  2. if (lo >= hi) {
  3. return;
  4. }
  5. let mid = lo + Math.floor((hi - lo) / 2);
  6. sort(arr, tmpArr, lo, mid);
  7. sort(arr, tmpArr, mid + 1, hi);
  8. merge(arr, tmpArr, lo, mid, hi);
  9. }
  1. function merge(arr, tmpArr, lo, mid, hi) {
  2. for (let k = lo; k <= hi; k++) {
  3. tmpArr[k] = arr[k];
  4. }
  5. let left = lo; // keeps index of left side of tmp array
  6. let right = mid + 1; // keeps index of right side of tmp array
  7. for (let l = lo; l <= hi; l++) { // l keeps the index of the sorted array
  8. if (left > mid) { // will merge remaining values in right side of array
  9. arr[l] = tmpArr[right];
  10. right++;
  11. } else if (right > hi) { // will merge remaining values in left side of array
  12. arr[l] = tmpArr[left];
  13. left++;
  14. } else if (tmpArr[left] < tmpArr[right]) { // checks if value in left array is less than value in right array
  15. arr[l] = tmpArr[left];
  16. left++;
  17. } else {
  18. arr[l] = tmpArr[right];
  19. right++;
  20. }
  21. }
  22. }
  23. function mergeSort(arr) {
  24. tmpArr = [];
  25. sort(arr, tmpArr, 0, arr.length - 1);
  26. }
  27. function sort(arr, tmpArr, lo, hi) {
  28. if (lo >= hi) {
  29. return;
  30. }
  31. let mid = lo + Math.floor((hi - lo) / 2);
  32. sort(arr, tmpArr, lo, mid);
  33. sort(arr, tmpArr, mid + 1, hi);
  34. merge(arr, tmpArr, lo, mid, hi);
  35. }
  36. let arr = [3, -1, 5, 6, 8, 2, 2, 1];
  37. mergeSort(arr);
  38. console.log(arr);
展开查看全部
htrmnn0y

htrmnn0y2#

我不能说一切都是错的,但这件事马上就跳出来了:

  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)); ).

相关问题