C++简单交换堆排序

C++简单交换堆排序

/* Can easily be modified to work with other data types */
 
void heapsort(int *arr, int n)
{
    int start, end;
 
    // heapify the array
    for(start = (n - 2) / 2; start >= 0; --start) // for every root
        siftDown(arr, start, n); // sift through it
     
    // sort the array
    for(end = n - 1; end; --end) // for every element of the heap
    {
        swapi(&arr[end], &arr[0]); // swap it with the top root
        siftDown(arr, 0, end); // rebuild the heap
    }
}
 
void siftDown(int *arr, int start, int end)
{
    int root, child;
 
    root = start; // pick the root index
    while(2 * root + 1 < end) // while the root has a child
    {
        child = 2 * root + 1; // pick its index
        if((child + 1 < end) && (arr[child] < arr[child+1]))
            ++child; // if the other child is bigger, pick it instead
        if(arr[root] < arr[child]) // if root is smaller than the child
        {
            swapi(&arr[child], &arr[root]); // swap them
            root = child; // go down the heap
        }
        else // if the child is smaller than the root
            return; // that root is in the right spot
    }
}
 
void swapi(int *x, int *y)
{
    int z;
     
    z = *x;
    *x = *y;
    *y = z;
}