Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4711150
  • 博文数量: 930
  • 博客积分: 12070
  • 博客等级: 上将
  • 技术积分: 11448
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-15 16:57
文章分类

全部博文(930)

文章存档

2011年(60)

2010年(220)

2009年(371)

2008年(279)

分类: LINUX

2009-05-17 13:27:38

[root@mip-123456 stack_sort]# cat stack.c
#include <stdio.h>

#define N 10
#define PARENT(i) (i-1)/2
#define LEFT(i) 2*(i)+1
#define RIGHT(i) 2*(i+1)

int heap_size = N;

inline int exchange(int* a,int* b)
{
 *a^=*b;
 *b^=*a;
 *a^=*b;
  
 return 0;
}

int max_heapify(int* A,int i)
{
  int l = 0;
  int r = 0;
  int largest = 0;

  l = LEFT(i);
  r = RIGHT(i);

  if((l<heap_size) && (*(A+l)>*(A+i)))
   largest = l;
  else
   largest = i;

  if((r<heap_size) && (*(A+r)>*(A+largest)))
   largest = r;

  if(largest != i)
    {
     exchange(A+i,A+largest);
     return max_heapify(A,largest);
     }

  return 0;
}

int build_max_heap(int* A)
{
 heap_size = N;
 int i = 0;
 
 for(i=heap_size/2-1;i>=0;i--)
   max_heapify(A,i);

 return 0;
}

int heap_sort(int* A)
{
 int i = 0;
// int j = 0;

 heap_size = N;

 build_max_heap(A);

 for(i=N-1;i>0;i--)
  {
 // printf("exchange 0 %d value: %d %d\n",i,*(A+0),*(A+i));

    exchange(A+0,A+i);
  // printf("after exchange 0 %d value: %d %d\n",i,*(A+0),*(A+i));

    heap_size--;
    max_heapify(A,0);
   #if 0
    for(j=0;j<=i;j++)
      printf("%5d",*(A+j));
    printf("\n");
   #endif
  }

  return 0;
}

int main()
{
 int i = 0;
 int A[N] = {16,14,10,8,7,9,3,2,4,1};
 printf("before sort:\n");
 for(i=0;i<N;i++)
   printf("%5d",*(A+i));

 printf("\nafter sort:\n");
 heap_sort(A);
 for(i=0;i<N;i++)
   printf("%5d",*(A+i));

  
  printf("\n");

 return 0;
}
[root@mip-123456 stack_sort]# ./stack
before sort:
   16 14 10 8 7 9 3 2 4 1
after sort:
    1 2 3 4 7 8 9 10 14 16

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