quick sort--快排--分治

#include <stdio.h>

static unsigned  pcount;
static unsigned qcount;

int partition(int array[], int p, int r)
{
    int key;
    int i,j;
    pcount++;

    key = array[r];
    i = p-1;

    for(j = p; j < r; j++) {
        if(array[j] < key) {
            i++;
            if(array[i] != array[j]) {
                array[i] ^= array[j];
                array[j] ^= array[i];
                array[i] ^= array[j];
            }
        }
    }

    if(array[i+1] != array[j]) {
        array[i+1] ^= array[j];
        array[j] ^= array[i+1];
        array[i+1] ^= array[j];
    }

    return i+1;
}

void quick_sort(int array[], int p, int r)
{
    int q,i;
    qcount++;

    if(p < r) {
        q = partition(array,p,r);
        quick_sort(array,p,q-1);
        quick_sort(array,q+1,r);
    }
}

int main()
{
    int array[5] = {9,8,6,7,5};
    int i;

    for(i=0; i < 5; i++) {
        printf("%2d",array[i]);
    }
    printf("\n");

    quick_sort(array,0,4);

    for(i=0; i < 5; i++) {
        printf("%2d",array[i]);
    }
    printf("\n");
    printf("pcount=%d,qcount=%d\n",pcount,qcount);
}

复杂度：T(N)=2*T(N/2)+cN, T(N)=O(N*lgN)