Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1006657
  • 博文数量: 150
  • 博客积分: 3017
  • 博客等级: 少校
  • 技术积分: 3829
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-19 14:40
个人简介

Now in Baidu WISE team

文章分类

全部博文(150)

文章存档

2014年(8)

2013年(31)

2012年(111)

分类: C/C++

2012-12-17 00:25:18

根据《算法导论》堆排序一节的描述实现。
代码如下(已验证)

点击(此处)折叠或打开

  1. #define LEFT(a) ((a)<<1)+1
  2. #define RIGHT(b) ((b)<<1)+2
  3. #define swap(a,b) a ^=b;b^=a;a^=b
  4. void output(int input[], int size){
  5.     if(input == NULL) return;
  6.     int i = 0;
  7.     while(i<size){
  8.         printf("%d ",input[i]);
  9.         i++;
  10.     }
  11.     printf("\n");
  12. }

  13. void MaxHeapify(int input[], int tar, int size){
  14.     if(input == NULL) return;
  15.     int largest = tar;
  16.     if(LEFT(tar)<size && input[LEFT(tar)]>input[tar]){
  17.         largest = LEFT(tar);
  18.     }
  19.     if(RIGHT(tar)<size && input[RIGHT(tar)]>input[largest]){
  20.         largest = RIGHT(tar);
  21.     }
  22.     if(tar!=largest){
  23.         swap(input[tar], input[largest]);
  24.         MaxHeapify(input,largest, size);
  25.     }

  26. }

  27. void CreateHeap(int input[], int size){
  28.     if(input == NULL) return;
  29.     int root = (size-1)>>1;
  30.     for(;root>=0;root--){
  31.         MaxHeapify(input, root,size);
  32.     }
  33. }
  34. void HeapSort(int input[], int size){
  35.     if(input == NULL) return;
  36.     CreateHeap(input, size);
  37.     int end = size-1;
  38.     for(;end>0;end--){
  39.         swap(input[0],input[end]);
  40.         printf("Select Max %d endIndex = %d\n", input[end],end-1);
  41.         MaxHeapify(input,0,end);
  42.         output(input, size);
  43.     }
  44. }


  45. int main(){
  46.     int input[] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
  47.     int size = sizeof(input)/sizeof(int);
  48.     HeapSort(input, size);
  49.     output(input,size);
  50. }


阅读(1175) | 评论(0) | 转发(6) |
给主人留下些什么吧!~~