可汗学院:JavaScript 循环耗时太长
Khan academy: JavaScript loop taking too long
我正在阅读有关算法的可汗学院课程。我在 https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/p/challenge-implement-insertion-sort。到目前为止我有:
var insert = function(array, rightIndex, value) {
for(var j = rightIndex;
j >= 0 && array[j] > value;
j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
var insertionSort = function(array) {
for(var i= 1; i < array.length ; i++ ) {
insert(array, i ,array[i+1] );
}
};
var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);
您可以在屏幕截图中看到似乎是问题所在的代码行,但我觉得没问题。我做错了什么?
您在 i
处开始 rightIndex
并移动值 array[i + 1]
,但 i
到达 array.length
并且 insert
开始通过将元素设置为 rightIndex + 1
。这将导致数组增长。
移动当前元素并改为从上一个索引开始:
for (var i = 1; i < array.length; i++) {
insert(array, i - 1,array[i]);
}
调试时捕获此问题的一种方法是密封您的数组,使其无法增长:
var array = Object.seal([22, 11, 99, 88, 9, 7, 42]);
不过这只适用于 strict mode。 如果你处于马虎模式,它只会隐藏错误。
我正在阅读有关算法的可汗学院课程。我在 https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort/p/challenge-implement-insertion-sort。到目前为止我有:
var insert = function(array, rightIndex, value) {
for(var j = rightIndex;
j >= 0 && array[j] > value;
j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
};
var insertionSort = function(array) {
for(var i= 1; i < array.length ; i++ ) {
insert(array, i ,array[i+1] );
}
};
var array = [22, 11, 99, 88, 9, 7, 42];
insertionSort(array);
您可以在屏幕截图中看到似乎是问题所在的代码行,但我觉得没问题。我做错了什么?
您在 i
处开始 rightIndex
并移动值 array[i + 1]
,但 i
到达 array.length
并且 insert
开始通过将元素设置为 rightIndex + 1
。这将导致数组增长。
移动当前元素并改为从上一个索引开始:
for (var i = 1; i < array.length; i++) {
insert(array, i - 1,array[i]);
}
调试时捕获此问题的一种方法是密封您的数组,使其无法增长:
var array = Object.seal([22, 11, 99, 88, 9, 7, 42]);
不过这只适用于 strict mode。 如果你处于马虎模式,它只会隐藏错误。