插入排序函数错误

Question

为此，插入函数需要通过将大于 value 的项目向右移动来为 value 腾出空间。它应该从 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]。幸运的是，测试仍然有效，因为任何数字（甚至是负数）与 "undefined" 的比较都是错误的。但是明确地对此进行测试而不是依赖语言的怪癖是更好的风格。原因是如果您要在另一种语言中应用相同的算法，array[-1] 可能会出错。

Answer 2

将值插入数组可以正确处理已排序的数组，在这种情况下，您的数组未排序。

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

你需要先对数组进行排序，为此使用这个

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

array = arra.sort(function (a, b) {  return a - b;  });

array = array.sort((a, b) => a - b);

//outputs:  2, 3, 5, 6 , 7, 9, 11, 13

然后你可以按排序插入这个数组

为此你可以尝试这样的事情

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

function insert(element, array) {
   array.push(element);

   array.sort(function(a, b) {
       return a - b;
   });

   return array;
}


//outputs:  2, 2, 3, 5, 6 , 7, 9, 11, 13

插入排序函数错误

Insertion Sort Function Error

javascript

arrays

insertion-sort

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

明确检查数组的开头