【算法导论】堆排序

简介:         堆排序像合并排序一样,时间复杂度为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


目录
相关文章
|
3月前
|
存储 人工智能 算法
深入浅出堆排序: 高效算法背后的原理与性能
深入浅出堆排序: 高效算法背后的原理与性能
47 1
|
5月前
|
算法 搜索推荐 Python
Python算法——堆排序
Python算法——堆排序
43 2
|
5月前
|
算法 搜索推荐 C#
C#堆排序算法
C#堆排序算法
|
6天前
|
算法
堆排序+TopK问题——“数据结构与算法”
堆排序+TopK问题——“数据结构与算法”
|
26天前
|
搜索推荐 算法
【八大经典排序算法】堆排序
【八大经典排序算法】堆排序
12 0
|
1月前
|
搜索推荐 C语言
排序算法-选择/堆排序(C语言)
排序算法-选择/堆排序(C语言)
11 0
|
2月前
|
搜索推荐 算法 Java
【数据结构排序算法篇】----堆排序【实战演练】
【数据结构排序算法篇】----堆排序【实战演练】
25 2
|
2月前
|
算法 搜索推荐
堆排序算法
堆排序算法
17 0
|
3月前
|
存储 搜索推荐
常见排序算法原理及实现——第二部分(归并排序、快速排序、堆排序)
常见排序算法原理及实现——第二部分(归并排序、快速排序、堆排序)
|
4月前
|
搜索推荐 算法 调度
堆排序:高效而稳定的排序算法
在计算机科学中,排序算法是一项基本而重要的任务。堆排序作为一种经典的排序算法,以其高效性和稳定性而受到广泛关注。本文将介绍堆排序的原理、实现方法以及其在实际应用中的优势。

热门文章

最新文章