读书人

一个简略的堆排序的程序

发布时间: 2012-12-24 10:43:13 作者: rapoo

一个简单的堆排序的程序

#include <stdio.h>int parent(int i){    return i/2;}int left_child(int i){    return 2*i;}int right_child(int i){    return 2*i+1;}//n the range needed to sortvoid build_max_heap(int A[], int i, int n) // 数组A中,除A[i]外,其它元素是大顶堆 {    int max = i, temp;    if (i<0 || n<1 || i>=n)        return ;        /* find max element among a[i] a[left_child] a[right_child] */    if (left_child(i)<n && A[max]<A[left_child(i)])        max = left_child(i);    if (right_child(i)<n && A[max]<A[right_child(i)])        max = right_child(i);    // exchange a[i], a[max]    if (i!=max)    {        temp = A[i];        A[i] = A[max];        A[max] = temp;        build_max_heap(A, max, n);    }    return;    }void max_heap_sort(int A[], int n){    int temp;    // exchange A[0]  A[n-1]    if (n==1)        return ;    temp = A[0];    A[0] = A[n-1];    A[n-1] = temp;    build_max_heap(A, 0, n-1);    max_heap_sort(A, n-1);}int main(){    int A[10] = {5,8,9,52,47,65,3,45,26,81};        int i, n = 10;     for (i=(n-1)/2; i>=0; i--)    {        build_max_heap(A, i, n);    }    max_heap_sort(A, n);        for (i=0; i<n; i++)    {        printf("%d ", A[i]);    }    printf("\n");        system("pause");    return 0;}

?

读书人网 >编程

热点推荐