Chinaunix首页 | 论坛 | 博客

wangcong02345wangcong02345.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

wangcong02345

  • 博客访问： 2151546
  • 博文数量： 438
  • 博客积分： 3871
  • 博客等级： 中校
  • 技术积分： 6075
  • 用 户 组： 普通用户
  • 注册时间： 2011-09-10 00:11
个人简介

邮箱: wangcong02345@163.com

文章分类

全部博文（438）

文章存档

2017年（15）

2016年（119）

2015年（91）

2014年（62）

2013年（56）

2012年（79）

2011年（16）

我的朋友
最近访客
推荐博文
相关博文
算法---6.堆排序

分类： LINUX

2016-08-06 14:56:57

0. 堆排序包括两个部分   (只讨论由小到大排序这种情况)
    a. 建堆        --> 建立一个大顶，从第一个非叶结点开始由下到上调整堆
    b. 堆排序  
             因为是大顶堆，max=arr[0],所以将arr[0] 与 arr[end]交换，然后[0-end-1]重新生成一个大顶堆 
             现在max=arr[0],再将arr[0] 与 arr[end-1]交换，然后[0-end-2]重新生成一个大顶堆 
             以此类推
             直至堆中只剩一个元素，堆排序过程结束
1.1 建堆的过程
对每一个非叶结点 建立一个大顶，从第一个非叶结点开始由下到上调整堆

1.2建堆的过程
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
  4. #define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))
  5. #define SWAP2(x,y) \
  6.     do{ if((x)<(y)) \
  7.         SWAP((x),(y));} \
  8.     while(0)
  9. #define POW(x) (1<<(x))
  10. #define L(x) (2*(x)+1) //left child
  11. #define R(x) (2*(x)+2) //right child
  12. int dump_array(int* arr, int len)
  13. {
  14.     int i;
  15.     for(i=0; i<len; i++)
  16.     {
  17.         printf("%d ", arr[i]);
  18.     }
  19.     printf("\n");
  20.     return 0;
  21. }

  23. int is_sum_pow2(int n)
  24. {
  25.     int t = n+1;
  26.     return n&t;
  27. }

  29. int get_level(int num)
  30. {
  31.     int ret;
  32.     __asm__ volatile("movl %1,%%ecx\n"
  33.         "xor %%eax, %%eax \n"
  34.         "bsr %%ecx, %%eax \n"
  35.         "movl %%eax, %0 \n":"=r"(ret):"r"(num):);
  36.     return ret;
  37. }

  39. int dump_tree(int* arr, int len)
  40. {
  41.     int i,j;
  42.     int level = get_level(len)+1;
  43.     int first = 1;
  44.     printf("<------------------\n");
  45.     for(i=0; i<len; i++)
  46.     {
  47.         if(first)
  48.         {
  49.             for(j=0; j<POW(level-1)-1; j++)
  50.                 printf(" ");
  51.             first = 0;
  52.         }else {
  53.             for(j=0; j<POW(level)-1; j++)
  54.                 printf(" ");
  55.         }
  56.         printf("%2d", arr[i]);
  57.         if( is_sum_pow2(i+1) == 0)
  58.         {
  59.             printf("\n");
  60.             level--;
  61.             first = 1;
  62.         }
  63.     }
  64.     printf("\n");
  65.     
  66.     printf("------------------>\n");
  67.     return 0;
  68. }

  70. int heap_adjust(int* arr,int s, int len)
  71. {
  72.     int i = s;
  73.     int temp;
  74.     int max;
  75.     while(i < (len-1))                           //长度是len，但数组下标是[0-len-1]
  76.     {
  77.         if(L(i) > len-1)                         //如果左结点的下标己超过了数组的总长度，说明左结点不存在  
  78.             break;                               //堆是一棵完全二叉树，左结点不存在说明这个是叶结点
  79.         if( (R(i)<(len-1)) && (arr[L(i)] < arr[R(i)]))   //判断右结点是否存在，存在且大于左结点 
  80.             max = R(i);                                  //说明子结点中右结点的值大
  81.         else
  82.             max = L(i);                                   
  83.          //到这儿己经找出最大的子结点的索引,然后parent与child相比较
  84.         if(arr[i] < arr[max])                            //若p < c，则需要交换并调整
  85.         {
  86.             SWAP(arr[i], arr[max]);                      //交换p与c的位置
  87.             //arr[i] = arr[max];
  88.         }else {
  89.             break;                                       //p > c,说明这一支都不需要调整,直接break
  90.         }
  91.         i = max;                                         //然后在下一次循环中进行调整
  92.         dump_tree(arr, len);
  93.     }
  94.     //dump_tree(arr, len);
  95.     return 0;
  96. }

  98. int heap_sort(int* arr, int len)
  99. {
  100.     int i;
  101.     //1. build heap
  102.     for(i=len/2-1; i>=0; i--)             //第一个非叶结点的位置是len/2-1
  103.     {
  104.         printf("%d=%d\n", i, arr[i]);
  105.         heap_adjust(arr, i, len);
  106.     }
  107.     dump_tree(arr, len);
  108.     printf("next heap sort ----\n");
  109. #if 0
  110.     //heap sort
  111.     for(i=len-1; i>0; i--)
  112.     {
  113.         SWAP(arr[0], arr[i]);
  114.         heap_adjust(arr, 0, i-1);
  115.         printf("%d=%d\n", i, arr[i]);
  116.         dump_tree(arr, len);
  117.     }
  118. #endif
  119. }

  121. int main ( int argc, char *argv[] )
  122. {
  123.     //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
  124.     int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
  125.     int len = sizeof(arr)/sizeof(int);
  126.     dbmsg("array len=%d", len);
  127.     dump_tree(arr, len);
  128.     heap_sort(arr, len);
  129.     printf("after heap sort\n");
  130.     dump_tree(arr, len);
  131.     dump_array(arr, len);
  132.     return EXIT_SUCCESS;
  133. }
