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

简介:

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;
}

目录
相关文章
|
6月前
|
搜索推荐 算法
选择排序(二)——堆排序(性能)与直接选择排序
选择排序(二)——堆排序(性能)与直接选择排序
50 1
|
算法 搜索推荐 C++
基本算法-选择排序
基本算法-选择排序
|
搜索推荐 索引
简单排序 --- 选择排序(常见经典排序算法)
简单排序 --- 选择排序(常见经典排序算法)
56 0
|
算法 搜索推荐
算法-直接选择排序
算法-直接选择排序
初学算法之分治---快速排序
初学算法之分治---快速排序
|
算法
算法初识---选择排序
一、算法内容 选择排序的内容比较简单,大体上说就是,先确定一个数字为最小,然后从他后面的数中来寻找是否有比他更小的数,如果有便将两者交换,这个过程完成后,第一个数字就以及被排好序,第一个数字为最小的,然后将第二个数字定为最小,再从它的后面找是否有比它小的,如果有,便和它交换,从而排好第二个数位,以此类推直到将最后一个数排好。
72 0
|
算法
算法初识---插入排序
插入排序将要排序的元素分成两组,已排序的和未排序的。每次将未排序的元素和已排序的元素依次比较,发现已排序序列中元素比待排序元素大则交换他俩的位置。若已排序的元素均比待排序的元素小,不做任何操作,因为算上待排序元素,新的序列仍然有序,进行下一个待排序元素的插入。直到所有元素都都插入到已排序元素中,全部元素排序完毕。
74 0
|
算法
算法初识---希尔排序
希尔排序是插入排序的优化版本,具体做法是: 1)选定一个增长量h,按照增长量对数据进行分组。 2)对分好组的每一组数据再进行插入排序。 3)减小增长量h,最小减为1,重复2)步骤,即继续对分组数据进行插入排序。
58 0
|
算法 搜索推荐
算法初识---冒泡排序
冒泡排序同选择排序一样是一种排序算法,它的主要方法是对比相邻两个数的大小,如果前边得数比后面的数的,则他们交换,否则比较接下来相邻的两个数,第一轮比较到最后会确定最后一个数的位置,即最后一个数是最大,每进行一轮就会排好一个数,直到把所有的数都排好。
62 0
|
搜索推荐
排序算法--选择排序
排序算法--选择排序
69 0