算法导论——第二章——堆排序 算法导论第二章

http://www.ntnoi.cn/FLASH/arithmetic/各种算法的动态演示http://www.cnblogs.com/tanky_woo/算法学习的好地方http://hi.baidu.com/�˷�̤��2008/blog算法学习的好地方

最后,给大家推荐我在网上看到的写的不错的几篇堆排序文章:

1.http://blog.csdn.net/super_chris/archive/2009/09/22/4581900.aspx

这一篇讲得很细致。

2.http://blog.csdn.net/made_in_chn/archive/2010/04/12/5473871.aspx

大家可以看看文章里的图,注意那是最小堆实现的图。

3.http://blog.csdn.net/midgard/archive/2009/04/14/4070074.aspx

同样讲的很细致的一篇。

4.http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.2.htm

这是网站很给力,有flash模拟堆排序,大家可以实际去看看。

1.原地排序就是指不申请多余的空间来进行的排序,就是在原来的排序数据中比较和交换的排序。例如快速排序,堆排序等都是原地排序,合并排序,计数排序等不是原地排序。排序稳定就是指:如果两个数相同,对他们进行的排序结果为他们的相对顺序不变。
2堆的定义:  

n个关键字序列Kl,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):

(1)ki<=k(2i+1)且ki<=k(2i+2)(1≤i≤n),当然,这是小根堆,大根堆则换成>=号。//ki相当于二叉树的非叶结点,K2i则是左孩子,k2i+1是右孩子  

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:

树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

堆排序:

  堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlogn)。

  堆排序的特点是:在排序过程中,将排序数组看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)   的记录。

堆排序基本思想:

  1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。

  2.将大根堆的堆顶元素和无序区最后一个元素交换,并将无序区最后一个位置例入有序区,然后将新的无序区调整为大根堆。重复操作,无序区在递减,有序区在递增。

完全二叉树的基本性质:

  数组中有n个元素,i是节点,1 <= i <= n/2就是说数组的后一半元素都是叶子节点。

i的父节点位置:i/2

i左子节点位置:i*2

i右子节点位置:i*2 + 1

length[A]是数组中的元素个数,heap-size[A]是存放在A中的堆的元素个数

下面我是按照算法导论中给出的算法,利用c++实现了堆排序,调试通过。

#include <iostream>
using namespace std;
int data[10]={71,18,151,138,160 ,63 ,174, 169 ,79 ,78 };
void max_heapify(int data[],int i,int heapsize)//以某个节点为根节点的子树进行调整,调整为大顶堆
{
int l=2*i+1;
int r=2*i+2;
int largest=i;
if(l<heapsize&&data[l]>data[i])
{
largest=l;
}
if(r<heapsize&&data[r]>data[largest])
{
largest=r;
}
if(largest!=i)
{
int temp=data[largest];
data[largest]=data[i];
data[i]=temp;
max_heapify(data,largest,heapsize);
}
}
void bulid_max_heap(int data[],int heapsize)//建堆的过程,通过自底向上地调用max_heapify来将一个数组data【1……n】变成一个大顶堆,
{                         //只需要对除了叶子节点以外的节点进行调整
for(int i=heapsize/2-1;i>=0;i--)
max_heapify(data,i,heapsize);
}
void heap_sort(int data[],int heapsize)//堆排序算法实现主体:先用bulid_max_heap将输入数组构造成大顶堆,
{                       //然后将data【0】和堆的最后一个元数交换,继续进行调整。
bulid_max_heap(data,heapsize);
for(int i=heapsize-1;i>0;i--)
{
int t=data[0];
data[0]=data[i];
data[i]=t;
max_heapify(data,0,i);

}
}
int main()
{
cout<<"堆排序算法实现"<<endl;
cout<<"排序之前的数据:";
for(int i=0;i<10;i++)
cout<<data[i]<<" ";
cout<<endl;
算法导论——第二章——堆排序 算法导论第二章
heap_sort(data,10);
cout<<"排序之后的数据:";
for(i=0;i<10;i++)
cout<<data[i]<<" ";
cout<<endl;
return 0;
}

  

爱华网本文地址 » http://www.413yy.cn/a/25101017/327750.html

更多阅读

快速排序-算法导论版本 算法导论 排序网络

快速排序算法和合并排序算法一样,也是基于分治模式。对子数组A[p...r]快速排序的分治过程的三个步骤为:分解:把数组A[p...r]分为A[p...q-1]与A[q+1...r]两部分,其中A[p...q-1]中的每个元素都小于等于A[q]而A[q+1...r]中的每个元素都大于

从小到大排序算法 java从小到大排序

查看文章 10种排序算法总结(冒泡、选择、插入、希尔、归并、快速、堆、拓扑、锦标赛、基数)2011年01月20日星期四 08:24P.M.排序算法有很多,所以在特定情景中使用哪一种算法很重要。为了选择合适的算法,可以按照建议的顺序考虑以下标

关于排序网络 算法导论 排序网络

突然发现自己一个礼拜以上没有写日志了,并且上一篇纯属吐槽。不行,不能这么堕落!今天在黑书上看见排序网络。恩。发现真是个好东西。不知道为什么自己特别喜欢像自动机啦,排序网络之类的这种可以实现“自动”干什么什么的,并且能够多次

判断一个序列是否是堆排序 判断子序列

例如:判断15,30,22,93,52,71是不是堆排序这个序列是堆排序的结果。判断是否为堆排序,要根据堆排序的两点性质来判断,分别是:(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)//ki相当于二叉树的非叶结点,K2i则是左孩子,k2i+1

几种排序以及其时间复杂度 堆排序时间复杂度

看了学姐的面试题,突然很想知道答案,就去百度上搜了一下:1.选择排序:不稳定,时间复杂度 O(n^2)选择排序的基本思想是对待排序的记录序列进行n-1遍的处理,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位

声明:《算法导论——第二章——堆排序 算法导论第二章》为网友孤久则安分享!如侵犯到您的合法权益请联系我们删除