一键排序,快速排序以中间元素为轴值

简介

快速排序是冒泡排序的改进，不稳定。 粗暴的黑裤子在1962年提出的区分交换排序，采用分割统治战略，一般与递归组合使用，减少排序中的比较次数。 其最佳情况为o(nlogn )，最差情况为o ) n^2)，平均时间复杂度为o ) nlogn )。基本思想

选择基准数，将排序的数据在一次排序中分割为独立的两个部分。 一部分的所有数据都小于另一部分的所有数据。 然后，可以使用这种方法分别快速排序这两个部分数据，并递归执行整个排序过程，以确保所有数据都有序。步骤

(1)从数列中选择一个基准值。

(2)任何小于参考值的都位于参考前面，任何大于参考值的都位于参考后面(可以在任何一侧布置相同数量)，并且该参考位于数列的中间位置。

)3)递归排序参考值前的子数列和参考值后的子数列。

注：所有基本要素/左光标/右光标都对应于单次排序。 也就是说，在整个排序过程的多次排序中，每个排序中检索的基本元素/左光标/右光标通常不同。 对于基本元素的选择，原则上是可选的，但通常选择数组的第一个元素作为基本元素(假设数组是随机分布的)。

排序过程的图像如下

选择上述数组的第一个元素6作为基准元素。 左光标是I哨兵，右光标是j哨兵，请遵循以下规则：

另一方面，向右扫描左光标，跨越所有小于基准元素的数组元素，遇到基准元素以上的数组元素并停止在该位置。 二、右光标向左扫描，跨越所有大于参考元素的数组元素，遇到小于参考元素的数组元素，并停止在该位置。

第一步：哨兵j先开始出动。 这里设定的基准数是最左边的数，所以哨兵j必须先开始出动，逐步向左移动，直到哨兵j发现不足6的要素并停止。 然后哨兵I向右移动并停止，直到找到大于6的元素。 最后哨兵I停在数字7之前，哨兵j停在数字5之前。

这个第一次交换结束后，哨兵j继续向左移动，如果发现4小于标准数6，在数字4前面停下来。 哨兵I也继续向右移动，在数字9前停下后，哨兵I和哨兵j再次进行交换。

第二次更换结束后，哨兵j继续向左移动，在数字3前停下； 哨兵I继续向右移动，但发现他遇到了哨兵j。 那么，此时说明探针结束，交换数字3和基准数字6。

该第一次探针实际结束时，以基准点6为界线，左侧数组元素均小于6，右侧数组元素均大于6。 左边的数组是3、1、2、5、4。 右边的排列是9、7、10、8。 此时，以数字3为基准要素，对左边的排列重复上述探针，探针完成后的排列为2、1、3、5、4。 对于右边的排列，也以数字9为基准要素，重复上面的探针，一步一步的分隔的最后排序完全结束。

快速排序中每一个倒圆角的处理实际上是通过将此倒圆角的基准计数返回位来结束排序，直到所有计数都返回位。

下图显示了整个算法的处理过程。

常规快速排序法

用公共类快速排序(/数组array交换附加在I和j位置的元素，以获得私有的array，int i，int j ) inttemp=Array )； array[i]=array[j]； array[j]=temp； }私有语音查询(int [ ] array，int left，int right ) if ) right=left ) { return； } else { int partition=partition it (array，left，right )； rec quick sort (阵列、左、分区-1)； //上次排序(分割)时，递归recquicksort ) array，partition 1，right )基准元素左侧的子数组； //排序(分割)上一个倒圆角时，递归基准元素右侧的子数组) )专用阵列(int [ ] array，int left，int right ) /为什么j有1，I

-j和++i开始的。        // 而基准元素选的array[left]即第一个元素，所以左游标从第二个元素开始比较。        int i = left;        int j = right + 1;        int pivot = array[left];// pivot为选取的基准元素        while (true) {            while (i < right && array[++i] < pivot) {            }            while (j > 0 && array[--j] > pivot) {            }            if (i >= j) { // 左右游标相遇时停止                break;            } else {                swap(array, i, j); // 左右游标未相遇时交换各自所指元素            }        }        swap(array, left, j); // 基准元素和游标相遇时所指元素交换为最后一次交换        return j; // 一趟排序完成，返回基准元素位置（注意这里基准元素已经交换位置了）    }    public static void sort(int[] array) {        recQuickSort(array, 0, array.length - 1);    }    public static void main(String[] args) {        //int[] array = {7,3,5,2,9,8,6,1,4,7};        int[] array = {9, 9, 8, 7, 6, 5, 4, 3, 2, 1};        sort(array);        for (int i : array) {            System.out.print(i + " ");        }        // 打印结果为：1 2 3 4 5 6 7 7 8 9    }}

三数取中法
避免分组一边倒的情况，比如逆序数组，选取第一个元素作为基准点，即最大元素是基准点，那么第一次循环，左游标要执行到最右边，而右游标执行一次，然后两者进行交换。这也会划分成很多的子数组。

在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。

public class QuickSort {    public static void main(String[] args) {        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};        quickSort(arr, 0, arr.length - 1);        System.out.println("排序结果：" + Arrays.toString(arr));    }     /**     * @param arr     * @param left  左指针     * @param right 右指针     */    public static void quickSort(int[] arr, int left, int right) {        if (left < right) {            // 获取枢纽值，并将其放在当前待处理序列末尾            dealPivot(arr, left, right);            // 枢纽值被放在序列末尾            int pivot = right - 1;            int i = left; // 左指针            int j = right - 1; // 右指针            while (true) {                while (arr[++i] < arr[pivot]) {                }                while (j > left && arr[--j] > arr[pivot]) {                }                if (i < j) {                    swap(arr, i, j);                } else {                    break;                }            }            if (i < right) {                swap(arr, i, right - 1);            }            quickSort(arr, left, i - 1);            quickSort(arr, i + 1, right);        }    }    /**     * 处理枢纽值     *     * @param arr     * @param left     * @param right     */    public static void dealPivot(int[] arr, int left, int right) {        int mid = (left + right) / 2;        if (arr[left] > arr[mid]) {            swap(arr, left, mid);        }        if (arr[left] > arr[right]) {            swap(arr, left, right);        }        if (arr[right] < arr[mid]) {            swap(arr, right, mid);        }        swap(arr, right - 1, mid);    }    /**     * 交换元素通用处理     *     * @param arr     * @param a     * @param b     */    private static void swap(int[] arr, int a, int b) {        int temp = arr[a];        arr[a] = arr[b];        arr[b] = temp;    }}

参考：https://www.cnblogs.com/ysocean/p/8032632.html
           https://www.cnblogs.com/chengxiao/p/6262208.html