插入排序函数错误

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'th 项被重复粘贴到 rightIndex+1'th 位置。13这就是为什么你的结果中有两个s 。

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

显式检查数组的开头

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

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

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