文章/答案/技术大牛

发布

社区首页 >问答首页 >JavaScript中外壳排序实现中的无限循环

问JavaScript中外壳排序实现中的无限循环
EN

Stack Overflow用户

提问于 2020-04-23 08:28:26

回答 1查看 62关注 0票数 1

我目前正在阅读Algorithms, 4th Edition by Robert Sedgewick的第四版，其中作者提供了shell sort的实现。我试图理解为什么这个实现在JavaScript中不起作用。尽管我能够对排序后的数组执行console.log操作，但程序似乎从未停止运行，它变成了一个无限循环。

 public class Shell
  {
     public static void sort(Comparable[] a)
     {  // Sort a[] into increasing order.
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
        while (h >= 1)
        {  // h-sort the array.
           for (int i = h; i < N; i++)
           {  // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
              for (int j = i; j >= h && less(a[j], a[j-h]); j -= h)
                 exch(a, j, j-h);
           }
           h = h/3; }
         }
     // See page 245 for less(), exch(), isSorted(), and main().
}

上面是用Java实现的。注意第一个循环while (h < N/3) h = 3*h + 1;没有{}的左大括号或右大括号，这是不是意味着它会一直运行到最后？

下面是我在JavaScript中的实现：

function shellSort(a) {
  let N = a.length;
  let h = 1;

  while (h < N/3) {
    h = 3 * h + 1

    while (h >= 1) 
    {
      for (let i = h; i < N; i++) 
      {
        for (let j = i; j >= h && a[j] < a[j - h]; j -= h){
        let temp = a[j - h]
          a[j - h] = a[j]
          a[j] = temp
        }
      }
      console.log(a)
      h = h/3
    }
  }
}

console.log(shellSort([7,11,3,6,2,5,9,8,1,10]))

当我记录输出时，我得到了排序数组，但我不知道无限循环是从哪里来的。当您运行代码时，这是输出到终端的内容：

  7, 8, 9, 10, 11
]
[
  1, 2, 3,  5,  6,
  7, 8, 9, 10, 11
]
[
  1, 2, 3,  5,  6,
  7, 8, 9, 10, 11
]
[
  1, 2, 3,  5,  6,
  7, 8, 9, 10, 11
]

有什么问题吗？我试着在h/3中添加一个Math.floor，但是没有成功。我哪里搞错了？

javascript

java

algorithm

sorting

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-04-23 09:46:50

在Java中，and integer除以整数仍然是整数：

int x = 5;
int y = x / 3;
// prints "1"
System.out.println(y);

然而，在Javascript中，没有整数，一切都是一个数字。然后,

let x = 5;
let y = x / 3;
// prints "1.6666666666666"
console.log(y);

您的算法要求h为整数，否则很难将其用作数组索引。您必须显式地将其转换为整数。固定的Javascript实现：

function shellSort(a) {
  let N = a.length;
  let h = 1;

  while (h < N / 3) {
    h = 3 * h + 1;
  }


  while (h >= 1) {
    for (let i = h; i < N; i++) {
      for (let j = i; j >= h && a[j] < a[j - h]; j -= h) {
        let temp = a[j - h]
        a[j - h] = a[j]
        a[j] = temp
      }
    }
    // parseInt here is key
    h = parseInt(h / 3)
  }

}
console.log(shellSort([7, 11, 3, 6, 2, 5, 9, 8, 1, 10]))

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/61377337

复制

相似问题

问JavaScript中外壳排序实现中的无限循环
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问JavaScript中外壳排序实现中的无限循环EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问JavaScript中外壳排序实现中的无限循环
EN