首页 > 代码库 > 夯实基础——堆排序

夯实基础——堆排序

堆结构:任意的一个父节点大于其子节点。


逻辑结构:二叉树

物理结构:数组


如果从角标0开始

父节点左孩子节点:2*i+1

父节点右孩子节点:2*i+2

最后一个非叶节点:(n-1)/2


如果从角标1开始

父节点左孩子节点:2*i

父节点右孩子节点:2*i+1

最后一个非叶节点:n/2


堆排序分析:

最优时间复杂度:O(nlog2n)

最坏时间复杂度:O(nlog2n)

平均时间复杂度:O(nlog2n)

空间复杂度:O(1)

稳定性:不稳定


堆排序主要分三个函数:

1 调整成堆结构 void HeapAdjust(int *a,int i,int size);

2 构建堆 void BuildHeap(int *a,int size);

3 堆排序 void HeapSort(int *a,int size);


当角标为0,堆排序代码:


//调整堆
void HeapAdjust(int *a,int i,int size)
{
    int lchild=2*i+1;//左孩子节点
    int rchild=2*i+2;
    int max=i;//临时变量
    //startNode->(size-1)/2:最后的一个非叶子节点
    //选取大于父节点的孩子节点与父节点交换
    //寻找前一个非叶子节点
    if(i<=(size-1)/2)//非叶子节点
    {
        if(lchild<=size&&a[lchild]>a[max])
        {
            max=lchild;
        }
        if(rchild<=size&&a[rchild]>a[max])
        {
            max=rchild;
        }
        if(max!=i)
        {
            swap(&a[i],&a[max]);
            HeapAdjust(a,max,size);//避免调整之后以max为父节点的子树不是堆,简称向下调整
        }
    }
}

//构建堆
void BuildHeap(int *a,int size)
{
    int i;
    //从最后一个非叶节点:(size-1)/2到根节点:0 依次向前遍历
    for(i=(size-1)/2;i>=0;i--)
    {
        HeapAdjust(a,i,size);
    }
}

//堆排序
void HeapSort(int *a,int size)
{
    int i;
    BuildHeap(a,size);//构建堆
    for(i=size;i>=0;i--)
    {
        swap(&a[0],&a[i]);
        HeapAdjust(a,0,i-1);//重新调整堆节点为大顶堆,每次循环将最大值放到堆尾,然后重新构建size:i-1的堆
    }
}

//交换
void swap(int *a,int *b)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}