Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3835602
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8584
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-08-24 21:34:48

    堆排序,过去写过一次,最近写了很多排序算法,比上次实现,代码写的明显熟练了很多,最近的学习,有很多的进步。

    堆排序的算法优先级是NlogN。但是堆排序的性能是不如快速排序。高德纳老爷子的计算机程序设计艺术卷三 P148,提到:
    when N =1000, MIX的平均次数大概为:
    160000u    for  heapsort
    130000u    for  shellsort
    80000u     for  quicksort

    (最小)堆排序还存在另外一个问题,就是每次将最后一个元素和第一个元素交换,最后一个元素一般比较大,几乎总是比第一个元素的两个孩子大,所以比较从概率上将没有多大的含义。把最后的元素放到第一个元素位置上,heap_fixdown几乎总是一路比较,一路下滑。

     我们将堆排序考虑成一个部门的情况。老大退休了,将新入职的员工(即最后一个元素)推上部门老大的位置,然后原老大的两个副手选择出最优秀的一个(最小堆就是谁小谁优秀)和新入职的员工比,如果比新入职的员工优秀,则交换职位。新入职的员工几乎总是肯定败给原老大的两个副手中优秀的那个,新入职的员工从老大,第一层领导,降职为了第二层领导。而优秀的副手升为新的老大。但是新入职的员工变成2层领导,他直接领导的三层领导不乐意了,凭啥 你一个新兵蛋子来当我的领导。于是新入职的员工的两个手下PK出最优秀的,由优秀者代表三层,挑战新兵蛋子的权威,和新兵蛋子一比较,得,新兵蛋子又败了,再次和三层优秀者交换职位。新兵蛋子降为了三层领导。新兵蛋子直接领导的四层,又不乐意了,凭啥你一个新兵蛋子当三层领导,。。。。。悲催的新兵蛋子一路下滑,直到他没有下属了,或者所有的下属不如他优秀。这就是堆排序中删除堆顶元素发生的事情。

    高德纳老爷子的卷三P156的习题18中也提到了这一点。推荐大家阅读刘未鹏的博文
    第一次写的堆排序浪费了空间,需要额外的空间了。所以我改进了第二个版本的heapsort2。堆排序中由于前面是最小堆,每次选出最小的元素放在数组尾,导致,排完之后需要首位对调才能是从小到大排序。为了堆排序的快捷,从小到大排序,请用最大堆,从大到小排序,请用最小堆。


  1. #ifndef _HEAP_H
  2. #define _HEAP_H

  3. #define father(pos) ((pos-1)>>1)
  4. #define firstson(pos) ((pos<<1)+1)
  5. #define secondson(pos) ((pos+1)<<1)

  6. typedef struct _Heap{
  7.      int *array;
  8.      int number;
  9.      int maxlen;
  10. }Heap;



  11. extern int heap_init(Heap *heap,int maxlen );
  12. extern  int heap_destroy(Heap* heap);
  13. extern void heap_fixup(int array[],int pos);
  14. extern void heap_fixdown(int array[],int pos,int rlimit);
  15. extern int heap_insert(Heap* heap,int value);
  16. extern int heap_delmax(Heap *heap);
  17. extern int heapsort(int array[],int left,int right);

  18. #endif

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4. #include"heap.h"

  5. int test_heapsort()
  6. {
  7.     int i;
  8.     int number = 20;
  9.     
  10.     int *array = malloc(number*sizeof(int));
  11.     if(array == NULL)
  12.     {
  13.             printf("malloc failed\n");
  14.      return -1;
  15.     }
  16.   

  17.     printf("----------------------------------------before heap sort------------\n");
  18.     //srand(time(NULL));
  19.     for(i = 0;i<number;i++)
  20.     {
  21.         array[i] = rand()%1000;
  22.         printf("\tarray[%-6d] = %-6d\n",i,array[i]);
  23.     }

  24.     printf("----------------------------------------after heap sort-------------\n");
  25.     
  26.     heapsort(array,0,number-1);
  27.     for(i = 0;i<number;i++)
  28.     {
  29.         printf("\tarray[%-6d] = %-6d\n",i,array[i]);
  30.     }
  31.     free(array);
  32.     return 0;
  33.     
  34. }
  35. int main()
  36. {
  37.     test_heapsort();
  38. }
  1. #include
  2. #include
  3. #include"heap.h"

  4. int heap_init(Heap *heap,int maxlen)
  5. {
  6. heap->array = (int *)malloc(maxlen*sizeof(int));
  7. if(heap->array == NULL)
  8. {
  9.             printf("malloc failed for heap_init\n");
  10.    return -1;
  11. }

  12. heap->maxlen = maxlen;
  13. heap->number = 0;
  14. return 0;
  15. }

 int heap_destroy(Heap* heap)
 {
     if(heap->array)
        free(heap->array);

     heap->array = NULL;
     heap->number = 0;
     heap->max->len = 0;
     return 0;
 }
  1. void inline swap(int *x ,int *y)
  2. {
  3. int temp =*x;
  4. *x = *y;
  5. *y = temp;
  6. }


  7. void heap_fixup(int array[],int pos)
  8. {
  9. while(pos>0 && array[pos]
  10. {
  11.                swap(&array[pos],&array[father(pos)]);
  12.       pos = father(pos);
  13. }
  14. }

  15. void heap_fixdown(int array[],int pos,int rlmit)
  16. {
  17.      int j;

  18.        while(firstson(pos) <= rlimit)
  19.        {
  20.            j = firstson(pos);
  21.     if(j < rlimit && array[j] >array[j+1])
  22. j++;
  23.     if(array[pos] < array[j])  
  24. break;
  25.     swap(&array[pos],&array[j]);
  26.     pos = j;
  27.        }
  28. }


  29. int heap_insert(Heap* heap,int value)
  30. {
  31. if(heap->number +1 >(heap->maxlen))
  32. {
  33.             int *new_array = realloc(heap->array,(heap->maxlen)*2);
  34.    if(new_array == NULL)
  35.    {
  36.  printf("realloc for heap_insert failed\n");
  37. return -1;
  38.    }
  39.             heap->array = new_array;
  40.    heap->maxlen = heap->maxlen <<1;
  41. }
  42. heap->array[heap->number] = value;
  43. heap_fixup(heap->array,heap->number);
  44. heap->number++;
  45. return 0;
  46. }


  47. int heap_delmin(Heap *heap)
  48. {
  49. swap(&(heap->array[0]),&(heap->array[heap->number-1]));
  50. heap->number--;
  51. heap_fixdown(heap->array,0,heap->number-1);
  52. return heap->array[heap->number];/*return the smallest element */
  53. }


  54. int heapsort(int array[],int left,int right)
  55. {
  56. int len;
  57. Heap heap;
  58. int ret;
  59. int pos;
  60. if(array == NULL)
  61. {
  62.               return -1;
  63. }
  64. if(left > right)
  65. {
  66.               return -2;
  67. }
  68. if(left == right)
  69. {
  70.               return  0;
  71. }

  72. len = right - left + 1;
  73.         ret = heap_init(&heap,len);
  74. if(ret <0)
  75. return ret;
  76. for(pos = left ;pos<=right;pos++)
  77.     heap_insert(&heap,array[pos]);

  78. for(pos = left ; pos <= right; pos++)
  79.             array[pos] = heap_delmin(&heap);
  80.         heap_destroy(&heap)
  81. return 0;
  82. }

int heapsort2(int array[],int left ,int right)
{
if(array == NULL)
{
            return -1;
}

if(left > right)
{
            return -2;
}

if( left == right )
{
           return 0;
}

int len = right - left + 1;
        int i;
int * base = &(array[left]);
for(i = father(len-1); i >=0; i --)
{
           heap_fixdown(base,i,len-1);
}

while(len >0)
{
              swap(&base[0], &base[len-1]);
     len--;
     heap_fixdown(base,0,len-1);
}

        /*由于是最小堆,同时从小到大排序,所以需要将数组翻转。如果是最大堆就不用翻转了*/
int mid = (right+left)/2;

for(i = left ;i <= mid;i++)
{
            swap(&array[i],&array[left+right - i]);
}
 
        return 0;
}

阅读(5210) | 评论(3) | 转发(7) |
给主人留下些什么吧!~~

lixinqi07031062011-08-27 13:27:25

最好写成一个通用的模板,像qsort那把cmp比较函数做为参数传进去。

Bean_lee2011-08-26 19:30:33

呵呵 好主意,我应该 typedef int Item,然后对Item类型进行 排序,下次 float double ,只需要改动 typedef 就可以了。然后再定义compare 函数。 呵呵我比较懒。

RoverMo2011-08-26 19:25:16

lz对排序算法掌握得还不错,不过有点疑问。为什么lz只实现对int类型的排序,而不是所有基本数据类型的排序呢?