快速排序

    快速排序：和归并排序相反，快速排序注重前期的分，归并排序注重后期的并，具体实现参加代码。

#include <stdio.h>

void quickSort(int *a, int start, int end);

int
main(int argc, char **argv)
{
    int a[] = {2,4,6,8,1,3,5,7,9,0};
    int n = sizeof(a) / sizeof(a[0]);

    quickSort(a, 0, n-1);

    printf("Result:");
    int i;
    for (i = 0; i < n; i++) {
        printf("%d,", a[i]);
    }
    printf("\n");

    return 0;
}

int
partition(int *a, int start, int end)
{
    int tag = a[end];
    int i = start - 1;
    int j;
    int tmp;

    for (j = start; j < end; j++) {
        if (a[j] < tag) {
            ++i;
            tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }

    a[end] = a[i+1];
    a[i+1] = tag;
    tag = a[end];

    return (i+1);
}

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

注：平均时间复杂度为：O(nlgn)，不稳定。