Heapsort 在 Javascript 中不工作
Heapsort not working in Javascript
我正在尝试在 Javascript 中实现堆排序,但在 array.length - 2
处有一个 undefined
元素,并且索引 0 处的元素未排序。
这是代码:
var heapSort = function(array) {
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var maxHeap = function(array, i) {
var l = 2 * i;
var r = l + 1;
var largest;
if (l <= array.heapSize && array[l] > array[i]) {
largest = l;
} else {
largest = i;
}
if (r <= array.heapSize && array[r] > array[largest]) {
largest = r;
}
if (largest != i) {
swap(array, i, largest);
maxHeap(array, largest);
}
};
var buildHeap = function(array) {
array.heapSize = array.length;
for (var i = Math.floor(array.length / 2); i >= 1; i--) {
maxHeap(array, i);
}
};
buildHeap(array);
for (var i = array.length; i >= 2; i--) {
swap(array, 1, i);
array.heapSize--;
maxHeap(array, 1);
}
};
var a = [55, 67, 10, 34, 25, 523, 1, -2];
heapSort(a);
document.getElementById("getHeapSort").innerHTML = a;
* {
font-family: Arial, sans-serif;
}
<p id="getHeapSort"></p>
我认为 array[i] == undefined
当 i = array.length
。我尝试修复此 (setting i = array.length - 1
),但数组以完全不同的顺序出现。我还认为 0 从未被交换,因为 i 总是大于 0。我再次尝试,并且数组以完全不同的顺序出现。
您在 JavaScript 中使用基于 1 的索引而不是基于 0 的索引。为了您的方便,我还添加了一个跟踪。
试试这个:
var heapSort = function(array) {
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var maxHeap = function(array, i) {
var l = 2 * i;
var r = l + 1;
var largest;
if (l < array.heapSize && array[l] > array[i]) {
largest = l;
} else {
largest = i;
}
if (r < array.heapSize && array[r] > array[largest]) {
largest = r;
}
if (largest != i) {
swap(array, i, largest);
maxHeap(array, largest);
}
};
var buildHeap = function(array) {
array.heapSize = array.length;
for (var i = Math.floor(array.length / 2); i >= 0; i--) {
maxHeap(array, i);
}
};
buildHeap(array);
for (var i = array.length-1; i >= 1; i--) {
swap(array, 0, i);
array.heapSize--;
maxHeap(array, 0);
document.getElementById("getHeapSort").innerHTML = document.getElementById("getHeapSort").innerHTML + a + "<br>";
}
};
var a = [55, 67, 10, 34, 25, 523, 1, -2];
document.getElementById("getHeapSort").innerHTML = a + "<br>";
heapSort(a);
这是一个 JFiddle:http://jsfiddle.net/mbL5enL5/1/
我正在尝试在 Javascript 中实现堆排序,但在 array.length - 2
处有一个 undefined
元素,并且索引 0 处的元素未排序。
这是代码:
var heapSort = function(array) {
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var maxHeap = function(array, i) {
var l = 2 * i;
var r = l + 1;
var largest;
if (l <= array.heapSize && array[l] > array[i]) {
largest = l;
} else {
largest = i;
}
if (r <= array.heapSize && array[r] > array[largest]) {
largest = r;
}
if (largest != i) {
swap(array, i, largest);
maxHeap(array, largest);
}
};
var buildHeap = function(array) {
array.heapSize = array.length;
for (var i = Math.floor(array.length / 2); i >= 1; i--) {
maxHeap(array, i);
}
};
buildHeap(array);
for (var i = array.length; i >= 2; i--) {
swap(array, 1, i);
array.heapSize--;
maxHeap(array, 1);
}
};
var a = [55, 67, 10, 34, 25, 523, 1, -2];
heapSort(a);
document.getElementById("getHeapSort").innerHTML = a;
* {
font-family: Arial, sans-serif;
}
<p id="getHeapSort"></p>
我认为 array[i] == undefined
当 i = array.length
。我尝试修复此 (setting i = array.length - 1
),但数组以完全不同的顺序出现。我还认为 0 从未被交换,因为 i 总是大于 0。我再次尝试,并且数组以完全不同的顺序出现。
您在 JavaScript 中使用基于 1 的索引而不是基于 0 的索引。为了您的方便,我还添加了一个跟踪。
试试这个:
var heapSort = function(array) {
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var maxHeap = function(array, i) {
var l = 2 * i;
var r = l + 1;
var largest;
if (l < array.heapSize && array[l] > array[i]) {
largest = l;
} else {
largest = i;
}
if (r < array.heapSize && array[r] > array[largest]) {
largest = r;
}
if (largest != i) {
swap(array, i, largest);
maxHeap(array, largest);
}
};
var buildHeap = function(array) {
array.heapSize = array.length;
for (var i = Math.floor(array.length / 2); i >= 0; i--) {
maxHeap(array, i);
}
};
buildHeap(array);
for (var i = array.length-1; i >= 1; i--) {
swap(array, 0, i);
array.heapSize--;
maxHeap(array, 0);
document.getElementById("getHeapSort").innerHTML = document.getElementById("getHeapSort").innerHTML + a + "<br>";
}
};
var a = [55, 67, 10, 34, 25, 523, 1, -2];
document.getElementById("getHeapSort").innerHTML = a + "<br>";
heapSort(a);
这是一个 JFiddle:http://jsfiddle.net/mbL5enL5/1/