堆排序算法看不明白的一处
本帖最后由 panzer111 于 2017-9-14 00:49 编辑// 159.cpp : 定义控制台应用程序的入口点。
//
#include "StdAfx.h"
#include <stdio.h>
void swap(int k[],int i,int j)
{
int temp;
temp=k;
k=k;
k=temp;
}
void HeapAdjust(int k[],int s, int n)
{
int i;
int temp=k;
for(i=2*s;i<=n;i*=2)
{
if (i<n && k<k)
{
i++;
}
if (temp >=k)
{
break;
}
k=k;
s=i;
}
temp=k;
}
void HeapSort(int k[],int n)
{
int i;
for(i=n/2;i>0;i--)
HeapAdjust(k,i,n);
for(i=n;i>1;i--)
{ swap(k,1,i);
HeapAdjust(k,1,i-1);
}
}
int main()
{
int i,a={1,5,7,3,54,49,21,78,47,16};
HeapSort(a,9);
for(i=1;i<10;i++)
{
printf("%d",a);
}
return 0;
}
------------------
void HeapSort(int k[],int n)
{
int i;
for(i=n/2;i>0;i--)
HeapAdjust(k,i,n);
for(i=n;i>1;i--)
{ swap(k,1,i);
HeapAdjust(k,i,i-1);
}
}
------------------
第一个for循环结束后，i已经到了0，首先从n/2开始构建堆，然后从n/2-1开始，自减直到1，也即是第一个起始数，那么第一个for循环结束后是否意味着对整个数组而言，HeapAdjust的整体大顶堆已经构建完毕？
既然整体大顶堆构建完毕，是指所有元素达到有序排列，还是仅仅把最大元素送上堆顶？ 本帖最后由 panzer111 于 2017-9-14 00:52 编辑
如果第一个for循环后大顶堆已经完毕，说明从n/2开始，到起始节点的上一行的最右节点开始构建
也就是说总会从起始节点i的双亲i/4，i/8....直到1，开始构建
for循环完毕后整个堆已经是有序状态，直接输出即可，为何还要第二个for循环？
页:
[1]