我目前正在尝试使用下堆算法对键数组进行排序。但是,当我显示新排序的数组时,会出现新数字,并且顺序似乎不正确。我无法判断我的算法是否有问题,或者我是否没有为该排序算法使用正确的条件。
我的工作是对 20 个键的数组进行排序。
代码:
/* Downheap sorting algorithm */
for(i=0; i<20; i++)
{
j = i + 1;
/* If parent is less than both children */
if(key[j] < key[2*j] && key[j] < key[(2*j)+1])
{
/* Check which child is smallest */
if(key[2*j] < key[(2*j)+1])
{
/* Parent is assigned smallest node */
swap(&key[j],&key[2*j]);
}
else{swap(&key[j],&key[(2*j)+1]);}
}
/* If parent is less than left child */
else if(key[j] < key[2*j])
{
swap(&key[j],&key[2*j]);
}
/* If parent is less than right child */
else if(key[j] < key[(2*j)+1])
{
swap(&key[j],&key[(2*j)+1]);
}
}
交换功能:
void swap(int *parent, int *child)
{
int temp;
temp = *child;
*child = *parent;
*parent = temp;
}
排序之前的键数组:
54,90,137,260,185,65,208,139,114,176,186,77,137,139,178,57,203,110,80,127
排序一次后键数组:
54,137,185,260,114,77,208,178,110,176,186,65,137,139,139,64,203,90,84,127
64 之前不存在。 57在哪里? 80消失了,84从哪里来?
任何帮助将不胜感激!
最佳答案
如果你有一个包含 20 个数字的数组,它们通常是 key[0]..key[19],并且对于堆,你需要考虑堆元素的一个或多个子元素不存在的可能性存在是因为它们的数组位置将超出数组的边缘。如果堆编号为 0..19,则元素 i 的子元素将位于 2i+1 和 2i+2,因此 0 有子元素 1 和 2,1 有子元素 3 和 4...8 有子元素 17 和 18,但是 9 19 岁只有一个 child ,10 岁根本没有 child 。
您是否期望 Downheap 完成所有排序工作?通常,如 http://en.wikipedia.org/wiki/Heapsort 中所述,Downheap是Heapsort的一部分,但不是全部。
关于c - 通过数组实现使用 Downheap 算法时遇到问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26707793/