快速排序算法

快速排序算法的平均时间复杂度为O(nlogn)，实现代码如下：

#include <stdio.h>
#include <stdlib.h>

int division(int a[], int left, int right)
{
    int i = left, j = right, base = a[left], t;

    while (i < j){
        while (i < j && a[j] >= base) --j;
        while (i < j && a[i] <= base) ++i;

        if (i != j){
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    a[left] = a[i];
    a[i] = base;

    return i;
}

void quick_sort(int a[], int left, int right)
{
    int div;

    if (left < right){// use if statement not while !!!
        div = division(a, left, right);
        quick_sort(a, left, div-1);
        quick_sort(a, div+1, right);
    }
}

int main(void)
{

    int a[100], size = 0, i;

    while (scanf("%d", &a[size]) != EOF){
        ++size;
    }

    printf("size : %d
", size);

    quick_sort(a, 0, size-1);

    for (i = 0; i < size; i++)
    {
        printf("%6d
", a[i]);
    }

    return 0;
}