文档章节

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

htq
 htq
发布于 2016/07/26 09:41
字数 535
阅读 4
收藏 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;
}
程序运行结果如下:



本文转载自:http://blog.csdn.net/htq__/article/details/50857239

共有 人打赏支持
htq

htq

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

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

带梦想一7飞
2012/09/13
0
0
最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

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

小数点
2017/12/04
0
0
8个常用算法的超常剖析

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

gitchat
2017/11/30
0
0
六种排序算法的JavaScript实现以及总结

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

DM.Zhong
05/24
0
0
算法分析(2)经典排序算法对比

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

wustor
2017/11/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Redis常用命令

keys 我把这个命令放在第一位,是因为笔者曾经做过的项目,以及一些朋友的项目,都因为使用keys这个命令,导致出现性能毛刺。这个命令的时间复杂度是O(N),而且redis又是单线程执行,在执行k...

谢思华
32分钟前
2
0
关于css宽度分离

所谓宽度分离就是width 属性不与影响宽度的 padding/border(有时候包括 margin)属性共存 例如: .box{width:200px;padding:20px;border:1px solid;} 为何要做宽度分离 一说到分离就是为了好...

莫西摩西
43分钟前
1
0
Linux常用命令

###############常用命令说明############################## cat /proc/version 显示内核的版本 mv dir1 new_dir 重命名/移动 一个目录 rm -rf a.txt b.txt c.txt 删除多个文件 chmod 777 ......

lyle_luo
50分钟前
2
0
全国地区代码科普

全国地区代码表 天津市 地区代码 地区名称 1100 天津市 辽宁省 地区代码 地区名称 2210 沈阳市 2210 法库县 2210 康平县 2210 辽中县 2210 新民市 2220 大连市 2222 普兰店市 2223 庄河市 22...

恋码之子
50分钟前
1
0
DbForge Schema Compare for MySQL入门教程:生成比较报告

【dbForge Schema Compare for MySQL下载】 当架构比较完成后,您可以生成比较报告以保留架构更改的记录。 1. 在“Comparison” 菜单中,单击“Generate Comparison Report” 。将打开“Gen...

Miss_Hello_World
51分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部