javascript - JavaScript中shell排序实现中的无限循环
问题描述
Algorithms, 4th Edition by Robert Sedgewick
我目前正在阅读作者实现 shell 排序的第四版。我试图理解为什么这个实现在 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
]
问题是什么?我尝试添加一个Math.floor
to h/3
但没有运气。我做错了什么?
解决方案
在 Java 中,整数除以整数仍然是整数:
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]))
推荐阅读
- angularjs - Django Rest Framework中的会话用户注销
- java - 使用 File 对象在 Android(API > 24)中捕获和保存视频?
- php - 如何显示当前登录 CodeIgniter 的数据用户
- reactjs - 单选按钮如何在反应索环中按行顺序(男性和女性)?
- wordpress - 从管理员会员面板捕获更新会员状态挂钩
- sql - 如果先前的联接为空,则有条件的左联接
- java - Java递归循环
- unix - 编辑 .gz 文件的第一行
- python - Python 脚本随机暂停,直到按下回车键
- docker - 为什么 docker 不缓存 'ENV SHELL /bin/bash'?