数据结构笔记 – 排序算法 堆排序算法
本文由发表于6年前 | 数据结构与算法 | 暂无评论 |  被围观 6,813 views+

堆排序:

其基本思想是将待排序的数组构造成一个大顶堆,从而获得数组最大的元素,即当前的根节点。将其移走之后,再把剩余的n-1个数组元素重新构造成一个大顶堆。反复执行,最后得到一个有序序列。

堆排序属于选择排序。

堆排序的过程:
① 循环处理元素构造大顶堆
② 获取堆顶元素并和最后一个叶节点交换位置
③ 重新构建大顶堆,元素个数减一(除去最后一个叶节点,即选出的最大值)。
④ 循环第2、3个步骤。
#include <stdio.h>    

#define MAXSIZE 100  /* 待排序数组的大小 */

typedef struct
{
	int r[MAXSIZE+1];	/* 待排序数组r,r[0]为哨兵或临时变量 */
	int length;			/* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 堆排序算法 */
void HeapSort(SortList *L)
{
	int i;
	/* 把待排序数组L构造成大顶堆 */
	for(i=L->length/2;i>0;i--) 
		 HeapAdjust(L,i,L->length);

	for(i=L->length;i>1;i--)
	{ 
		/* 将当前大顶堆的根节点即数组最大值和未排序钱的数组最后一个元素交换位置 */
		int temp=L->r[1];
		L->r[1]=L->r[i];
		L->r[i]=temp;
		/* 把待排序数组L(1 to i-1)中剩余的元素继续构造成大顶堆 */
		HeapAdjust(L,1,i-1); 
	}
}

/* 已知r[s...m]中除了r[s]元素之外均满足堆的定义,本函数通过调整r[s]元素,使待排序数组L构造成大顶堆 */
void HeapAdjust(SortList *L,int s,int m)
{ 
	int temp,j;
	temp=L->r[s];
	/* 沿着元素比较大的结点往下找 */
	for(j=2*s;j<=m;j*=2)
	{
		/* 比较左子树和右子数的大小,获取较大子数的下标j */
		if(j<m && L->r[j]<L->r[j+1])
			++j;
		/* r[s]已经是最大的,无需改变位置 */
		if(temp>=L->r[j])
			break; 
		/* 把较大的子节点赋值给r[s] ,此时r[s]与r[j]相等 */
		L->r[s]=L->r[j];
		/* 从被替换的子节点j开始继续下一个循环,查找j的子节点 */
		s=j;
	}
	/* 此时的r[s]为循环到最后一个处理的父节点 */
	L->r[s]=temp; /* 此时的r[s]为最后一个被交换的子节点,而不是开始的,把temp值赋予该结点,实现和需要处理元素的交换 */
}
堆排序算法复杂度分析:

在初始化构建大顶堆时,每个非终端结点最多比较两次,所有,这个构建的过程时间复杂度为O(n)。

排序过程中,第i次取堆顶记录重建大顶堆的时间复杂度为O(logi),并且需要取n-1次堆顶记录,所有重建堆的时间复杂度为O(nlogn)。总体上来说,堆排序的时间复杂度为:O(nlogn)。

因为初始化构建堆所需比较次数较多,所以堆排序不适合待排序元素较少的情况。

除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/data-structure-notes-sorting-algorithm-heapsort-algorithm.html
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
如果您有更好的原创技术博文或者观点,欢迎投稿:admin@itzhai.com,或者关注订阅左侧浮动面板的微信号订阅IT宅itread)发送消息。
数据结构与算法推荐专题
文章评论
    没有评论
给我留言

有人回复时邮件通知我
数据结构与算法的相关文章
随机文章 本月热门 热评
1 操作系统引论之操作系统基础介绍和发展历史过程 2011/6/28
2 JDBC数据库连接和事务的管理 一个JDBC基本操作封装类的编写 2011/10/13
3 微型计算机技术实用知识点问答题 2011/6/29
4 chrome插件编写中需要了解的几个概念和一些方法 2013/6/5
5 数据结构笔记 – 排序算法 优化冒泡排序算法 2011/9/20
6 C++语法笔记 – 数组 指针与字符串 2011/9/4
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.