c - 通过数组实现使用 Downheap 算法时遇到问题

标签 c arrays algorithm sorting

我目前正在尝试使用下堆算法对键数组进行排序。但是,当我显示新排序的数组时,会出现新数字,并且顺序似乎不正确。我无法判断我的算法是否有问题,或者我是否没有为该排序算法使用正确的条件。

我的工作是对 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/

相关文章:

C结构数组段错误

在c中为捕获的数据包创建PCAP文件

algorithm - 详尽搜索算法 - 现有作品?

algorithm - 通过算法计算全局 Tab 键顺序?

c++ - 适应 Boyer-Moore 实现

c - 如何从递归函数返回字符串数组?

c - [C]关于 %s 、 %c 的字符串和数组

javascript - 二维数组 - 将对象添加到字段

c - 指针和 realloc 的问题,C 中的程序崩溃错误

python - numpy 数组的固定大小子矩阵的索引