开发者社区> hujunzheng> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

堆排序算法---属于选择排序

简介: 1.堆   堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:   Key[i]=key[2i+2]   即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。   堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Ke...
+关注继续查看

1.堆

  堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:

  Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

  即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

  堆分为大顶堆和小顶堆,满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆,满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的,小顶堆的堆顶的关键字是所有关键字中最小的。

2.堆排序的思想

  利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

  其基本思想为(大顶堆):

  1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;

  2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

  3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到 新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

3.操作过程如下:

  1)初始化堆:将R[1..n]构造为堆;

  2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换,然后将新的无序区调整为新的堆。

  因此对于堆排序,最重要的两个操作就是构造初始堆和调整堆,其实构造初始堆事实上也是调整堆的过程,只不过构造初始堆是对所有的非叶节点都进行调整。

4.举例说明堆排序的操作过程

a首先是讲一个无序的序列构建成一个个堆:

 

 b.然后是输出堆顶元素之后,调整剩余元素成为一个新的堆:

5.下面是代码部分:

#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<cstdlib> 
#include<cstdio>
const int INF=0X3f3f3f3f;
using namespace std;

typedef struct
{
   int a[100];
   int len;
   void outList(){
           for(int i=1; i<=len; ++i)
               cout<<a[i]<<" ";
           cout<<endl;
   }
}list;
list L;
/**********************************************************************************/

void heapAdjust(int ld, int rd){//堆排序, 排序区间[ld,rd] 
    int rc = L.a[ld];
    int cur = ld;
    for(int p = ld*2; p<=rd; p=p*2){
        if(p<rd && L.a[p] > L.a[p+1]) ++p;//取左右子树的最小值
        if(rc < L.a[p]) break;//如果父节点的值比左右子树的值都小,那么已经调整好了,已经是小堆顶了
        L.a[cur] = L.a[p];//否则交换父节点和左右子树最小的子树的值,父节点的值存在rc中,所以只要将最小子树的值赋给父节点就好 
        cur = p;
    }
    L.a[cur] = rc;
}

/**********************************************************************************/

int main() {
    int i;
   scanf("%d", &L.len);
   for(i=1; i<=L.len; i++)
     scanf("%d", &L.a[i]);

    for(int i=L.len/2; i>=1; --i)//将整个区间调整成小堆顶,从最后一个非终结点开始
        heapAdjust(i, L.len);
    
    for(int i=1; i<=L.len; ++i) {
        cout<<L.a[1]<<" "; 
        L.a[1] = L.a[L.len-i+1];//将最后一个元素赋给第一个元素 
        heapAdjust(1, L.len-i);//重新调整堆 
    }
    cout<<endl;
    return 0;
}

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法-基数排序和堆排序
排序算法-基数排序和堆排序
13 0
算法渣-排序-选择排序
没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
34 0
排序算法之选择排序
选择排序(Selection sort)
22 0
排序算法:选择排序
上一次,我们介绍了排序算法中“龟速三兄弟”的二哥“插入排序”。今天,我们继续介绍“龟速三兄弟”中的小弟——“选择排序”。和二哥“插入排序”一样,由于同样是“龟速三兄弟”中的一员,但是处理过程没有大哥“冒泡排序”那么简单明了,因此有不少人可能都没接触过“选择排序”,本文将通过例子来介绍“选择排序”的完整过程。
32 0
八大排序算法~堆排序
八大排序算法~堆排序
35 0
算法-选择排序
选择排序是一种排序算法,它在每次迭代中从未排序列表中选择最小元素,并将该元素放在未排序列表的开头。
48 0
排序算法之直接选择排序
直接选择排序      直接选择排序是将整个待排序序列分为两部分,一部分为有序(最开始有序序列为空),一部分为无序(最终无序序列为空)。有序序列中的数都不大于无序序列中的数。它的过程是每次都在无序中寻找一个最小的数,然后将其与无序序列的第一个数交换,并并入有序序列。则有序序列长度增1,无序序列长度减1。      比如:对R[0….n]数组进行选择排序。其中R[0…i]为
1012 0
算法 - 排序 - 选择排序
每次循环把最小的值往前移 C++代码: Sorter.hpp #ifndef _Algorithm_Sorter_H_ #define _Algorithm_Sorter_H_ template class Sorter { public: static void...
745 0
+关注
hujunzheng
java核心技术专家
444
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载