快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想
    分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序的基本思想

从待排序的数据序列中任取一个数据（如第一个数据）作为分界值，所有比它小的数据元素一律放到左边，所有比它大的数据元素放到右边。这样一趟后，就形成了两个子序列：左序列中的数据都比分界值小，右序列的数据元素都比分界值大。

然后，对左、右两个子序列递归进行上述操作，直到每个子序列只剩一个元素。

从上面的算法分析可以看出，实现快速排序的关键在于第一趟要做的事情：

（1）选出指定的基准(PivotKey)

（2）将所有小于分界值的数据元素放在左边

（3）将所有大于分界值的数据元素放到右边

主要是如何实现2、3两步！

排序效果：

Java实现代码：

package com.liuhao.sort;

import java.util.Arrays;

/**
* 快速排序的Java实现
* @author liuhao
*
*/
public class QuickSort {

    /**
     * @param data
     * @param start
     * @param end
     */
    private static int subSort(DataWrap[] data, int start, int end){

        DataWrap tmp = data[start];
        while(start < end){
            while( start < end && data[end].compareTo(tmp) >= 0){
                end--;
            }
            data[start] = data[end];
           
            while(start < end && data[start].compareTo(tmp) <= 0){
                start++;
            }
            data[end] = data[start];
        }
       
        data[end] = tmp;
       
        System.out.println(Arrays.toString(data));
       
        return start;
    }
   
    /**
     * 递归进行快速排序
     * @param data
     * @param start
     * @param end
     */
    public static void quickSort(DataWrap[] data, int start, int end){
        if(start < end){
            int key = subSort(data, start, end);
            quickSort(data, start, key-1);
            quickSort(data, key+1, end);
        }
    }
   
    public static void main(String[] args) {
        DataWrap[] data = http://www.mamicode.com/{>运行结果：
算法分析
快速排序的时间主要耗费在划分操作上，对长度为k的区间进行划分，共需k-1次关键字的比较。 
（1）最坏时间复杂度 
    最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
    因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值： 
               Cmax = n(n-1)/2=O(n2) 
    如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。
（2） 最好时间复杂度 
    在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数： 
        0(nlgn) 
注意： 
    用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。
    因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。 
（3）基准关键字的选取 
    在当前无序区中选取划分的基准关键字是决定算法性能的关键。 
①"三者取中"的规则 
    "三者取中"规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的Partition算法完全相同。

②取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准 
    选取基准最好的方法是用一个随机函数产生一个取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准，这相当于强迫 R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。具体算法【参见教材】
注意： 
     随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。算法的随机化不仅仅适用于快速排序，也适用于其它需要数据随机分布的算法。
（4）平均时间复杂度 
    尽管快速排序的最坏时间为O(n2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。
（5）空间复杂度 
    快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。
（6）稳定性 
    快速排序是非稳定的，例如[2，2，1]。
排序算法总结之快速排序