1.基本思想
快速排序也是基于分支算法的，步骤大致如下：
(1)选择一个基准元素，通常选择第一个元素或者最后一个元素；
(2)通过一趟排序讲待排序的记录分割成独立的两个部分，其中一部分记录的元素值均比基准元素值小，另一部分记录的元素值比基准值大。
(3)此时基准元素在其排好序后的正确位置；
(4)然后分别对这两部分记录用同样的方法继续进行排序，知道整个序列有序。

在上图中只是这排序中的第一趟，第二趟依旧按此方法进行排序，在57分为左右两段进行排序。

---

2.实例

public class Sort {

    private int[] array;

    public Sort(int[] array) {
        this.array = array;
    }
    //排序打印格式
    public void display(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+"\t");
        }
        System.out.println();
    }

    public void quikSort(){
            recursiveQuikSort(0,array.length-1);
    }
    /**
     * @param low  数组最小下标
     * @param high 数组最大下标
     */
    public void recursiveQuikSort(int low, int high){
        if(low>=high){
            return;
        }else {
            //以第一个元素为基准
            int pivot = array[low];
            int partition = partition(low, high, pivot);
            display();
            recursiveQuikSort(low, partition-1);
            recursiveQuikSort(partition+1,high);
        }



    }

    /**
     * @param low 数组中最小下标
     * @param high 数组中最大下标
     * @param pivot 划分的基准元素
     */
    private int partition(int low, int high, int pivot){
        while(low < high){
            while (low < high && array[high]>=pivot){
                //从右端开始扫描，定位到第一个比pivot小的元素
                high--;

            }
            swap(low,high);
            while (low < high && array[low] <= pivot){
                low++;

            }
            swap(low,high);
        }
        return low;

    }
    /**
     * @param low 数组中最小下标
     * @param high 数组中最大下标
     */
    private void swap(int low, int high){
        int temp = array[high];
        array[high] = array[low];
        array[low] = temp;
    }


    //测试方法
    public static void main(String[] args) {
        int[] a = {57,68,59,52,72,28,96,33,24,19};
        Sort sort = new Sort(a);
        System.out.print("未排序时的结果：");
        sort.display();
        sort.quikSort();
    }
}

---

3.算法分析
快速排序与归并排序一样采取看分治算法，它的时间复杂度也是O(Nlog2^N).
对于分支算法一般都说如此，用递归的方法把数据项分为两组，让后调用自身来分别处理每一组数据，算法实际上是以2未底，运行时间与N*log2N成正比。
对于快速排序来说，最理想的状态是随机分布的数据，即我们任意选定的枢纽主语中间位置，有一半元素小于它，有一般元素大于它。当数据是由小到大排列或者由大到小排列是，快速排序的效率最低。假如选中的元素为数组的中值，自然是最好的选择，但是却要遍历整个数组来确定中值，这个过程可能比排列花费的时间还要长。折衷的方法的找到数组中的第一个、最后一个以及处于中间位置的元素，选出三者中的中值作为枢纽，既避免了枢纽是最值的情况，也不会像在全部元素中寻找中值那样费时间。这种方法被称为“三项数据取中”。