堆排序
#include <stdio.h>void swap(int k[],int i,int j)
{
int temp;
temp=k;
k=k;
k=temp;
}
voidHeapAdjust(int k[],int s,int n)
{
int i;
int temp;
temp=k;//待调整的双亲结点
for(i=2*s;i<=n;i*=2) //i 左孩子 s 是双亲
{
if(i<n&&k<k)//如果左孩子 小于右孩子 ，
{
i++; //使 i 指向 较大的元素
}
if(temp>=k)
{
break;
}
k=k;
s=i;
}
k=temp;
}
void HeapSort(int k[],int n) //构建大顶堆
{
int i;
for(i=n/2;i>0;i--)
{
HeapAdjust(k,i,n); //数组k 传递数据i 是传递双亲， n 是用来判断的 调整成打顶堆的
}
for(i=n;i>1;i--)
{
swap(k,1,i);
HeapAdjust(k,1,n-1);
}
}
intmain()
{
int a={-1,5,2,6,8,3,9,1,7,4}; // 层次排序构造二叉树
int i;
HeapSort(a,9);
printf("排序出来的结构");
for(i=1;i<10;i++)
{
printf("%d",a);
}
}
看着小甲鱼的代码打的，但是我的结果是错的。 我寻找错误的时候，
1.理解不了了 第二次 HeadAdjust 第二个参数 为什么是 1
2.并且恳求 指教代码的错误 #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, temp;
temp = k; // current pointed parent node
for(i= 2*s; i <= n; i *= 2) // 2*s == lchild, 2*s+1 == rchild
{ // i*=2 >> next parent
if(i < n && k < k) // lchild < rchild
{
i++; // points to rchild
}
if(temp >= k)
{
break;
}
k = k;
s = i;
}
k = temp;
}
void HeapSort(int k[], int n)
{
int i;
for(i = n/2; i > 0; i--) // Construct Big Tree
{
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, 2, 6, 3, 9, 1, 7, 4}; //{5, 2, 6, 3, 9, 1, 7, 4, 8};
HeapSort(a, 9);
printf("Sorted list: ");
for(i = 1; i < 10; i++)
{
printf("%d ", a);
}
printf("\n");
return 0;
}
从元素 1 开始，也就是第二个元素。因为元素 0 是补上去但不在操作范围内的 HeapAdjust(k,1,n-1);
HeapAdjust(k,1,i-1); HeapAdjust(k,1,n-1);
HeapAdjust(k,1,i-1); claws0n 发表于 2018-8-25 11:56
从元素 1 开始，也就是第二个元素。因为元素 0 是补上去但不在操作范围内的
谢谢你
在这个过程我一直在想，但我觉得应该 第二个 HeapAdjust () 函数中第二个参数是1，是双亲的位置， 因为 在第一次的转换位置之后，根节点 的位置是有问题的，最大的元素跑到了最后，不符合了大顶锥，其余的在第一次HeapAdjust(),函数 已经排好了。 所以它要重新调整 那个位置， 就是 1 的位置， 也正如你说的，元素是从1 开始的。 所以 传递 1 这个双亲的位置。
这是我迷惑的地方。 还是谢谢你 claws0n 发表于 2018-8-25 12:00
HeapAdjust(k,1,n-1);
HeapAdjust(k,1,i-1);
懂拉~thanks~
页:
[1]