排序>快速排序是一种最坏情况时间复杂度为 o(n^2)的算法。虽然最坏情况时间复杂度很差，但是排序>快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好：它的期望时间排序复杂度是o(nlgn)

描述

与归并排序一样，排序>快速排序算法也使用了分治思想，下面是排序>快速排序的三个分治过程：

• 分解：数组分区，此处我们取末尾元素作为划分标准，划分逻辑见下图：
  

• 解决：通过递归调用排序>快速排序，对左、右数组进行排序。

• 合并：因为子数组都是原址排序的，所以不需要合并。

实现

数组分区实现：以最后一个元素为样本元素，进行分区。将数组划分为左、中（样本元素存放区域）、右三组。左侧区域小于中，右侧区域大于中

    /**
     * 数组分区算法
     * 以最后一个元素为样本元素，进行分区
     * 将数组划分为左、中（样本元素存放区域）、右三组。左侧区域小于中，右侧区域大于中
     *
     * @param array 待排序数组
     * @param start 数组开始位置
     * @param end   数组结束位置
     * @return 样本元素位置
     */
    private static int partition(int[] array, int start, int end) {
        int sample = array[end];
        //默认左侧区域为空
        int leftEnd = start - 1;
        int temp;

        for (int j = start; j < end; j++) {
            //如果当前位置元素值小于样本值
            if (array[j] <= sample) {
                //将当前元素移动到左侧区域，即左侧区域空间增加1
                leftEnd++;
                temp = array[leftEnd];
                array[leftEnd] = array[j];
                array[j] = temp;
            }
        }
        //将样本元素移动到中间区域，也就是与左侧区域紧挨着
        //leftEnd + 1 就是样本元素所在位置
        //如此形成左、中、右的区间排布
        temp = array[leftEnd + 1];
        array[leftEnd + 1] = array[end];
        array[end] = temp;

        //输出分区后的数组
        System.out.println(Arrays.toString(array));
        return leftEnd + 1;
    }

排序实现：和其他的递归调用没太大区别，只需注意每次排序子数组时需要剔除掉样本元素就好。

   /**
     * 排序>快速排序
     * @param array 排序数组
     * @param start 数组起始位置
     * @param end 数组结束位置
     */
    private static void quickSort(int[] array, int start, int end) {
        if (start < end){
            //对数组进行分区，记录分区后的样本元素位置点位置
            int mid = partition(array,start,end);
            //对样本元素左侧区域进行递归排序
            quickSort(array,start,mid-1);
            //对样本元素右侧区域进行递归排序
            quickSort(array,mid+1,end);
        }
    }

此篇文章比预计晚了四天，忙里偷"闲"的生产出来，质量一般、贵在坚持！各位加油，下一篇《线性时间排序算法》