1.3 执行结果如下
  1. heap.c:main[125]: array len=10
    <------------------
                  49
          38              65
      97      76      13      27
    49  55   4
    ------------------>
    4=76    -->76 4     不用调整 
    3=97    -->97 49 55 不用调整  
    2=65    -->65 13 27 不用调整 
    1=38    -->38 97 76 要调整
    <------------------
                  49
          97              65              -->38 97 76中97最大，将97与38交换，再调整38这一支
      38      76      13      27
    49  55   4
    ------------------>
    <------------------
                  49
          97              65
      55      76      13      27          -->38 49 55中55最大，将55与38交换，38是叶结点了，调整结束
    49  38   4
    ------------------>
    0=49
    <------------------
                  97                      -->49 97 65中97最大，将97与49交换，再调整49这一支
          49              65
      55      76      13      27
    49  38   4
    ------------------>
    <------------------
                  97
          76              65
      55      49      13      27           -->49 55 76中76最大，将76与49交换，再调整49这一支
    49  38   4
    ------------------>
    <------------------
                  97
          76              65
      55      49      13      27           -->49 4中49最大，不用调整，调整结束
    49  38   4
    ------------------>
    next heap sort ----
    after HeapSort
    <------------------
                  97
          76              65
      55      49      13      27
    49  38   4
    ------------------>
    97 76 65 55 49 13 27 49 38 4 
2.1 堆排序的过程
上一步己经建成一个大顶堆了，堆顶元素就是要排序数据的最大值
把最大值交换到数组的结尾，然后把剩下的数据再排成一个大顶堆，这样就找出了次大值
以此类推
虽然中间过程一直是大顶堆，最后输出总的数组时却是一个小顶堆，这样就完成了排序。

