快速排序quicksort的Ｃ实现

    所有的排序算法中，快速排序一定要会写，因为这个最实用。完全可以用在工程实践之中。

    下面的实现没有采用随机化的策略，每次partition，都把最右边的元素作为主元或者衡量的坐标，把比主元小的放在左边，比主元大的放在右边，主元的位置作为interval返回。

    本文提供的算法存在一定的弊端，就是选的主元有可能不能将数组分成均等的两份，极端情况下，比如输入是逆序的情况下，选的主元没有起到任何分而治之的目的，导致算法复杂度变为O(N^2)。

    解决的办法有：

    1 随机化策略，partition不是选择最右边的元素，而是在【left,right】之间随机选择一个元素，作为主元。（选中后，和最右边的元素交换即可。其他不变）。这种方法也有缺点，就是每次选择主元，都需要个随机化得函数，代价稍微有点高。

    2 三者取中的办法，将最左端 最右端，和中间三个元素进行比较，选择三者中间那个元素作为主元。代价较低。能起到不错的效果。当然这种方法在某些情景下也可能退化。

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

void  swap(int  *a ,int *b)
{
    int t = *a;
    *a   = *b;
    *b = t;
}


int  partition(int array[],int l,int r)
{
    int pivot =  array[r];
    int curpos = l;
    int j ;

    for( j = l;j<r;j++)
    {
        if(array[j] < pivot)
        {
            swap(&array[j],&array[curpos]);
            curpos++;
        }
    }

    swap(&array[r],&array[curpos]);
    return curpos;


}

void quicksort(int array[],int l,int r)
{
    int interval;
    if(l < r)
    {
        interval = partition(array,l,r);
        quicksort(array,l,interval-1);
        quicksort(array,interval+1,r);
    }

}


int test_quicksort()
{
    int number = 12;
    int *array = malloc(number*sizeof(int));
    if（array == NULL）
    {
        printf("malloc failed\n");
        return -1;
    }
    int i;

    printf("----------------------------------------before quick sort--------------\n");
    srand(time(NULL));
    for(i = 0;i<number;i++)
    {
        array[i] = rand()%1000;
        printf("\tarray[%d] = %d\n",i,array[i]);
    }

    printf("----------------------------------------after quick sort-----------------\n");

    quicksort(array,0,number-1);
    for(i = 0;i<number;i++)
    {
        printf("\tarray[%d] = %d\n",i,array[i]);
    }
    return 0;
}
int main()
{
    test_quicksort();
}