【算法导论】堆排序-阿里云开发者社区

开发者社区> tengweitw> 正文

【算法导论】堆排序

简介:         堆排序像合并排序一样,时间复杂度为O(nlogn);像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。         二叉堆的概念:是一种数组对象,可以被视为一棵完全二叉树,树的每一层都是填满的,最后一层可能除外。
+关注继续查看

        堆排序像合并排序一样,时间复杂度为O(nlogn);像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。

        二叉堆的概念:是一种数组对象,可以被视为一棵完全二叉树,树的每一层都是填满的,最后一层可能除外。

        二叉树有两种:最大堆和最小堆。最大堆:父节点不小于子节点。最小堆:父节点不大于子节点。在堆排序中我们使用最大堆;最小堆通常在构造优先队列时使用。

        进行堆排序分为三个模块:1.保持最大堆性质;2.建堆;3:进行排序。

        1.保持最大堆性质即使以i为根的子树成为最大堆

            可以由下图为例:

         

   具体程序如下

/*****************************************\
 输入:原始数组arrayA 父节点的下标i             
 功能:使以i为根的子树成为最大堆
 时间复杂度:lgn即树的层数
\*****************************************/

void MaxHeapify(int* arrayA,int n,int i)//i为父节点的在数组的下标
{
	
	int Length=n;
	
	int l=2*i;//l为左子节点的在数组的下标
	int r=l+1;//r为右子节点的在数组的下标
	int largest=0;
	int temp=0;

	if((l<Length)&&(arrayA[l]>arrayA[i]))
       largest=l;
	else
		largest=i;
	if((r<Length)&&(arrayA[r]>arrayA[largest]))
	    largest=r;
	if(largest!=i)
	{
		temp=arrayA[i];
		arrayA[i]=arrayA[largest];
		arrayA[largest]=temp;
		MaxHeapify(arrayA,n,largest);
	}
}

    2.建堆:使数组arrayA中的元素成为最大堆

     


具体程序如下

/*****************************************\
 输入:原始数组arrayA              
 功能:使数组arrayA中的元素成为最大堆
 时间复杂度:nlgn
\*****************************************/
void BuildMaxHeap(int* arrayA,int n)
{
	for(int i=n/2;i>0;i--)
		MaxHeapify(arrayA,n,i);
}

3.堆排序

   主要思想是将每次的堆的顶节点与最末的叶节点进行交换,然后重新根据最大堆性质使得顶节点(根)成为最大值,如此循环。

   

具体程序如下:

/*****************************************\
 输入:原始数组arrayA              
 功能:进行从小到大的排序
 时间复杂度:nlgn
\*****************************************/
void HeapSort(int* arrayA,int n)
{
	int temp=0;
	int Length=n;
	for(int i=Length-1;i>=2;i--)
	{
		temp=arrayA[1];
		arrayA[1]=arrayA[i];
		arrayA[i]=temp;
		n--;
		MaxHeapify(arrayA,n,1);
	   
	}
}

下面将三个步骤综合起来,总的排序算法程序如下

#include<iostream>
#include<ctime> 
using namespace std;

void MaxHeapify(int* arrayA,int n,int i);//保持最大堆的性质
void BuildMaxHeap(int* arrayA,int n);//构造堆
void HeapSort(int* arrayA,int n);//进行堆排序

void main()
{

	int arrayA[11]={0,4,1,3,2,16,9,10,14,8,7};//第一个空间不用,是为了方便下标计算

	int Length=sizeof(arrayA)/sizeof(int);//数组的长度

	BuildMaxHeap(arrayA,Length);//利用数组arrayA建立最大堆

	cout<<"原序列为:";
    for(int i=0;i<Length;i++)
		cout<<arrayA[i]<<" ";
	cout<<endl;

	HeapSort(arrayA,Length);

	cout<<"排序好的序列为:";
	for(int i=0;i<Length;i++)
		cout<<arrayA[i]<<" ";
	cout<<endl;



}

/*****************************************\
 输入:原始数组arrayA 父节点的下标i             
 功能:使以i为根的子树成为最大堆
 时间复杂度:lgn即树的层数
\*****************************************/

void MaxHeapify(int* arrayA,int n,int i)//i为父节点的在数组的下标
{
	
	int Length=n;
	
	int l=2*i;//l为左子节点的在数组的下标
	int r=l+1;//r为右子节点的在数组的下标
	int largest=0;
	int temp=0;

	if((l<Length)&&(arrayA[l]>arrayA[i]))
       largest=l;
	else
		largest=i;
	if((r<Length)&&(arrayA[r]>arrayA[largest]))
	    largest=r;
	if(largest!=i)
	{
		temp=arrayA[i];
		arrayA[i]=arrayA[largest];
		arrayA[largest]=temp;
		MaxHeapify(arrayA,n,largest);
	}
}


/*****************************************\
 输入:原始数组arrayA              
 功能:使数组arrayA中的元素成为最大堆
 时间复杂度:nlgn
\*****************************************/
void BuildMaxHeap(int* arrayA,int n)
{
	for(int i=n/2;i>0;i--)
		MaxHeapify(arrayA,n,i);
}


/*****************************************\
 输入:原始数组arrayA              
 功能:进行从小到大的排序
 时间复杂度:nlgn
\*****************************************/
void HeapSort(int* arrayA,int n)
{
	int temp=0;
	int Length=n;
	for(int i=Length-1;i>=2;i--)
	{
		temp=arrayA[1];
		arrayA[1]=arrayA[i];
		arrayA[i]=temp;
		n--;
		MaxHeapify(arrayA,n,1);
	   
	}
}

注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为:

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
} 



原文:http://blog.csdn.net/tengweitw/article/details/9152899

作者:nineheadedbird


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
堆排序+代码实现
堆,heap,是二叉树的一种。小根堆有这样的性质——任意一个结点的值比它的左右孩子都要小。 排序思想将待排元素看作是完全二叉树,物理上用一维数组存储。
1057 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10086 0
【算法导论】选择排序法
选择排序法         选择排序其实是冒泡法的一种改进,其基本思路也是:先确定最小元素,再找次最小元素,最后确定最大元素。         它与冒泡排序的最大区别在于:冒泡排序是只要碰见比它大的元素就交换,而选择排序是直接将元素放在最终的确定位置,从而避免了多次交换过程。
934 0
【算法导论】堆排序
        堆排序像合并排序一样,时间复杂度为O(nlogn);像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。         二叉堆的概念:是一种数组对象,可以被视为一棵完全二叉树,树的每一层都是填满的,最后一层可能除外。
794 0
算法笔记--堆排序
堆排序也是一种选择排序,对序列的原始顺序不敏感,适用于数据量大的情况。 1. 算法思想           堆:子节点的值总是小于/大于它的父节点。这里使用的是最大堆。           将数组转化为最大堆,依次将对顶元素取出,与堆中最后一个元素交换,堆长度减一,对堆作调整;如此循环至堆为空,最后得到一个元素由小到大排列的数组。
599 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13891 0
排序算法(五):堆排序
从二叉搜索树和平衡二叉树的介绍中,可以发现二叉树这种结构具有一个很好的特性,当有序的二叉树构造完成之后,更改树中节点后,只需要 的时间复杂度即可将二叉树重新调整为有序状态。
896 0
【算法导论】基数排序
基数排序 时间复杂度:O(n). 基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。
807 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
159
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载