2.2 堆排序
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
  4. #define SWAP(x,y) (x=(x)+(y),y=(x)-(y),x=(x)-(y))
  5. #define SWAP2(x,y) \
  6.     do{ if((x)<(y)) \
  7.         SWAP((x),(y));} \
  8.     while(0)
  9. #define POW(x) (1<<(x))
  10. #define L(x) (2*(x)+1) //left child
  11. #define R(x) (2*(x)+2) //right child
  12. int dump_array(int* arr, int len)
  13. {
  14.     int i;
  15.     for(i=0; i<len; i++)
  16.     {
  17.         printf("%d ", arr[i]);
  18.     }
  19.     printf("\n");
  20.     return 0;
  21. }

  23. int is_sum_pow2(int n)
  24. {
  25.     int t = n+1;
  26.     return n&t;
  27. }

  29. int get_level(int num)
  30. {
  31.     int ret;
  32.     __asm__ volatile("movl %1,%%ecx\n"
  33.         "xor %%eax, %%eax \n"
  34.         "bsr %%ecx, %%eax \n"
  35.         "movl %%eax, %0 \n":"=r"(ret):"r"(num):);
  36.     return ret;
  37. }

  39. int dump_tree(int* arr, int len)
  40. {
  41.     int i,j;
  42.     int level = get_level(len)+1;
  43.     int first = 1;
  44.     printf("<------------------\n");
  45.     for(i=0; i<len; i++)
  46.     {
  47.         if(first)
  48.         {
  49.             for(j=0; j<POW(level-1)-1; j++)
  50.                 printf(" ");
  51.             first = 0;
  52.         }else {
  53.             for(j=0; j<POW(level)-1; j++)
  54.                 printf(" ");
  55.         }
  56.         printf("%2d", arr[i]);
  57.         if( is_sum_pow2(i+1) == 0)
  58.         {
  59.             printf("\n");
  60.             level--;
  61.             first = 1;
  62.         }
  63.     }
  64.     printf("\n");
  65.     
  66.     printf("------------------>\n");
  67.     return 0;
  68. }

  70. int heap_adjust(int* arr,int s, int len)
  71. {
  72.     int i = s;
  73.     int temp;
  74.     int max;
  75.     while(i < (len-1))
  76.     {
  77.         if(L(i) > len-1)
  78.             break;
  79.         if( (R(i)<(len-1)) && (arr[L(i)] < arr[R(i)]))
  80.             max = R(i);
  81.         else
  82.             max = L(i);
  83.         if(arr[i] < arr[max])
  84.         {
  85.             SWAP(arr[i], arr[max]);
  86.             //arr[i] = arr[max];
  87.         }else {
  88.             break;
  89.         }
  90.         i = max;
  91.         //dump_tree(arr, len);
  92.     }
  93.     //dump_tree(arr, len);
  94.     return 0;
  95. }

  97. int heap_sort(int* arr, int len)
  98. {
  99.     int i;
  100.     //1. build heap
  101.     for(i=len/2-1; i>=0; i--)
  102.     {
  103.         printf("%d=%d\n", i, arr[i]);
  104.         heap_adjust(arr, i, len);
  105.     }
  106.     printf("build heap over");
  107.     dump_tree(arr, len);
  108.     printf("next heap sort ----\n");
  109. #if 1
  110.     //heap sort
  111.     for(i=len-1; i>0; i--)                      //从最后一个结点开始调整 
  112.     {
  113.         SWAP(arr[0], arr[i]);                    //0与end交换
  114.         heap_adjust(arr, 0, i-1);                //再调整成一个大顶堆 
  115.         printf("%d=%d", i, arr[i]);
  116.         dump_tree(arr, len);
  117.     }
  118. #endif
  119. }

  121. int main ( int argc, char *argv[] )
  122. {
  123.     //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
  124.     int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
  125.     int len = sizeof(arr)/sizeof(int);
  126.     printf("array len=%d, before sort", len);
  127.     dump_tree(arr, len);
  128.     heap_sort(arr, len);
  129.     printf("after heap sort");
  130.     dump_tree(arr, len);                            //最终结是是一个小顶堆
  131.     dump_array(arr, len);
  132.     return EXIT_SUCCESS;
  133. }


3.3 执行结果如下:
  1. array len=10, before sort<------------------
                  49
          38              65
      97      76      13      27
    49  55   4
    ------------------>
    4=76
    3=97
    2=65
    1=38
    0=49
    build heap over<------------------    //建了一个大顶堆
                  97
          76              65
      55      49      13      27
    49  38   4
    ------------------>
    next heap sort ----
    9=97<------------------              //将堆顶的97与最后的4交换，然后重新建大顶堆
                  76
          55              65
      49      49      13      27
     4  38  97
    ------------------>
    8=76<------------------               //将堆顶的76与倒数第二的38交换，然后重新建大顶堆
                  65
          55              38
      49      49      13      27
     4  76  97
    ------------------>
    7=65<------------------
                  55
          49              38
       4      49      13      27
    65  76  97
    ------------------>
    6=55<------------------
                  49
          27              38
       4      49      13      55
    65  76  97
    ------------------>
    5=49<------------------
                  38
          27              13
       4      49      49      55
    65  76  97
    ------------------>
    4=38<------------------
                  49
          27              13
       4      38      49      55
    65  76  97
    ------------------>
    3=49<------------------
                  27
           4              13
      49      38      49      55
    65  76  97
    ------------------>
    2=27<------------------
                  13
           4              27
      49      38      49      55
    65  76  97
    ------------------>
    1=13<------------------
                   4
          13              27
      49      38      49      55
    65  76  97
    ------------------>
    after heap sort<------------------
                   4
          13              27
      49      38      49      55
    65  76  97
    ------------------>
    4 13 27 49 38 49 55 65 76 97
3.4 注意
a. 如果在堆排序过程中有如下数据
  49
65  76
49 65 76中最大的数是76,只需要将76与49交换即可,然后再调整49这一支的数据，65这一支不动即可

  76
65  49
而只需要将76与49交换即可,不需要再将65与49交换.
  76
49  65
3.5 代码 
6heap.rar   (下载后改名为heap.tar.gz)





阅读(983) | 评论(0) | 转发(0) |
0

上一篇：算法---6.堆排序之树形打印

下一篇：算法---7.归并排序

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6