快速排序

#include <stdio.h>

void myPrint(int *A, int len);
void mySwap(int *A, int *B);
int partition(int *A, int start, int end);
void quickSort(int *A, int start, int end);

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);
        quickSort(a, 0, len-1);
        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
partition(int *A, int start, int end)
{
        int key = *(A+start);
        int i = start + 1;

        while (i <= end) {
                if (key >= *(A+i)) {
                        *(A+i-1) = *(A+i);
                        i++;
                } else {
                        mySwap(A+i, A+end);
                        end--;
                }
        }
        *(A+i-1) = key;

        return (i-1);
}

void
quickSort(int *A, int start, int end)
{
        int base;
        if (start < end) {
                base = partition(A, start, end);
                quickSort(A, start, base-1);
                quickSort(A, base+1, end);
        }
}

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