堆排序

堆排序是对简单选择排序算法的一种改进,在每次选择最小记录的同时,根据比较结果对其他记录做出相应的调整。

堆是具有下列性质的完全二叉树:每个节点的值都大于(小于)或者等于其左右孩子节点的值,为大顶堆(小于)。

堆排序的基本思想是:从最后一个含有叶子节点的节点开始将待排序列构造成一个堆,然后将堆顶元素与末尾元素交换,然后不管末尾元素,将剩余的元素重新形成一个堆,如此反复,直到有序。

注意:由于堆是一种树形结构,所以被排序的序列要从1开始编号。

// 堆排序.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;
//将L数组中s到len的数据建立成为大顶堆
void HeapAdjust(int *L,int s,int len)
{
    int  temp;
    temp=L[s];
    for(int j=2*s;j<=len;j=j*2)
    {
        if(j<len&&L[j]<=L[j+1])//找到孩子节点中较大的那个
        {
            j++;
        }
        if(temp<L[j])//如果节点比孩子节点中较大的那个小,将此节点替换为较大的孩子节点
        {
            L[s]=L[j];
            s=j;
        }
    }
    L[s]=temp;
}
void swap(int *L,int i,int j)
{
    int temp=L[i];
    L[i]=L[j];
    L[j]=temp;
}
//输入数组名和数组长度,进行堆排序
void heapsort(int *L,int len)
{
    //从最后一个含有叶子节点的节点开始构造堆(参见二叉树性质5)
    for(int i=len/2;i>0;i--)
    {
        HeapAdjust(L,i,len);
    }
    //每一次交换堆顶和堆尾元素,然后重新构造堆
    for(int i=len;i>1;i--)
    {
        swap(L,1,i);
        HeapAdjust(L,1,i-1);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int num[10]={0,2,5,4,7,5,4,8,41,86};
    //注意这里由于堆排序利用的是二叉树的第五条性质,所以数组下标要从1开始,num中0不在排序的序列之中
    heapsort(num,9);
    for(int i=1;i<10;i++)
    {
        cout<<num[i]<<' ';
    }
    return 0;
}

更加图文并茂的推荐一篇别人的博文:http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT笔记

京东2017校园招聘笔试真题(希尔排序)

对关键字{10,20,8,25,35,6,18,30,5,15,28}序列进行希尔排序,取增量d =5时,排序结果为( ) A. {6,18,8,5,15,10...

3055
来自专栏null的专栏

挑战数据结构与算法面试题——统计上排数在下排出现的次数

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 本题应该是一个确定的问题,即上排的是个数是题目中给定的...

3196
来自专栏CVer

排序算法 | 冒泡排序(含C++/Python代码实现)

排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。排序算法有很多,本文将介绍最经典的排序算法:冒泡排序...

1162
来自专栏技术墨客

JVM与字节码——2进制流字节码解析 原

本位将详细介绍字节码的2进制结构和JVM解析2进制流的规范。规范对字节码有非常严格的结构要求,其结构可以用一个JSON来描述:

912
来自专栏java工会

Java基础第一阶段知识点,招实习的面试官都在问这些

2169
来自专栏数据结构与算法

洛谷P3377 【模板】左偏树(可并堆)

题目描述 如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作: 操作1: 1 x y 将第x个数和第y个数所在的小根堆合并(若第x或第y...

2714
来自专栏进击的君君的前端之路

面向对象、this

1203
来自专栏代码世界

Python基础数据类型之集合以及其他和深浅copy

一、基础数据类型汇总补充 list  在循环一个列表时,最好不要删除列表中的元素,这样会使索引发生改变,从而报错(可以从后向前循环删除,这样不会改变未删元素的索...

3059
来自专栏Android Note

Kotlin —  lateinit vs lazy

1123
来自专栏开发与安全

从零开始学C++之从C到C++(一):const与#define、结构体对齐、函数重载name mangling、new/delete 等

一、bool 类型 逻辑型也称布尔型,其取值为true(逻辑真)和false(逻辑假),存储字节数在不同编译系统中可能有所不同,VC++中为1个字节。 声明方式...

1920

扫码关注云+社区

领取腾讯云代金券