一个简单的堆排序，搞了半天，汗～～

/*
 * =====================================================================================
 *
 *       Filename:  heap_sort.c
 *
 *    Description:  堆排序
 *
 *        Version:  1.0
 *        Created:  2011年09月28日 20时09分46秒 CST
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  nestor 
 *        Company:  
 *
 * =====================================================================================
 */

#include "stdio.h"
#define length 10

int heap_size;

void max_heappify(int a[],int i); 
void build_max_heap(int a[]);
void heap_sort(int a[]);
int left(int i); 
int right(int i); 
int main(void)
{
    int a[length+1]={0,45,324,4,54,324,4,54,65,67,43},i;
    printf("please input 10 numbers to sort\n");
//  for(i=1;i<length+1;i++)
//      scanf("%d",&a[i]);

    heap_sort(a);
    for(i=1;i<length+1;i++)
    {

        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

void max_heappify(int a[],int i)
{
    int l, r, largest, temp;
    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)
    {
        temp=a[i];
        a[i]=a[largest];
        a[largest]=temp;
        max_heappify(a, largest);
    }
}
void build_max_heap(int a[])
{
    int i;
    heap_size=length;
    for(i=heap_size/2;i>=1;i--)
    {
        max_heappify(a, i);
    }
}
void heap_sort(int a[])
{
    int i,temp;
    build_max_heap(a);
    for(i=length;i>=1;i--)
    {
        temp=a[i];
        a[i]=a[1];
        a[1]=temp;
        heap_size--;
        max_heappify(a,1);
    }
}
int left(int i)
{
    return 2*i;
}
int right(int i)
{
    return 2*i+1;
}

• 相关文章