C++、C#、java算法学习日记06----堆排序思想(Heap

页面导航:首页 > 软件编程 > C#教程 > C++、C#、java算法学习日记06----堆排序思想(Heap

C++、C#、java算法学习日记06----堆排序思想(Heap

来源: 作者: 时间:2016-01-15 14:58 【

上一篇所学的 希尔排序 是对插入排序的一种高效优化,而堆排序则是对选择排序的一种高效优化,也属于选择排序的一种,所以他的基本思想同 直接选择排序 一样也就是每次从数列中

上一篇所学的 希尔排序 是对插入排序的一种高效优化,而堆排序则是对选择排序的一种高效优化,也属于选择排序的一种,所以他的基本思想同 直接选择排序 一样也就是每次从数列中选出最大或最小的放到末尾或是开头,但是堆排序的选择过程要比 直接选择排序 的选择过程高效的多,采用了树形结构来记录每次的比较结果(可以省略重复的比较),大值总是作为父节点(最终形成大根堆),或是小值总是作为父节点(最终形成小根堆),最后堆顶元素就是最大或最小值。

基本思想:

将待排序数列 array[0....n] 调整为大根堆(这里我们进行升序排列),也就是将数组调整为一颗父节点总是大于子节点的完全二叉树,然后将堆顶元素 array[0](也就是最大值)与末尾元素 array[n] 交换(这样一交换刚拍好的大根堆就乱了),再次调整选择后的数组 array[0...array[n-1]] 为大根堆,经过n-1次这样的循环后只剩下一个元素array[0]此时升序排序完成。

从上面的描述过程中可知,堆排序主要分为2个部分的循环,

1.调整堆 2.首尾交换再调整

调整堆:

本篇我们以大根堆为例(因为要做升序排序),上面也说了大根堆也就是一颗父节点总是大于子节点的完全二叉树,所以具有完全二叉树的所有性质。因此如果父节点为 array[i],则它的2个子节点为array[2*i+1](左孩子),array[2*i+2](右孩子),并且父节点大于左右孩子。

比如将:array[]={16, 7, 3, 20, 17, 8 }调整为大根堆。

首先该数组用完全二叉树表示为:

\

从最后一个父节点array[2]开始调整(与array[5]比较,交换)

 

\

最终结果:

\(大根堆)此时数组array[]={20,17,8,7,16,3}

 

我们用C++代码实现为:

#include

using namespace std;

void HeapAdjust(int *array,int nLength)
{
	int i;
	int Child,temp;
	//i为父节点下标,从最后一个父节点到第一个父节点
	for(i=(nLength/2-1);i>=0;i--)
	{
		for(;2*i+1

结果为: 20 17 8 7 16 3

 

首尾交换再调整:

经过调整堆我们选出最大值也就是堆顶array[0]与array[5]交换,然后将被打乱的堆再经过上面的调整再交换,也就是调用n-1次 HeapAdujust()函数。

\

 

 

堆排序的基本思想就是如此了,堆排序适合对海量的数据进行排序,当然了为了使效率更高你还可以定义k叉数,不过思想还是一样的。下一篇中我们将随机生成10000个数利用C++、C#、java 实现堆排序并查看用时记录。

 

 

 

 

Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<