一个简单的堆排序的程序_C/C++_编程开发_程序员俱乐部

堆排序的小例子，可以参考一下

#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 sort
void 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;
}

?