当前位置：首页 > news >正文

堆排序 SCAU c++

news 来源：原创 2024/5/17 17:56:31

堆排序大体思路是：建堆，然后通过堆交换结点大小，将最大的结点放到堆最顶端，将该最大数与数组最后一位交换，不断重复这个过程，直到数组从后往前逐渐完成排序。

此题用大根堆排序和小根堆排序都行，只有一点细微上的差别。

比如每次swap交换的是数组第一位而不是最后一位，然后在adjust函数中判别条件是左右孩子结点取小的那个，父节点小于该孩子结点，那就更换，换到最后堆顶为最小的。

大根堆代码详解如下，附在代码注释中：

#include <iostream>
#include <stdio.h>

using namespace std;

void HeadAdjust(int a[],int k,int len)//每次调整都从数组第一位开始慢慢向后调整
{
    a[0]=a[k];//k为对应父节点下标

    for(int i=2*k;i<=len;i*=2)
    {
        //对于父节点和两个子节点，要更换的是子节点中更大的那一个跟父节点换
        if(i<len && a[i]<a[i+1])//如果左孩子小于右孩子
            i++;

        if(a[0]>=a[i])//如果父节点比更大的那个孩子数值还要大，就不用交换
            break;
        else
        {
            a[k]=a[i];//父节点与孩子交换
            k=i;//将k也就是下标往下移动，换到更大的结点那里，继续往下找看看还有没有需要换的结点
        }

    }

    a[k]=a[0];//此时父节点数值可以放入该位置了，因此左右孩子都比他小了

}

void BuildMaxHeap(int a[],int len)
{
        for(int i=len/2;i>0;i--)//从底向上建
        {
            HeadAdjust(a,i,len);
        }

}

void HeapSort(int a[],int len)
{
    //BuildMaxHeap(a,len);

    for(int i=len;i>1;i--)
    {
        swap(a[i],a[1]);//将大根堆的最顶端也就是数组中最大的数已处于数组第一位，与数组最后一位交换，然后就是倒数第二，倒数第三
        HeadAdjust(a,1,i-1);//然后再对堆进行交换，最后一位已经是最大的了所以不用排序了

        for(int j=1;j<=len;j++)
        {
            printf("%d ",a[j]);
        }
        printf("\n");

    }

}


int main()
{
    int n,i;
            //思路是，建堆，然后通过堆交换结点大小，将最大的结点放到堆最顶端，将该最大数与数组最后一位交换，不断重复这个过程
    scanf("%d",&n);
    int a[n+1];

    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    BuildMaxHeap(a,n);//先建堆,大根堆,建成完全二叉树先

    for(int j=1;j<=n;j++)
    {
        printf("%d ",a[j]);
    }
    printf("\n");

    HeapSort(a,n);//然后调堆


    return 0;
}

欢迎大家在评论区留言~~

觉得有帮助的不妨点个赞