图解堆排序-C语言实现

栏目: 编程工具 · 发布时间: 5年前

内容简介:我们在介绍《什么是优先队列》的时候就注意到,如果每次都删除堆顶元素,那么将会得到一个有序的数据。因此,我们可以利用二叉堆来对数据进行排序。通过前面的学习我们可以看到,如果构建一个二叉堆,最后每次从堆顶取出一个元素,那么最终取出元素就是有序的,不过如果要用来对数据按照从小到大排序,就不是构造小顶堆,而是大顶堆了,即堆顶元素大于等于其左右儿子节点。总结堆排序思路如下:根据前面的分析,我们来看一个具体的例子。假设我们要对

我们在介绍《什么是优先队列》的时候就注意到,如果每次都删除堆顶元素,那么将会得到一个有序的数据。因此,我们可以利用二叉堆来对数据进行排序。 点我查看本文代码地址。

排序 分析

通过前面的学习我们可以看到,如果构建一个二叉堆,最后每次从堆顶取出一个元素,那么最终取出元素就是有序的,不过如果要用来对数据按照从小到大排序,就不是构造小顶堆,而是大顶堆了,即堆顶元素大于等于其左右儿子节点。总结堆排序思路如下:

  • 以O(N)时间复杂度构建N个元素的二叉堆
  • 以O(logN)时间复杂度删除一个堆顶元素,N个元素时间复杂度为O(NlogN)
  • 由于删除一个堆顶元素时,就会空出一个位置,为了节省空间,将删除的堆顶元素放到数组末尾
  • 当堆为空时,完成排序
  • 由于数组元素从下标0开始,因此每个位置必须利用好。假设堆顶元素位置为i,那么左右儿子节点位置分别为2i+1,2i+2

实例分析

根据前面的分析,我们来看一个具体的例子。假设我们要对

进行排序。

该数据构成的原始二叉树如下:

图解堆排序-C语言实现

构建二叉堆

为了能够使得数组所有元素满足堆的性质,即父节点大于等于儿子节点,我们需要从倒数第二层开始调整(为什么不是从最后一层?)。即调整8和10。

对于8来说,找到它的儿子节点中较大的一个,即35,将8和35交换后如下:

图解堆排序-C语言实现

此时数组数据为:

对于10来说,它比左右儿子节点都大,因此不需要调整。

对于1来说,它的右儿子35最大,因此需要调整,和右儿子交换后如下:

图解堆排序-C语言实现

此时数组数据为:

但是一次交换后,我们发现,1的左儿子还是比它大,因此交换它和较大的左儿子的位置,交换后如下:

图解堆排序-C语言实现

此时数组数据为:

最终我们得到了满足堆性质的二叉堆了。

基于二叉堆的排序

在堆创建好后,每次取出堆顶元素,并且调整堆,把堆顶元素放在数组最后即可。

例如,对于前面创建好的堆,堆顶元素是35,我们取出第i(此时为1)个元素35,并把堆最后一个元素放在数组倒数第i个位置:

图解堆排序-C语言实现

为了满足堆性质,我们需要调整堆顶元素,因为堆顶元素目前不满足堆性质,因此需要交换8和15的位置:

图解堆排序-C语言实现

此时所有元素再次满足堆性质。

此时数组数据为:

对于其他元素也是同样的操作,因此不再赘述。

代码实现

根据上面的分析,关键代码实现如下:

void adjust_ele(ElementType arr[],int i,int length)
{
    int child ;
    ElementType temp;
    for(temp = arr[i];2*i+1 < length;i = child)
    {
        child = 2 * i +1;
        
        /*找到较大的儿子*/
        if(child != length-1 && arr[child+1] > arr[child])
            child+=1;
        /*如果空穴元素小于该儿子,则空穴下滑*/
        if(temp < arr[child])
           arr[i] = arr[child];
        else
         break;
    }
    /*将i位置的元素放到正确的位置*/
    arr[i] = temp;
}
void heap_sort(ElementType arr[],int length)
{
    int i = 0;
    /*构建堆*/
    for(i = length /2;i >= 0;i--)
    {
        adjust_ele(arr,i,length);
        //printArr(arr,length);
    }
    for(i = length-1;i > 0;i--)
    {
        /*填充i位置的空穴*/
        swap(&arr[0],&arr[i]);
        
        /*每次都处理堆顶元素*/
        adjust_ele(arr,0,i);
        //printArr(arr,length);
    }
}

完整可运行代码地址: heapSort

运行结果:

before sort:1 10 8 5 7 15 35 
after  sort:1 5 7 8 10 15 35

总结

结合我们前面介绍的优先队列,我们很容易理解堆排序,不过需要注意的就是位置0必须使用上。另外通过利用删除堆顶元素后空出来的位置,避免了另外申请数组内存来存放排序好的数组。建议自己修改完整可运行代码,来观察数据调整情况。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Bandit Algorithms for Website Optimization

Bandit Algorithms for Website Optimization

John Myles White / O'Reilly Media / 2013-1-3 / USD 19.99

This book shows you how to run experiments on your website using A/B testing - and then takes you a huge step further by introducing you to bandit algorithms for website optimization. Author John Myle......一起来看看 《Bandit Algorithms for Website Optimization》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器