堆排序，C版

C语言: 堆排序，C版

#include <stdio.h>
#include <math.h>


#define LEFT(i)        ((i)<<1)
#define RIGHT(i)    (((i)<<1) + 1)

void max_heapify(int a[], int i, int heapsize);
void heap_sort(int a[], int heapsize);
void build_max_heap(int a[], int heapsize);
void exchange(int *x, int *y);

//交换两个数的值
void exchange(int *x, int *y) {
    int temp;

    temp = *x;
    *x = *y;
    *y = temp;
}

//保持最大堆性质
void max_heapify(int a[], int i, int heapsize) {
    int left, right, largerest;

    left = LEFT(i);
    right = RIGHT(i);

    if (left <= heapsize && a[left]>a[i])
    {
        largerest = left;
    }else{
        largerest = i;
    }

    if (right <= heapsize && a[right]>a[largerest])
    {
        largerest = right;
    }

    if(largerest != i) {
        exchange(&a[i], &a[largerest]);
        max_heapify(a, largerest, heapsize);
    }

}

//建造最大堆
void build_max_heap(int a[], int heapsize) {
    int i;

    for (i=(int)ceil(heapsize/2); i >=1 ; i--)
    {
        max_heapify(a, i, heapsize);
    }
}

//堆排序
void heap_sort(int a[], int heapsize) {

    //build heap
    build_max_heap(a, heapsize);

    while(heapsize>1)
    {
        //exchange max
        exchange(&a[1], &a[heapsize]);
        heapsize--;
        max_heapify(a, 1, heapsize);
    }
   
}

int main() {
    int a[] = {0,    2,        0,        23,        38,        19,
                    98,        203,    803,    3,        78,
                    34,        68,        49,        9,        55};
   
    int array_size = sizeof(a)/sizeof(int);
    int i,heapsize;

    heapsize = array_size - 1;

    heap_sort(a, heapsize);
   
    //打印排序后的数组
    for (i=1; i<=heapsize ; i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
    getchar();
    return 0;

}