首页 > algorithm > 排序3(堆排序)

排序3(堆排序)

  端午节快乐!今天再看一个算法。
  堆排序是采用顺序存储表示,用一个数组表示,但是逻辑上是一个堆,用堆的思维进行排序。
  首先,先建立一个大顶堆(maxHeapFather),就是每一个父亲都比子女的数值大。遍历的每一个元素都确定自己的儿子(包括孙子、重孙子)都是一个大顶堆,
  其次,开始建一个堆,遍历n/2个点后,就成了一个最大的大顶堆。然后进行排序,把顶部的最大数与最后一个数进行调换,之后再把n-1个数,在进行堆排序,一直重复到最后,就成了一个有序的队列。
  算法分析:堆排序方法对记录少的文件效率不高,主要是n很大的文件上,因为运行时间主要花在了建初始的大堆和建新堆时的反复“筛选”上!对深度为k的堆,筛选算法中进行的关键字比较次数最多为2(k-1)次,则在建含有n个元素、深度为h的堆时,总共进行的关键字比较次数不超过4n次。在最坏的情况下,其时间复杂度也为O(nlgn)
  总结反思:
  注意1:在调试的过程中,堆顶应该从1开始,这样左边的树=2*i,右边的树为2*i+1。
  注意2:什么叫伪码?就是非常不能运行的语言。还是自己的功底不行吧,在内容的实现方面还是有点卡壳,伪码与实现的距离很远啊!

#include<stdio.h>
#define PARENT(i) ((i)/2)
#define LEFT(i) (2*i)
#define RIGHT(i) (2*i+1)
static heapSize=10;

void maxHeapFather(int * a,int i)
{
int l=LEFT(i);
int r=RIGHT(i);
int largest=i,t;
if(la[i])
largest=l;
if(ra[largest])
largest=r;
if(largest!=i)
{
t=a[i];
a[i]=a[largest];
a[largest]=t;
maxHeapFather(a,largest);
}
return;
}
void buildMaxHeap(int *a)
{
int i;
for(i=heapSize/2;i>=1;i–)
maxHeapFather(a,i);
return;
}
void heapSort(int *a)
{
int i,t;
buildMaxHeap(a);
for(i=heapSize;i>1;i–)
{
t=a[1];
a[1]=a[i];
a[i]=t;
heapSize–;
maxHeapFather(a,1);
}
}
int main()
{
int i,a[11]={0,4,5,7,8,1,9,3,6,11,2};
heapSort(a);
for(i=1;i<11;i++)
printf(“%d “,a[i]);
printf(“\n”);
return 0;
}

  1. Emmanuel 9月 2nd, 2012 @ 05:10 | #1

    Kick the tires and light the fires, problem officially sloved!

评论提交中, 请稍候...

留言


可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 0 )
  1. 还没有 trackbacks