堆排序法

堆排序法是选择排序法的一种。它的基本思想是，将无序区建成一个大头堆或小头堆。然后交换最顶端元素与最尾端元素，然后通过下虑将交换后的无序区重新修改成可用堆。依次类推，直到将所有元素排序完毕

算法

void percdown(int arr[], int i, int N)
{
    int tmp;
    int child;
    for(tmp = arr[i];  (2*i+1) < N; i=child)
    {
        child = 2 * i + 1;
        if (child != N -1 && arr[child + 1] > arr[child])
            child++;

        if(tmp < arr[child])
            arr[i] = arr[child];
        else
            break;
    }
    arr[i] = tmp;
}

void buildheap(int arr[], int N)
{
    int i;
    for(i = N / 2; i >=0; i++)
        percdown(arr[], i, N);
}

void heapsort(int arr[], int N)
{
    int i;
    buildheap(arr[], N);
    for(i=N - 1; i>0; i--)
    {
        arr[0] = arr[0] ^ arr[i];
        arr[i] = arr[0] ^ arr[i];
        arr[0] = arr[0] ^ arr[i];
   
        percdown(arr[], 0, N);
    }
   
}