堆排序给出错误的输出

Question

折腾了堆排序算法，终于弄明白了，还是不行，我好像也找不到问题，可能是我盯着它看了3个小时吧。。问题是它给出了错误的输入。该程序编译并没有给出错误。我用的是 Visual Studio 2013。输入：{ 1, 4, 5, 3, 2, 7, 8, 5, 4, 7, 8, 1 } 预期输出：数组已排序。

输出：1 2 3 5 7 1 4 4 7 8 5 8

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

void change(int *a, int *b){
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}
void OrganizeHeap(int *A, int n, int i){
    int left = i * 2 + 1, right = i * 2 + 2;
    int largest = i;
    if (left < n && A[left] >= A[i])
        largest = left;

    if (right < n && A[right] >= A[i])
        largest = right;

    if (largest != i){
        change(&A[i], &A[largest]);
            OrganizeHeap(A, n, largest);
    }
}
void BuildHeap(int *A, int n){
    for (int i = n / 2 - 1; i >= 0; i--)
        OrganizeHeap(A, n, i);
}
void HeapSort(int *A, int n){
    BuildHeap(A, n);
    for (int i = n - 1; i >= 0; i--){
        change(&A[0], &A[i]);
        OrganizeHeap(A, i, 0);
    }
}
int main() {
    int max;
    int A[] = { 1, 4, 5, 3, 2, 7, 8, 5, 4, 7, 8, 1 };
    int n = sizeof(A) / sizeof(int);
    HeapSort(A, n);
    for (int i = 0; i < n; i++)
        printf("%d ", A[i]);
    _getch();
    return 0;
}

Answer 1

你的代码有两个问题

    if (right < n && A[right] >= A[i])
          largest = right;

如果 A[i] 是 5，A[left] 是 7 那么 largest 将被设置为 left。现在如果 A[right] 是 6。A[right] 大于 A[i] 那么最大的将设置为 right。largest 应该是 left而不是 right 因为 A[left] > A[right] 所以你可以做类似的事情

  if (right < n && A[right] >= A[largest]) //see note below

第二个问题在代码编辑后已经去掉了

注：

在检查时你可以只使用 > 而不是 >=

堆排序给出错误的输出

Heap Sort giving wrong output

c

sorting

algorithm

heapsort