随笔 - 13  文章 - 36  trackbacks - 0
<2009年5月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(2)

随笔档案

友情链接

搜索

  •  

最新评论

阅读排行榜

评论排行榜

                                                                      堆排序算法

                                                                                                               ---------- C++博客 Alex-Lee   2009-10-15

      (二叉)堆结构是一种数组对象,它可以被视为一颗完全二叉树。算法时间复杂度O(nlgn),具有插入排序和合并排序的优点。堆结构满足堆性质:对除根以外的每个节点i,满足A[PARENT(i)] >= A[i]。
   
       堆排序算法实现有三个部分完成:
1,保持堆性质函数heap_ify;
2,构建堆函数build_heap;
3,堆排序函数 heap_sort;
另外,在优先级队列中有extract-max 过程和insert过程,在作业队列中常用,比如消息队列。这部分在优先级排序中说明。

实现:
1,数据元素结构(使用int作为实现版本)
typedef struct int_array
{
 int *pa;
 int array_size;
} INT_ARRAY;

2,swap
void swap(int *pa,int *pb)
{
 int tmp;
 tmp = *pa;
 *pa = *pb;
 *pb = tmp;
}

3, tree child define
//结点标识从0开始算,算其左右孩子结点宏
#define LEFT(i)  2*i +1
#define RIGHT(i) 2*i +2

4,heap_ify
//使得以i给根结点的树满足堆特性a[i]>=a[child(i)]
static void heap_ify(INT_ARRAY *pia,int heap_size,int i)
{
 int left,right,largest;

 left = LEFT(i);
 right = RIGHT(i);

 //找出i结点与其左右孩子结点的值的最大者
 if (left <= heap_size && pia->pa[left] > pia->pa[i])
 {
  largest = left;
 }
 else
 {
  largest = i;
 }
 if (right <= heap_size && pia->pa[right] > pia->pa[largest])
 {
  largest = right;
 }

 if (largest != i)
 {//如果i结点值比子结点值小,那么与孩子结点最大值交换
  swap(&pia->pa[i],&pia->pa[largest]);
  //保证交换数据后的子树还能满足堆特性
  heap_ify(pia,heap_size,largest);
 }
}
5,build_heap

//创建堆后,整个树满足a[parent(i)]>=a[i];
static void build_heap(INT_ARRAY *pia)
{
 int i;
 for (i = pia->array_size/2;i >= 0 ;--i)
 {
  heap_ify(pia,pia->array_size,i);
 }
}
6,heap_sort
//首先创建堆,由于a[0]总是保存最大树,
//将a[0]置换到a[n-i],这样完成升序排序。
void heap_sort(INT_ARRAY *pia)
{
 int i,heap_size;
 heap_size = pia->array_size -1;
 build_heap(pia);
 //print_sort(pa,len,"after build heap");
 for (i = pia->array_size -1; i > 0;--i)
 {
  swap(&pia->pa[0],&pia->pa[i]);
  heap_size --;
  heap_ify(pia,heap_size,0);
 }
}

代码:heap-sort算法代码
堆排序算法效率还是不错的,虽然可能比不上快速排序,今天测试了2次,1千万整数排序不超过20秒。

                                                                                 

posted on 2009-10-15 21:01 Alex-Lee 阅读(1590) 评论(1)  编辑 收藏 引用

FeedBack:
# re: 堆排序算法 2009-10-17 11:47 egmkang
我试过自己写快排,1000W int32,需要6秒时间.  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理