疾速排序（Quick Sort）

1.什么是疾速排序

疾速排序是由东尼·霍尔所倒退的一种排序算法。在均匀情况下，排序 n 个我的项目要 (nlogn) 次比拟。在最坏情况下则须要 (n2) 次比拟，但这种情况并不常见。事实上，疾速排序通常显著比其余 (nlogn) 算法更快，因为它的外部循环（inner loop）能够在大部分的架构上很有效率地被实现进去。

疾速排序应用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

2.算法步骤

从数列中挑出一个元素，称为 "基准"（pivot）;

从新排序数列，所有元素比基准值小的摆放在基准后面，所有元素比基准值大的摆在基准的前面（雷同的数能够到任一边）。在这个分区退出之后，该基准就处于数列的两头地位。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

3.动图演示

4.代码实现

public static void main(String[] args) {        //初始化数组        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};        quickSort(arr,0,arr.length -1);        System.out.println(Arrays.toString(arr));    }    private static void quickSort(int[] arr,int l, int r){        if(l >= r){            return;        }        int left = l;         int right = r;         int pivot = arr[left];        while(left < right){                        while(left < right && arr[right] >= pivot){                right --;            }            if(left < right){                arr[left] = arr[right];            }            while (left < right && arr[left] <= pivot){                left ++;            }            if (left < right){                arr[right] = arr[left];            }else{                arr[left] = pivot;            }        }        quickSort(arr,l,right -1);        quickSort(arr,right + 1,r);    }

正文版本：

 public static void main(String[] args) {        //初始化数组        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};        quickSort(arr, 0, arr.length - 1);        System.out.println(Arrays.toString(arr));    }    private static void quickSort(int[] arr, int l, int r) {        if (l >= r) {            return;        }        int left = l; // 0        int right = r; // 9        int pivot = arr[left]; // 5        while (left < right) {            /**             *  第一次循环：0 < 9 && arr[right] (9)   9 >= 5  条件满足  9 --  = 8             *  第二次循环：0 < 8 && arr[right] (8)   10 >= 5 条件满足  8 --  = 7             *  第三次循环：0 < 7 && arr[right] (7)   6 >= 5  条件满足  7 --  = 6             *  第四次循环：0 < 6 && arr[right] (6)   8 >= 5  条件满足  6 --  = 5             *  第五次循环：0 < 5 && arr[right] (5)   7 >= 5  条件满足  5 --  = 4             *  第六次循环：0 < 4 && arr[right] (4)   2 >= 5  条件不满足  此时 left = 0; right = 4             */            while (left < right && arr[right] >= pivot) {                right--;            }            /**             *  0 < 4             */            if (left < right) {                /**                 *  arr[left] = 5                 *  arr[right] = 2                 *  执行之后，数组变成如下：                 *  {2, 3, 1, 4, 2, 7, 8, 6, 10, 9};                 */                arr[left] = arr[right];            }            /**             *  第一次循环：0 < 4 && arr[left] (2) <= 5 条件满足  0 ++  = 1             *  第二次循环：1 < 4 && arr[left] (3) <= 5 条件满足  1 ++  = 2             *  第三次循环：2 < 4 && arr[left] (1) <= 5 条件满足  2 ++  = 3             *  第四次循环：3 < 4 && arr[left] (4) <= 5 条件满足  3 ++  = 4             *  第四次循环：4 < 4 条件不满足，此时 left = 4; right = 4             */            while (left < right && arr[left] <= pivot) {                left++;            }            /**             *  4 < 4 不满足条件进入else             */            if (left < right) {                arr[right] = arr[left];            } else {                /**                 * arr[left] = 2;                 * pivot = 5;                 * arr[left] = 5;                 * 此时数组变成如下：                 * {2, 3, 1, 4, 5, 7, 8, 6, 10, 9};                 */                arr[left] = pivot;            }        }        /**         * l = 0         * right = 4         * {2, 3, 1, 4};         * quickSort(arr,0,4-1);         * 排序基准左侧的数         */        quickSort(arr, l, right - 1);        /**         * right = 4         * r = 9         * {7, 8, 6, 10, 9};         * quickSort(arr,4 + 1,9);         * 排序基准右侧的数         */        quickSort(arr, right + 1, r);    }

5.输入后果

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]