堆排序

#include <stdio.h>

void myPrint(int *A, int len);
void mySwap(int *A, int *B);
int left(int i);
int right(int i);
void maxHeapV(int *A, int i, int len);
void buildMaxHeap(int *A, int len);
void heapSort(int *A, int len);

int
main(void)
{
        int a[] = {1,3,5,7,9,0,2,4,6,8,0};
        int len = sizeof(a)/sizeof(a[0]);

        myPrint(a, len);
        heapSort(a, len);
        myPrint(a, len);

        return (0);
}

void
myPrint(int *A, int len)
{
        printf("Enter: ");
        int i = 0;
        for (i = 0; i < len; i++) {
                printf("%d,",*(A+i));
        }
        printf("\n");
}

void
mySwap(int *A, int *B)
{
        int tmp;
        tmp = *A;
        *A = *B;
        *B = tmp;
}

int
left(int i)
{
        return (2*i);
}

int
right(int i)
{
        return (2*i + 1);
}

void
maxHeapV(int *A, int i, int len)
{
        int lf = left(i);
        int rt = right(i);
        int largest;
        int tmp;
        if (lf < len && *(A+lf) > *(A+i))
                largest = lf;
        else
                largest = i;

        if (rt < len && *(A+rt) > *(A+largest))
                largest = rt;

        if (largest != i) {
                mySwap(A+largest, A+i);
                maxHeapV(A, largest, len);
        }
}

void
buildMaxHeap(int *A, int len)
{
        int i;
        for (i = len-1; i >=0; i--) {
                maxHeapV(A, i, len);
        }
}
void
heapSort(int *A, int len)
{
        int i;
        buildMaxHeap(A, len);
        for (i = len-1; i > 0; i--) {
                mySwap(A+i, A+0);
                len--;
                maxHeapV(A, 0, len);
        }
}

稳定性：非稳定
T(n)：Θ(nlogn)
S(n): O(1)