堆排序，数组的索引从 1 而不是 0 开始

Question

#include<stdio.h>

int swap(int *a,int *b){

int tmp;

 tmp=*a;
*a=*b;
*b=tmp;

}

void heapify(int a[],int n,int i){

int largest =i;
int left=2*i+1;
int right=2*i+2;

while(left<=n&&a[left]>a[largest]){
    largest=left;
 }

while(right<=n&&a[right]>a[largest]){
    largest=right;
 }

if(largest!=i){
swap(&a[largest],&a[i]);
heapify(a,n,largest);
 }

}

int heapSort(int a[],int n){

int i;

for(i=n/2-1;i>=0;i--){
  heapify(a,n,i);
 }

for(i=n;i>=0;i--){
    swap(&a[0],&a[i]);
    heapify(a,n,0);

 }

}

 void printlist(int A[],int len){

int i;

for(i=0;i<len;i++){
    printf(" %d",A[i]);
 }
 printf("\n");
}

int main(){


int a[]={1,5,4,6,3,9,7};
int len=sizeof(a)/sizeof(a[0]);

printf("before :");
printlist(a,len);
heapSort(a,len-1);
printf("after:");
printlist(a,len);

}

由于heapsort中的数组索引从1开始，我通过改变i、left、right的值手动将其更改为0....

但是问题还是出现

这是输出：之前：1 5 4 6 3 9 7 之后：9 7 6 4 5 3 1

一定是有些错误我没有注意到，谢谢帮助！！

ps:谁能推荐一个很酷的link，它不能发现代码的错误或错误，那就太好了。

Answer 1

问题出在这里：

for(i=n;i>=0;i--){
    swap(&a[0],&a[i]);
    heapify(a,n,0);

}

对 heapify 的调用仍在使用整个堆。您需要将其更改为 heapify(a, i-1, 0).

此外，在您的 heapify 函数中，您有：

while(left<=n&&a[left]>a[largest]){
    largest=left;
 }

while(right<=n&&a[right]>a[largest]){
    largest=right;
 }

这些没有必要是 while 语句，因为循环体永远不会执行超过一次。例如，如果在第一个中执行主体，则 largest == left，并且下一次 a[left] > a[largest] 将无法评估为真。这些都可以是 if 语句。

堆排序，数组的索引从 1 而不是 0 开始

Heap Sort ,index of array starting 1 instead of 0

c

heap

heapsort