快速排序是目前最流行的算法，在大多数情况下，快速排序都是最快的，执行时间为O(N*logN)。

快速排序本质上是通过把一个数组划分为两个子数组，然后在递归调用自身对每一个字数组进行快速排序。

即数组划分为字数组A，B，在对A进行划分为A₁，A₂，对A₁划分为A₁₁，A₁₂。。B也是如此执行，这就涉及到递归调用自身的操作。

1.取右值作为枢纽的情形

/**     * 快速排序     *      * @param left     * @param right     */    public static void quickSort(int left, int right, int[] arr)    {        // 检查数据是否只包含一个数据项，如果是，则为有序数组，无需排序        if (right - left <= 0)        {            return;        }        else        {            // 设置参照值为最右边的数据值            int pivot = arr[right];            int partition = partitionIt(left, right, pivot, arr);            // 调用自身对左边排序            quickSort(left, partition - 1, arr);            // 调用自身对右边排序            quickSort(partition + 1, right, arr);        }    }

（1）设置枢纽：int pivot = arr[right]; 为了方便，这里选择做右边的作为枢纽。当一轮排序下来后，枢纽的位置在最终排序的位置就确定了，

这是因为，最终排序后，左边的数值总比枢纽的小，右边的数值总比枢纽的大。

 

（2）这里看到主要有3个方法

      1）partitionIt(left, right, pivot, arr); 数据结构学习笔记3.1节所描述的划分方法，主要是取出枢纽值。

      2）quickSort(left, partition - 1, arr); 递归调用自身排序左边的数组。

      3）quickSort(partition + 1, right, arr); 递归调用自身排序右边的数组。

递归方法可以这样理解：先把左边排好，再排列右边。

 

完整代码：

/**     * 快速排序     *      * @param left     * @param right     */    public static void quickSort(int left, int right, int[] arr)    {        // 检查数据是否只包含一个数据项，如果是，则为有序数组，无需排序        if (right - left <= 0)        {            return;        }        else        {            // 设置参照值为最右边的数据值            int pivot = arr[right];            int partition = partitionIt(left, right, pivot, arr);            // 调用自身对左边排序            quickSort(left, partition - 1, arr);            // 调用自身对右边排序            quickSort(partition + 1, right, arr);        }    }    /**     * 划分数据     *      * @param left 左边数据     * @param right 右边数据     * @param pivot 参照值     * @return     */    public static int partitionIt(int left, int right, int pivot, int[] arr)    {        // 左边指针        // 左边数据-1，为了后面执行++leftPrt操作时，数据能正确+1        int leftPrt = left - 1;        // 右边指针        // 右边数据-1，为了后面执行--rightPrt操作时，数据能正确-1        int rightPrt = right + 1;        while (true)        {            // 左边数据比参照值的小，不做后续操作，循环            while (leftPrt < arr.length && arr[++leftPrt] < pivot)            {                int a = 0;            }            // 右边数据比参照值的大，不做后续操作，循环            while (rightPrt > 0 && arr[--rightPrt] >= pivot)            {                int b = 0;            }            if (leftPrt >= rightPrt)            {                break;            }            else            {                // 交左右两边的数据                swap(leftPrt, rightPrt, arr);            }        }        // 重置参照值        swap(leftPrt, right, arr);        return leftPrt;    }    /**     * 数据交换     *      * @param index1 入参1     * @param index2 入参2     * @param arr 比较数组     */    public static void swap(int index1, int index2, int[] arr)    {        int temp = arr[index1];        arr[index1] = arr[index2];        arr[index2] = temp;    }

 

2.取中值作为枢纽的情形

对于快速排序算法来说，最优的情况是有两个大小相等的子数组。

以右值作为枢纽，有一种情形：当数组以逆序排序列时，这时候产生N-1的子数组和一个只包含枢纽的子数组。此时执行的效率为O（N²）。

 

解决方法：

三数据项取中：思路是取数组N的第1个，第N/2个，第N个数据，即arr[0]，arr[N/2],，arr[N-1]项数据，此时操作是：

（1）比较三项数据，取中间值作为枢纽。

（2）对这三个数据排序。

 

完整代码：

/**     * 快速排序     * @param left 数组第一个位置，即0     * @param right 数组最后一个数据，即arr.length - 1     * @param arr 数组     */    public static void recQuickSort(int left, int right, int[] arr)    {        // 数组长度        int size = right - left + 1;                // 如果数据项只有3项        if (size <= 3)        {            // 处理数组个数小于3个的数组            manualSort(left, right, arr);        }        else        {            int median = midanOf3(left, right, arr);            int partition = partitionIt(left, right, median, arr);            recQuickSort(left, partition - 1, arr);            recQuickSort(partition, right, arr);        }    }        /**     * 处理整个数组小于或等于3个数据项的数组     * @param left 数组左边位置     * @param right 数组右边位置     * @param arr 数组     */    public static void manualSort(int left, int right, int[] arr)    {        int size = right - left + 1;        if (size <= 1)        {            return;        }        if (size == 2)        {            // 如果左边数据大于右边数据，则交换位置            if (arr[left] > arr[right])            {                swap(left, right, arr);            }            return;        }        // 数组长度为3        else        {            // 交换位置，交换方法：先用第一个数据项一次于后面两个数据项比较，            // 取出最小的数据放在最左边，然后在比较后面两个数据            if (arr[left] > arr[right - 1])            {                swap(left, right, arr);            }            if (arr[left] > arr[right])            {                swap(left, right, arr);            }            if(arr[right- 1] > arr[right])                {                swap(right - 1, right, arr);            }        }    }        /**     * 取出3个数据项，排序，并将中枢取出放在数组right - 1位置     * @param left 数组左边项     * @param right数组右边项     * @param arr 数组     */    public static int midanOf3(int left, int right, int[] arr)    {        // 取出中间项        int center = (right + left) / 2;                // 通过交换排序，思路与manualSort中使用的方法一致        if (arr[left] > arr[center])        {            swap(left, center, arr);        }        if (arr[left] > arr[right])        {            swap(left, right, arr);        }        if (arr[center] > arr[right])        {            swap(center, right, arr);        }                // 交换中枢与right - 1的位置        // 由于arr[right]的位置已经排好，即数值比中枢的要打，已经划分        // 所以取倒数第二个数据right - 1的数据，将center中枢的位置与之交换，目的减少右边排序次数        swap(center, right - 1, arr);                // 此时位置值为中枢值        return arr[right - 1];     }        /**     * 划分数组     * @param left 数组左边位置     * @param right 数组右边位置     * @param median 中枢值     * @param arr 数组     */    public static int partitionIt(int left, int right, int median ,int[] arr)    {        int leftPrt = left;        int rightPrt = right - 1;                 while(true)        {            while (arr[++leftPrt] < median);            while (arr[--rightPrt] > median);                        if (leftPrt >= rightPrt)            {                break;            }            else            {                // 左边大于中枢值，右边小于中枢值，交换                swap(leftPrt, rightPrt, arr);            }        }                // 重置中枢值，此时左边leftPrt指针的位置指向右边数组的第一个数据项，比中枢值大        // 将左边标记的位置与right - 1交换，此时，中枢值所在的位置已经固定，不会在变        swap(leftPrt, right - 1, arr);        return leftPrt;    }        /**     * 数据交换     *      * @param index1 入参1     * @param index2 入参2     * @param arr 比较数组     */    public static void swap(int index1, int index2, int[] arr)    {        int temp = arr[index1];        arr[index1] = arr[index2];        arr[index2] = temp;    }

1. manualSort(left, right, arr);这个方法是处理当数组划分后，数组个数小于等于3个时，此时直接交换排序排序即可。

2.midanOf3(left, right, arr);这个方法是去数组（包含子数组）的中间值，也是通过比较交换的方法排序。

 

取中值排序的特点：对于随机排序，执行效果与取右值相差不大，但是在逆序中，排序消耗时间有明显的提高。