文档章节

数据结构排序算法之堆排序

htq
 htq
发布于 2016/07/26 09:41
字数 535
阅读 0
收藏 0
点赞 0
评论 0

关于堆排序的相关知识非常复杂,不懂得可以参考任意一本数据结构教程,本博客只对堆排序框架及代码进行讲解。

堆排序分三个大的步骤:建初堆,堆调整,堆排序(其中最核心的是堆调整)
1建初堆:从数组中的最后一个非叶子节点开始,从下而上倒推(重复调用堆调整函数)
2堆调整:堆调整的前提是已建好了一个堆,但是因为输出,导致需要重新调整堆
3堆排序:从数组中所有元素开始,将堆顶元素与堆尾元素交换,然后数组的元素个数减一,然后继续调用堆调整函数。

基于以上框架,堆排序的代码如下:

#include<iostream>
using namespace std;
void sift(int a[],int root,int len)//堆调整函数
{
	int child=2*root;
	while(child<=len)//注意该函数的参数是从root到len,所以此处必须写=
	{
		if(child<len&&a[child]<a[child+1])//注意此处必须是child<len,之所以不取=因为child=child+1会溢出
		{
			child=child+1;
		}
		if(a[root]<a[child])
		{
			swap(a[root],a[child]);
			root=child;
			child=2*root;
		}
		else
		{
			break;//这个地方之所以可以直接break是因为堆调整函数的前提它本身就是堆,只不过交换了之后得重新调整,所以如果当前结点不满足,则它的子孙结点一定都不满足。
		}
	}
}
void cre_heap(int a[],int n)
{
	for(int i=n/2;i>=1;i--)//从最后一个非叶子结点开始,自底向上倒推,之所以是从非叶子结点开始。是因为该函数是将当前结点与其子结点比较大小,而叶子结点无子结点
	{
		
		sift(a,i,n);//调整堆函数的参数为,array_name,root,len.
	}
}
void heap_sort(int a[],int n)
{
	cre_heap(a,n);//堆排序的第一步,建初堆
	for(int i=n;i>=1;i--)
	{
		swap(a[1],a[i]);
		sift(a,1,i-1);
	}
}
void main()
{
	int a[10]={0,4,2,1,3,7,6,5,9,8};
	heap_sort(a,9);
	for(int i=0;i<10;i++)
	{
		cout<<a[i]<<' ';
	}
	cout<<endl;
}
程序运行结果如下:



© 著作权归作者所有

共有 人打赏支持
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
常用数据结构以及数据结构的排序算法

数组 (Array)   在程序设计中,为了处理方便, 把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中, 数组属于构造数据类型。一个数组可...

带梦想一7飞 ⋅ 2012/09/13 ⋅ 0

排序----堆排序

上一篇:快速排序 数据结构--堆的构造和实现 堆排序可以分为两个阶段: 构造堆。将原始数组重新组织安排进一个堆中 下沉排序。从堆中按递减顺序取出所有元素并得到排序结果 用下沉操作由N个元...

Superheros ⋅ 2017/11/30 ⋅ 0

最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

作者:jack 1. 关于排序 很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如: 数据库脚本,如MSSql, MySq...

小数点 ⋅ 2017/12/04 ⋅ 0

8个常用算法的超常剖析

本文来自作者 jack 在 GitChat 上分享「最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析」,「阅读原文」查看交流实录 「文末高能」 「更多同类话题」 「查看全部话题」 编辑 | ...

gitchat ⋅ 2017/11/30 ⋅ 0

堆排序算法

堆是什么 堆是一种用完全二叉树表示的数据结构,其特点是父节点比子节点大(若是大顶堆,以下若无特殊说明均指大顶堆) 堆排序算法 堆排序算法是利用堆的性质进行排序的一种算法,其大致的原...

LinJeffrey ⋅ 2012/04/26 ⋅ 0

六种排序算法的JavaScript实现以及总结

最近几天在系统的复习排序算法,之前都没有系统性的学习过,也没有留下过什么笔记,所以很快就忘了,这次好好地学习一下。 首先说明为了减少限制,以下代码通通运行于Node V8引擎而非浏览器,...

DM.Zhong ⋅ 05/24 ⋅ 0

算法分析(2)经典排序算法对比

