待补充：非递归版本。

快速排序和前面的中值排序非常类似。

分为partition和sort主体两个部分。

1.partition
和前面求第k大的数用到的思路非常类似。
(0)确定一个pivotIndex
(1)交换a[right]和a[pivotIndex]
(2)i=store=left,i从left到right-1，注意要包含right-1！！（不用包含right，因为里面是pivot）
(3)在(2)过程中，如果a[i] (4)完成上述步骤后，交换a[store]和a[right]
(5)返回store下标

2.qsort
(0)仅当left (1)根据partition确定下标pivot
(2)qsort(left,pivot-1)
(3)qsort(pivot+1,right)

该算法证明非常复杂，时间复杂度平均O(nlogn)，最差O(n^2)

排序题：
排序

关于快速排序的优化：

(1)随机选择中枢值。
(2)采用k中值：在[left, right]之间随机选择k个中值，然后取k的中值作为中枢值，一般k=3。
(3)平衡切分：如果很多值等于中枢值，会导致子问题不平衡，可以轮换的将等于中枢值的换位一次到左、右两个子数组中。
(4)优化递归次序，如果堆积的递归栈过大，不利于系统处理，可以优先处理小数组，使得栈尽可能的浅。
(5)当数组过小时，插入排序将远好于快速排序，因此，一般当规模小时将切换到插入排序。
三中值 + 小规模插入排序可以使得快速排序的性能提升20% ~ 25%。
内观排序(IntroSort)：1997年由Musser提出，它将检测内部递归深度，如果超过log(n)，将切换到堆排序。SGI的STL就使用了内观排序作为默认的排序算法。

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

typedef long TYPE;

void swap(TYPE* a, TYPE* b)
{
        TYPE tmp = *a;
        *a = *b;
        *b = tmp;
}

int partition(TYPE* array, int left, int right)
{
        int pivotIndex = rand()%(right-left) + left;
        TYPE pivot = array[pivotIndex];
        int store, i;
        //1. Swap array[pivot] and array[right]
        swap(&array[right], &array[pivotIndex]);

        //2. Scan from left to right, swap i,store, where a[i]<pivot
        store = i = left;
        for(;i<right;i++)
        {
                if(array[i] < pivot)
                {
                        swap(&array[store], &array[i]);
                        store++;
                }
        }

        //3. Swap right and store
        swap(&array[right], &array[store]);

        return store;
}

void myqsort(TYPE* arr, int left, int right)
{
        if(left<right)
        {
                int pi = partition(arr, left, right);
                myqsort(arr,left, pi-1);
                myqsort(arr,pi+1,right);
        }
}

int main()
{
        TYPE array[16] = {15,9,8,1,4,11,7,12,13,6,5,3,16,2,10,14};
        int i;
        int len = sizeof(array)/sizeof(TYPE);
        //partition(array, 0, len-1);
        srand(time(NULL));
        myqsort(array, 0, len-1);

        //print
        for(i=0;i<len;i++)
        {
                printf("%ld ",array[i]) ;
        }
        printf("\n");

}