javascript - 插入排序函数错误

Question

为了做到这一点，插入函数需要通过将大于值的项目向右移动来为值腾出空间。它应该从 rightIndex 开始，并在找到小于或等于 value 的项目或到达数组开头时停止。一旦函数为值腾出了空间，它就可以将值写入数组。

var insert = function(array, rightIndex, value) {
    var key = value;
    for(var i = rightIndex; array[i] > value ; i = i - 1)
    {
        array[rightIndex + 1] = array[rightIndex];
    }
    array[i+1] = value;
};

为什么我输入这个数组后这个函数不能正常工作!

var array = [3, 5, 7, 11, 13, 2, 9, 6];

它显示了这个结果:

insert(array, 4, 2);

2,5,7,11,13,13,9,6

Answer 1

向右移动项目的行需要编辑

更改当前显示的行:

array[rightIndex + 1] = array[rightIndex];

阅读如下:

array[i + 1] = array[i];

在当前编写的代码中，第 rightIndex 项被重复粘贴到第 rightIndex+1 位置。这就是为什么您的结果中会出现两个 13。

所以你的代码已经几乎是正确的了!

显式检查数组的开头

您可以更改 for 循环以确保永远不会超出数组的开头。

for(var i = rightIndex; i>=0 && array[i] > value ; i = i - 1)

插入i>=0 &&意味着当i低于0时，Javascript知道结束循环。否则它将尝试读取未定义的元素array[-1]。幸运的是，测试仍然有效，因为任何数字(甚至负数)与“未定义”的比较都将是错误的。但显式测试这一点比依赖语言的怪癖要好得多。原因是，如果您要在另一种语言中应用相同的算法，array[-1] 可能会出错。