[TOC] 概述 上一篇文章分析了一下基本的排序算法以及Java的实现,不过没有比较深入的去分析,因为对于O(n^2)的算法实现比较简单,但是对于O(nLogn)的算法本身有些复杂,所以就分为两篇文章来...

wustor ⋅ 2017/11/06 ⋅ 0

各种排序算法及其java程序实现

各种排序算法:冒择路(入)兮(稀)快归堆,桶式排序,基数排序 冒泡排序,选择排序,插入排序,稀尔排序,快速排序,归并排序,堆排序,桶式排序,基数排序 一、冒泡排序(BubbleSort) 1. 基本思...

长平狐 ⋅ 2012/11/12 ⋅ 0

排序算法图文视频讲解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部排序算法有...

BearCatYN ⋅ 2015/01/21 ⋅ 0

8大排序算法图文讲解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部排序算法有...

LCZ777 ⋅ 2014/08/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Mahout推荐算法API详解

前言 用Mahout来构建推荐系统,是一件既简单又困难的事情。简单是因为Mahout完整地封装了“协同过滤”算法,并实现了并行化,提供非常简单的API接口;困难是因为我们不了解算法细节,很难去根...

xiaomin0322 ⋅ 24分钟前 ⋅ 0

WampServer默认web服务器根目录位置

安装WampServer之后的web服务器根目录默认位置在WampServer安装目录下的www:

临江仙卜算子 ⋅ 25分钟前 ⋅ 0

Redux的一些手法记录

Redux Redux的基本概念见另一篇文。 这里记录一下Redux在项目中的实际操作的手法。 actions 首先定义action.js,actions的type,可以另起一个action-type.js文件。 action-type.js用来存...

LinearLaw ⋅ 26分钟前 ⋅ 0

android 手势检测(左右滑动、上下滑动)

GestureDetector类可以让我们快速的处理手势事件,如点击,滑动等。 使用GestureDetector分三步: 1. 定义GestureDetector类 2. 初始化手势类,同时设置手势监听 3. 将touch事件交给gesture...

王先森oO ⋅ 41分钟前 ⋅ 0

java 方法的执行时间监控 设置超时(Future 接口)

java 方法的执行时间监控 设置超时(Future 接口) import java.util.concurrent.Callable; import java.util.concurrent.ExecutionException; import java.util.concurrent.Executor......

青峰Jun19er ⋅ 45分钟前 ⋅ 0

一名开源小白的Apache成长自述

今天收到了来自Apache Vote我成为Serviceomb项目Committer的邮件,代表自己的贡献得到了充分的肯定;除了感谢团队的给力支持,我更希望将自己的成长经历——如何践行Apache Way的心得介绍给大...

微服务框架 ⋅ 47分钟前 ⋅ 0

vim介绍、颜色显示和移动光标、一般模式下复制、剪切和粘贴

1.vim 是 vi 的升级版 vim 是带有颜色显示的 mini安装的系统,一般都不带有vim [root@aminglinux-128 ~]# yum install -y vim-enhanced已加载插件:fastestmirror, langpacksLoading mir...

oschina130111 ⋅ 48分钟前 ⋅ 0

Deepin 操作系统四面楚歌

作为国内做的最好的 Linux 发行版,源自 Debian sid 的 Deepin 目前正面临重重困境,新版本不断延期,开发人员离职,bug 长期得不到修复,和 Debian/Ubuntu 的兼容性问题也面临越来越严重的挑...

六库科技 ⋅ 48分钟前 ⋅ 0

MyBatis之动态sql

我们需要知道的是,使用mybatis重点是对sql的灵活解析和处理。在原先的UserMappser.xml中,我们这样查询表中满足条件的记录 : 123 <select id="findUserList" parameterType="userQuery...

瑟青豆 ⋅ 48分钟前 ⋅ 0

这届俄罗斯世界杯的冷门那么多怎么办?

最纯粹的世界杯,最神奇的大冷门。 德国0比1被墨西哥摩擦了。 日本历史性的赢了哥伦比亚。 C罗也挑平了西班牙。 梅西被冰岛狮吼吼愣神了。 就连11次进世界杯4强的巴西也被瑞士逼平了。 天台已...

开源中国众包平台 ⋅ 49分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部