[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
|
