以前写的快速排序，基本上按下面伪代码这个套路写出来就完了，但其实对于快排，可以通过很多方面来进行改进以达到更好的效率。

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

先回顾一下上面快排的模拟图
分析：

• 首先，清楚快排原理的同志都知道，快排特别热衷于凌乱的数据，最好情况下时间复杂度能达到O(nlogn)，空间复杂度为O(logn)；但是对于基本有序或者倒序的数据则无能为力，时间复杂度直接降到O(n^2），空间复杂度为O( n ) 。对于这种情况，取一个合理的基准值就很重要了。
  一种较为稳妥的方法是随机选取数组中的某个位置，而不是总是顽固地选择最右端的元素，这样确实可以避免排序的退化。
  再回想我们为什么要取随机值？就是为了避免输入数据有序造成的异常，如果一种方法能够在这种情况下利用这种原有的有序性岂不是更好吗？三值取中法就是这样的方法，它的选取方法是先从数组的开头、结尾和中间选取3个元素，再取这3个元素的中间值作为划分的基准。首先，三值取中法本身带有一定的随机性，所以能够很好的处理随机数据；其次，它使得最坏情况几乎不可能发生，如果数组原本就具有有序性，那么按照原始的划分方法，取到的3个元素中必然有2个将被划分到大于（或小于）v的值所在的数组中，而三值取中法则扭转了这种不利；最后，与随机化方法相比，三值取中法省去了生成随机数的开销。
• 其次，在快速排序算法的递归实现中，存在一种不太好的现象：随着递归层层深入，大量数据被分割成了小数组；快排对于大数组的划分可以迅速地将元素移动到它正确位置的附近，比如说对1024进行一次均等划分，那么某个元素可能会移动数百个单位位置，若进行4次均等划分，元素在正确位置上的概率就从1/1024骤升到1/64，考虑到64与1024的绝对数值，这是相当高的效率；然而对于小数组，快速排序的效率就不那么理想了，对于16个元素的数组，快速排序也要划分4次才能把它移动到正确的位置上，相对于之前几百个位置的移动，小数组排序一次只能移动几个单位的位置。
  换句话说，快速排序对少量数据的划分远不如它对大量数据的划分这么划算，当排序进入到小数组阶段后，它将多次因为这些小数组而频繁调用自身，但获得的收益并不大，我姑且把这种现象叫做小数组的边际效益。采取分治递归策略的排序算法（如归并排序）都存在同样的问题，所以这类排序都可以在这方面优化。对大量数据排序时，我们应该在前期利用快速排序的特点，让这些数据迅速移动到正确位置附近，然后在后期消除小数组的边际效应。
  消除边际效应的一个方法就是设定一个M值，当数组元素个数小于M时，视为小数组，此时快速排序就直接返回，最后把数组处理得差不多时，再用其它排序方法对数组进行最终排序。那么M值应该取多少？又应该选择何种排序算法进行最终排序？
  首先回答第二个问题，因为它的答案是显而易见的。对接近有序的数据排序，没有什么算法比插入排序更合适了，插入排序的执行开销与所有元素偏离自己正确位置的距离成正比。

最后看一下结合上面两种改进方法写出来的快排：

package sort;

public class QuickSortDemo2 {
    private static void print(long[] a) {
        System.out.print("a : ");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    private static void quickSort(long[] a, int left, int right) {
//      if(right<=left){
//          return;
//      }
        //当数组长度比较短并且基本有序时，使用插入排序会有比较好的效率提升
        if (right - left + 1 <= 10) {
            insertSort(a, left, right);
        } else {
            //取left和right的中间值，有两个好处：1、防止对于基本有序的数组进行多余无效的交换；2、能够很巧妙的为数组越界作参考标准
            long median = getMedian(a, left, right);
            int partition = partitionInt(a, left, right, median);
            quickSort(a, left, partition-1);
            quickSort(a, partition+1, right);
        }
    }

    private static int partitionInt(long[] a, int left, int right, long median) {
        int leftPtr = left;
        int rightPtr = right - 1;
        while (true) {
            while (a[++leftPtr] < median)   //因为median取的是left、right和center的中间值，所以仅通过一句判断很巧妙的实现了数组越界的判断
                ;
            while (a[--rightPtr] > median)  //同上
                ;
            if(leftPtr >= rightPtr){
                break;
            }
            swap(a,leftPtr,rightPtr);
        }
        swap(a, leftPtr, right-1);
        return leftPtr;
    }

    private static long getMedian(long[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[left] > a[center]) {
            swap(a, left, center);
        }
        if (a[left] > a[right]) {
            swap(a, left, right);
        }
        if (a[center] > a[right]) {
            swap(a, center, right);
        }
        swap(a, center, right - 1); //将中值放到right-1位置，后面的比较替换只针对left+1~right-2
        return a[right - 1];
    }

    private static void insertSort(long[] a, int left, int right) {
        int in, out;
        for (out = left + 1; out <= right; out++) {
            in = out;
            long temp = a[out];
            while (in > left && a[in - 1] > temp) {
                a[in] = a[in - 1];
                --in;
            }
            a[in] = temp;
        }

    }

    private static void swap(long[] a, int i, int j) {
        long temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        long[] a = new long[10000];
        for (int i = 0; i < a.length; i++) {
            a[i] = (long) (Math.random() * 99);
        }
        print(a);
        long startTime = System.currentTimeMillis();
        quickSort(a, 0, a.length - 1);
        long endTime = System.currentTimeMillis();
        System.out.println("use: " + (endTime - startTime) + "ms");
        print(a);

    }

}

github:
https://github.com/aweneves/Algorithm1/blob/master/src/sort/QuickSortDemo2.java

快速排序平均复杂度为O(nlgn)，

最坏情况为O(n^2），即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，所以快速排序时间复杂度下界为O(nlogn)，最坏情况下为O(n^2)

1.如果在排序时选取最后一个元素为基准，则可以通过以下方法来避免划分的不平衡。

int Patition(int *pnArr, int nLeft, int nRight)
{
    int nKey = nRight;
    int i = nLeft - 1;
    bool bExchange = false;

    for (int j = nLeft; j < nRight; j++)
    {
        if (pnArr[j] < pnArr[nKey])
        {
            i++;
            Swap(&pnArr[i], &pnArr[j]);
            bExchange = true;
        }
    }
    Swap(&pnArr[i+1],&pnArr[nRight]);
    if (bExchange)
    {
        return i+1;
    }
    else
    {
        return (nLeft + nRight) / 2;
    }
}

2.但是上面的改进只适合选取最后一个元素，如果对于一个有序序列，选取中间元素为基准，则把中间的元素交换到最后还是会又一次交换的过程，不能改善。（改善方法可以同下面的随机选取元素方法一样设置阈值）.

3.快速排序的最坏情况基于每次划分对基准元素的选择。基本的快速排序选取第一个元素作为基准元素。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为基准元素。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。

4.设置阈值。快速排序的实现需要消耗递归栈的空间，而大多数情况下都会通过使用系统递归栈来完成递归求解。在元素数量较大时，对系统栈的频繁存取会影响到排序的效率。

一种常见的办法是设置一个阈值，在每次递归求解中，如果元素总数不足这个阈值，则放弃快速排序，调用一个简单的排序过程完成该子序列的排序。这样的方法减少了对系统递归栈的频繁存取，节省了时间的消费。

一般的经验表明，阈值取一个较小的值，排序算法采用选择、插入等紧凑、简洁的排序。一个可以参考的具体方案：阈值T=10，排序算法用选择排序。阈值不要太大，否则省下的存取系统栈的时间，将会被简单排序算法较多的时间花费所抵消。

快速排序基本思路：找到一个标定点，左边的元素小于标定点，右边元素大于标定点，然后再对左右区间递归快速排序。

// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int __partition(T arr[], int l, int r) {

	T v = arr[l];

	int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
	for (int i = l + 1; i <= r; i++)
		if (arr[i] < v) {
			j++;
			swap(arr[j], arr[i]);
		}

	swap(arr[l], arr[j]);

	return j;
}

// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r) {

	if (l >= r)
		return;

	int p = __partition(arr, l, r);
	__quickSort(arr, l, p - 1);
	__quickSort(arr, p + 1, r);
}

template <typename T>
void quickSort(T arr[], int n) {

	__quickSort(arr, 0, n - 1);
}

改进1：如果数组近乎有序，标定点的选择会影响快速排序的性能，如果每次都选择最小值作为标定点，快速排序时间复杂度会退化为，因此需要随机化标定点元素。

template <typename T>
int __partition(T arr[], int l, int r) {
	// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
	swap(arr[l], arr[rand() % (r - l + 1) + l]);
	T v = arr[l];

	int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
	for (int i = l + 1; i <= r; i++)
		if (arr[i] < v) {
			j++;
			swap(arr[j], arr[i]);
		}

	swap(arr[l], arr[j]);

	return j;
}

改进2：如果数组有大量相同元素，上面的做法会将相同元素分到大于v的区间，会造成两个子区间元素不平衡，所以需要将相等元素平衡地分入两个区间。

template <typename T>
int _partition2(T arr[], int l, int r) {

	// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
	swap(arr[l], arr[rand() % (r - l + 1) + l]);
	T v = arr[l];
	
	//[l+1,i) <=v, (j,r]>=v
	int i = l + 1, j = r;
	while (i <j)
	{
		while (i <=r&&arr[i] < v)
			i++;
		while (j >l && arr[j-1] > v)
			j--;
		swap(arr[i], arr[j]);
		i++; j--;
	}
	swap(arr[i], arr[l]);
	return i;
}

对应地，还有三路快速排序算法。