我已经在 javascript 中实现了一组排序算法,用于训练目的。除了堆排序之外,我的实现已经成功地对整数和单字符字符串数组进行了排序。
我的实现对数组进行了正确排序,但在返回排序后的数组时将最小的数字放在末尾除外。
我不是 CS 学生/毕业生,也没有很多编程背景。我正在通过 read/try/fail 方法学习,但我无法使其正常工作。
我会将代码及其结果放在本段下方。最后,我想补充一点,我正在使用 this Wikipedia article 处的伪代码。作为我实现的引用。
function heapSort(intl)
{
var l = intl.length,
end = l - 1,
swap;
intl = _heapify(intl,l);
while(end>0)
{
swap = intl[0];
intl[0] = intl[end];
intl[end] = swap;
--end;
intl = _siftDown(intl, 0, end);
}
return intl;
}
function _heapify(intl, l)
{
var start = (l - 2) / 2;
while(start >= 0)
{
intl = _siftDown(intl, start, l-1);
--start;
}
return intl;
}
function _siftDown(intl, start, end)
{
var root = start,
child, swap, swapr;
while(root*2+1 <= end)
{
child = root * 2 + 1;
swap = root;
if(intl[swap] < intl[child])
swap = child;
if(child+1 <= end && intl[swap]<intl[child+1])
swap = child + 1;
if(swap!=root)
{
swap = intl[root];
intl[root] = intl[swap];
intl[swap] = swap;
root = swap;
}else
{
return intl;
}
}
return intl;
}
x =
[24,5,896,624,437,5,6,4,37,45,654];
y =
["a","b","r","s","t","e","q","u","q"];
console.log(heapSort(x),"\n",heapSort(y));
通过 nodejs 运行代码:
$ node sort.js
[ 5, 5, 6, 24, 37, 45, 437, 624, 654, 896, 4 ]
[ 'b', 'e', 'q', 'q', 'r', 's', 't', 'u', 'a' ]
我试图通过更改代码找到错误所在,但找不到。谁能告诉我问题出在哪里?提前致谢。
最佳答案
我看到了 2 个错误:
在
_heapify
函数中,如果l
不是奇数,则start
变量不是整数:var start = Math.floor( ( l - 2 ) / 2 );
在
_siftDown
函数中,当您有效地交换数组的 2 个元素时,您使用了swap
而不是swapr
:swapr = intl[root]; // <-- Here swapr instead of swap intl[root] = intl[swap]; intl[swap] = swapr; // <-- Here swapr instead of the 1st occurrence of swap root = swapr; // <-- Here swapr instead of swap
关于javascript - Heapsort算法,把最小的元素放在最后,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13601409/