C语言 堆排序堆排序

Question

我有一个问题女巫堆排序。我不知道我的代码出了什么问题。该程序仅更改了表中的第二个和最后一个位置。这是我的代码（没有主函数）：

   #include<stdio.h>
#define DUZO 100000000
int heap_size;
int tab[DUZO];
void heapify(int start){
    int l, r, largest, pom;
    l = 2*start + 1;
    r = 2*start + 2;
    if((l < heap_size) && (tab[l] > tab[start]))
        largest = l;
    else
        largest = start;
    if((r <  heap_size) && (tab[r] > tab[largest]))
        largest = r;
    if(largest != start){
        pom = tab[start];
        tab[start] = tab[largest];
        tab[largest] = pom;
        heapify(largest);
    }
}
void build_max(){
    int lenght, i;
    lenght = heap_size;
    for(i = ((lenght - 1)/2); i >= 0; --i){
        heapify(i);
    }
}
void heap_sort(){
    int i;
    build_max();

    for(i = heap_size-1; i > 0; --i) {
        int tmp = tab[0];
        tab[0] = tab[i];
        tab[i] = tmp;
        --heap_size;
        heapify(0);
    }
}

感谢所有的帮助。

Answer 1

int heap_size = 6;
int tab[5];

这要求写入（和读取）超过数组的末尾，导致未定义的行为，可能会产生不良后果。

将堆大小和数组作为全局变量是一个坏主意，它们应该是函数的参数。

l = 2*start + 1;
r = 2*start + 2;

这是当您在索引 0 处具有堆顶部时的索引，但是

if((l <= heap_size) && (tab[l] > tab[start]))

如果堆的顶部位于索引 1 处，则将使用该检查。对于索引 0，应该<（也在下一次检查 r 中）。

void build_max(){
    int lenght, i;
    lenght = heap_size;
    for(i = ((lenght - 1)/2); i > 0; i--){
        heapify(i);
    }
}

忘记堆顶部，

所以它通常不会创建堆，条件应该是i >= 0.

void heap_sort(){
    int i, lenght;
    build_max();
    lenght =  heap_size;
    for(i = lenght; i > 1; i--){
        heap_size -= 1;
        heapify(i);
    }
}

不会在最后一个位置交换堆的顶部，因此它根本不排序。循环应如下所示

for(i = heap_size-1; i > 0; --i) {
    /* swap top of heap in the last position */
    int tmp = tab[0];
    tab[0] = tab[i];
    tab[i] = tmp;
    --heap_size; /* urk, but what can we do if heapify uses the global? */
    heapify(0);  /* we need to heapify from the top, since that's where the leaf landed */
}

实际对数组进行排序。