快速排序介绍

    快速排序像归并排序一样，快速排序也是一种分治的递归算法。将数组S排序的基本算法由下列简单的四步组成：

1.     如果S中元素个数是0或1，则返回。
2.     取S中任一元素做为枢纽元。
3.     然后将比枢轴元大的数组元素放在枢轴元的右边，比枢轴元小的数组元素都放在枢轴元素的左边。
4.     再分别对枢轴元左边的序列和枢轴元右边的序列进行快速排序。

  选取枢纽元

    现在翻看网上资料，最多的就是把序列的第一个元素用作枢纽元。如果输入是随机的，那么这时可以接受的，而如果输入是预排序或者是反序的，那么这样的枢纽元就产生一个劣质的分割，因为所有的元素不是被划入S1就是被划入S2.更糟糕的是，这种情况毫无例外的发生在所有的递归调用中。因此，使用第一个元素做为枢纽元是绝对可怕的坏主意。

    一种安全的方针是随机选取枢纽元。一般来说这种策略非常安全，除非随机数发生器有问题，因为随机的枢纽元不可能总在接连不断的产生劣质的分割。

    另外还有一种就是三数中值分割法。枢纽元的最好的选择就是数组的中值。不幸的是，这很难算出并且会明显减慢快速排序的速度。因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。

 算法实现

    在本文中提供了两种快速排序的实现，分别是把序列的第一个元素用作枢纽元的实现和采用三数中值分割法作为枢纽元的代码实现。

    首先我们来看第一种，假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。那么此时数字6作为枢纽元。算法描述如下图所示

    代码如下

public static void main(String [] args){        int[] a={6,1,2,7,9,3,4,5,10,8};        quicksort( a,0,a.length-1);        for(int i=0;i
    
     =temp&&i
    

    接下来我们再来看看利用三数中值法来选取枢纽元的算法实现。采用三数取中法时，会有一个问题，就是当数组不断的递归划分变小之后，枢轴左边的元素个数不足3，这样三数取中法就失去了应有的意义。此外，正如前面提到，对于小数组而言，插入排序反而比快速排序的效率更高。正是基于以上两个原因，我们可以将快速排序与插入排序结合。当递归划分的数组变小之后，达到某个值（CUTOFF）时，采用插入排序。

private static final int CUTOFF = 10;        static int[] a = {6,1,2,7,9,3,4,5,10,8,24,30,25,39,16,14};        public static void main(String[] args){            quickSort(a, 0, a.length - 1);            for(int i=0;i
    
     pivot){}                    if(i < j)                        swapReference(arr, i, j);                    else                        break;                }                swapReference(arr, i, right - 1);//restore pivot                quickSort(arr, left, i - 1);                quickSort(arr, i + 1, right);            }else                //Do an insertion sort on the subarray                insertSort(arr, left, right);        }    private static void insertSort(int[] a, int left ,int right) {        for (int p = left + 1; p <= right; p++) {            int tmp = a[p];//保存当前位置p的元素，其中[0,p-1]已经有序            int j;            for (j = p; j > 0 && tmp
    

    快速排序的时间复杂度

    平均情况下，时间复杂度为O(NlogN)，最坏情况下为O(N^2)