堆排序

forxtz

发布于 2022-05-10 09:29:49

1250

发布于 2022-05-10 09:29:49

文章被收录于专栏：源懒由码

复杂度为O(nlogn),辅助空间1，属于不稳定的排序。

存储的实际是数组，但是把他当做二叉树来处理。

了解一下大根堆和小根堆，大根堆就是指，父节点大于子节点的“二叉树”序列。

n个关键字序列Kl，K2，…，Kn称为（Heap），从数组上看就是，ki>=k(2i）且ki>=k(2i+1)(1≤i≤ n/2）

小根堆反之。

堆排序的过程就是：

1.构造堆 -- 大根堆或者小根堆（对应，把数组从小到大排或者从大到小排）

2.重复建堆

构造堆：首先，需要知道，从数组上看，最后一个非叶子节点就是 array[len/2-1]，然后，我们从最后一个非叶子节点到根节点开始，整理数组，把较大的结点往上移，形成父节点比子结点大。此话花费 n/2*( log2(n) - log2(i)

重复建堆：因为你构造好一个大根堆，那么，堆顶就是最大的嘛，然后把最大的跟当前堆中最后一个元素交换位置，就形成两个序列，一个是堆的序列，一个是排好序的序列。接着，因为你的堆被改过，所以要再调节，形成回大根堆，然后再跟堆最后一个元素交换，重复。此处花费 (n-1) * log(i). 所以，总得来说，复杂度为 nlog2(n)

for(i=length-1;i>0;--i)
    {
        //把第一个元素和当前的最后一个元素交换，
        //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
        swap(array[i],array[0]);
        //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
        make_heap(array,0,i);
    }

贴上全部代码：

#include <iostream>  
using namespace std;  

//堆排序
//整理节点time:O(lgn)
template<typename T>
void make_heap(T* array,int element,int length)
{
    int nChild;
    for(;2*element+1<length;element=nChild)
    {
        //子结点的位置=2*（父结点位置）+1
        nChild=2*element+1;
        //得到子结点中较大的结点
        if(nChild<length-1&&array[nChild+1]>array[nChild])++nChild;
        //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
        if(array[element]<array[nChild])
        {
            swap(array[element],array[nChild]);
            //nTemp=array[i];
            //array[i]=array[nChild];
            //array[nChild]=nTemp; 
        }
        else break; //否则退出循环
    }
}
//堆排序time:O(nlgn)
template<typename T>
void heap_sort(T* array,int length)
{
    int i;
    //调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
    //length/2-1是最后一个非叶节点，此处"/"为整除,此为构造堆过程
    for(i=length/2-1;i>=0;--i)
    make_heap(array,i,length);
    //从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
    for(i=length-1;i>0;--i)
    {
        //把第一个元素和当前的最后一个元素交换，
        //保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
        swap(array[i],array[0]);
        //不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
        make_heap(array,0,i);
    }
}


int main()  
{  
    const int len = 9;  
    int array[len] = {4,7,3,5,4,3,2,1,0};  

    //建堆
    for(int i=len/2-1;i>=0;--i)
    make_heap(array,i,len);
    for(auto elem : array)
        cout << elem << " ";
    cout << endl;

    //堆排序
    heap_sort(array, len);  
    for(auto elem : array)
        cout << elem << " ";
    cout << endl;

    system("pause");
    return 0;  
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2015-08-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法