快速排序

快速排序又是一种分而治之思想在排序算法上的典型应用。快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

时间复杂度

在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

经典快排

代码

public static void quickSort1(int[] arr){
        if (arr == null || arr.length <2){
            return;
        }
        process1(arr,0,arr.length-1);
    }

    public static void process1(int[] arr, int L, int R){
        if (L>=R){
            return;
        }
        int M =partition(arr,L,R);
        process1(arr,L,M-1);
        process1(arr,M,R);

    }

    private static int partition(int[] arr,int L,int R) {
        if (L>R){
            return -1;
        }
        if (L ==R){
            return L;
        }
        int lessEqual = L-1;//小于等于的位置
        int index = L;//当前位置
        while (index<R){
            if (arr[index]<=arr[R]){
                //如果当前位置的数据小于等于 目标数据 ，则把当前位置的数据和 小于等于位置的的下一个位置进行交换
                //同时 小于等于位置往下移动一位
                swap(arr,index,++lessEqual);
            }
            index++; //当前位置往后移动一位
        }
        //最后，小于等于位置和 目标数据进行交换
        swap(arr,++lessEqual,R);
        return lessEqual;

    }

    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
复制代码

其中代码中while 循环部分图解

优化一版的快排

优点：分为三个部分

代码

public static void quickSort2(int[] arr){
        if (arr == null || arr.length<2){
            return;
        }
        process2(arr,0,arr.length-1);
    }

    private static void process2(int[] arr, int L, int R) {
        if (L>=R){
            return;
        }
        //小于等于目标区域
        int[] equalArea = netherLandsFlag(arr,L,R);
        process2(arr,L,equalArea[0]-1);
        process2(arr,equalArea[1]+1,R);

    }

    private static int[] netherLandsFlag(int[] arr, int L, int R) {
        if (L>R){
            return new int[]{-1,-1};
        }
        if (L == R){
            return new int[]{L,R};
        }
        int less = L-1;//小于区域 的右边界
        int more = R;//大于区域的 左边界
        int index = L;//当前位置
        while (index<more){
            if (arr[index] == arr[R]){
                index++;
            }else if (arr[index] < arr[R]){
//                swap(arr,index,less+1);
                //less++
//                index++;
                //优化一下
                swap(arr,index++,++less);
            }else {
                //此时index 不向下移动，因为换过来的数还没有看
                swap(arr,index,--more);
            }
        }
        swap(arr,more,R);//  <[R] =[R] >[R]
        return new int[]{less+1,more};
    }

    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
复制代码

int more = R;//大于区域的 左边界
为什么大于区域的有边界是 R，因为R 位置上的数是对比的目标数，这个位置预留，R-1 是大于R的左边界
一开始 是在【L–R-1】位置上进行对目标数的比较，所以边界为： L-1）L….R-1(R

图解

改进版随机快排

经典快速排序总是指定数组或者某部分的最后一个元素作为基准值，随机快速排序指定数组或者某一部分中的随机值作为基准值。

这样做的好处就是避免快速排序的最坏运行情况是 O(n²)。

图解

代码

 private static void quickSort3(int[] arr){
        if (arr ==null || arr.length<2){
            return;
        }
        process3(arr,0,arr.length-1);
    }

    private static void process3(int[] arr, int L, int R) {
        if (L>=R){
            return;
        }
        //随机选择一个数和目标数进行交换
        swap(arr,L+(int)(Math.random() *(R-L+1)),R);
        int[] equalArea = netherLandsFlag(arr,L,R);
        process3(arr,L,equalArea[0]-1);
        process3(arr,equalArea[1]+1,R);

    }
复制代码

不同就是加入了随机因子。