[已解决]堆排序

仅有的倔强

#include <stdio.h>

void swap(int k[],int i,int j)
{
        int temp;

        temp=k[i];
        k[i]=k[j];
        k[j]=temp;
}

void  HeapAdjust(int k[],int s,int n)
{
        int i;
        int temp;

    temp=k[s];  //待调整的双亲结点


        for(i=2*s;i<=n;i*=2) //i 左孩子   s 是双亲
        {
                if(i<n&&k[i]<k[i+1])  //如果左孩子 小于右孩子 ，
                {
                        i++;      //使 i 指向 较大的元素
                }
                if(temp>=k[i])
                {
                        break;
                }
                k[s]=k[i];
                s=i;
        }
        k[s]=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);
        }
}

int  main()
   {
           int a[10]={-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[i]);
           }
   }


看着小甲鱼的代码打的，但是我的结果是错的。 我寻找错误的时候，
1.理解不了了 第二次 HeadAdjust 第二个参数 为什么是 1
2.并且恳求 指教代码的错误

最佳答案

月排行榜 / 总排行榜

claws0n

2018-8-25 11:56:09

#include <stdio.h>

void swap(int k[], int i, int j)
{
        int temp;
        
        temp = k[i];
        k[i] = k[j]; 
        k[j] = temp;
}

void HeapAdjust(int k[], int s, int n)
{
        int i, temp;
        
        temp = k[s];        // 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[i] < k[i+1])                // lchild < rchild
                {
                        i++;                                                // points to rchild
                }
                if(temp >= k[i])
                {
                        break;
                }
                
                k[s] = k[i];
                s = i;
        }
        k[s] = 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[10] = {-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[i]);
        }
        printf("\n");
        
        return 0;
}

从元素 1 开始，也就是第二个元素。因为元素 0 是补上去但不在操作范围内的

跳转到最佳答案楼层

claws0n

#include <stdio.h>

void swap(int k[], int i, int j)
{
        int temp;
        
        temp = k[i];
        k[i] = k[j]; 
        k[j] = temp;
}

void HeapAdjust(int k[], int s, int n)
{
        int i, temp;
        
        temp = k[s];        // 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[i] < k[i+1])                // lchild < rchild
                {
                        i++;                                                // points to rchild
                }
                if(temp >= k[i])
                {
                        break;
                }
                
                k[s] = k[i];
                s = i;
        }
        k[s] = 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[10] = {-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[i]);
        }
        printf("\n");
        
        return 0;
}

从元素 1 开始，也就是第二个元素。因为元素 0 是补上去但不在操作范围内的

claws0n

HeapAdjust(k,1,n-1);
HeapAdjust(k,1,i-1);

claws0n

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~