快速排序算法及复杂度分析、进一步优化

对一个数组a[]={5,4,6,3,9,1}如何进行快速排序？
快速排序算法的基本思想是设定一个基准值，一般取数组中的第一个值，然后将所有比它小的值都放到它前边，将所有比它大的值都放到它后边，这个过程称为一次快速排序。
从右边下标h开始找比基准值小的值，直到找到后将下标h的值赋给基准值坐标l，然后从左边下标l开始找比基准值大的值，直到找到后将下标i处的值赋给下标h，然后继续从后边找……直到l==h，将基准值覆盖这个中间位置。
通过一趟排序后将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最后达到整个数组都变为有序序列。采用的是二分法分而治之的思想。
java实现代码如下：

public static void quickSort(int[] a,int low,int high) {
        if( low >= high)
            return ;
        int l=low;
        int h=high;
        int p=a[l];
        while(l<h) {
            while(l<h && a[h]>=p)
                h--;
            a[l]=a[h];
            while(l<h && a[l]<=p)
                l++;
            a[h]=a[l];  
        }
        a[l]=p;
        quickSort(a, low, l-1);
        quickSort(a, l+1, high);
    }

稳定性：不稳定，相等的值可能会交换位置。
最差情况下时间复杂度：
待排序的为逆序，每次划分后只得到一个比上一次划分少一个记录的子序列，另一个为空。需要n-1次递归，第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此：

最差情况

最好情况下时间复杂度：
每次划分都很均匀，如果排序n个值，其递归树的深度为[log2n]+1（以2为底）,仅需递归log2n

最好情况

平均时间复杂度：
一般情况下，设枢轴的关键字在第k个位置（1<=k<=n）,那么

平均情况

详细推导过程见《算法导论》7.4节。

eclipse调试（逐步调试F5）

那快排如何优化呢？
思路一：
随机产生一个low和high之间的数并和第一个值进行交换作为基准值

int r = (int)(Math.random()*(high-low+1))+low;
swap(a, low, r);

思路二：
三数取中选取枢轴

思路三：
当排序序列长度分割到一定大小后，使用插入排序