快速排序及其简单优化

       快速排序是我们大一进入学校就会的东西，但我发现自己到了大学之后学东西非常 生硬，都是被别人灌输的，缺少了自己思考的过程，这几天被左神一语惊醒，我们学习算法应该是一个思考与探索的过程，不是简单的把这道题AC了就完事了，那我们大学之前那么辛苦可不是为了来大学玩的，所以以后要学会思考和学会探索；

       首先今天我们来讲的是快速排序，这里用三种方法来写快排的；

 ①设定一个标志，两个 哨兵分别从两端开始行走的方法，主代码如下：

public static void quickSort(int[] arr,int l,int r){

        if ( l < r ){
            //随机出标志数
            swap1(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int q = partition(arr ,l , r);
            quickSort(arr,l,q-1);
            quickSort(arr,q+1,r);
        }
    }

public static int partition(int[] arr,int l,int r){
        int p = arr[l];//设置标志位置
        int i = l;//左哨兵
        int j = r;//右哨兵
        while (i < j){
            while (arr[j] >= p && i < j){
                j--;
            }
            if (i<j){
                swap1(arr,i,j);
            }
            while (arr[i] <= p && i < j){
                i++;
            }
            if (i<j){
                swap1(arr,i,j);
            }
        }
        return i;
    }

 ②把最右边的设置 为标志位，一个哨兵 从最左侧依次进行比较，把 数组 分为两个区，代码 如下：

public static void quickSort2(int[] arr,int l,int r){

        if ( l < r ){
            //随机产生标志位
            swap1(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int q = partition2(arr,l,r);
            quickSort(arr,l,q-1);
            quickSort(arr,q+1,r);
        }
    }

public static int partition2(int[] arr,int l,int r){
        int i = l-1;
        int j = r;
        while (l < j){
            //每次把最右边的设置为标志位，这样减少了额外空间
            if (arr[l]<=arr[r]){
                i++;
                swap1(arr,i,l);
                l++;
            }else{
                j--;
                swap1(arr,j,l);
            }
        }
        swap1(arr,j,r);
        return i+1;
    }

 ③把数组分为三部分，大于区，小于区和等于区，这样会减少比较的次数，代码如下：

public static void quickSort1(int[] arr,int l,int r){

        if ( l < r ){
            swap1(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] q = partition1(arr,l,r);
            quickSort(arr,l,q[0]-1);
            quickSort(arr,q[0]+1,r);
        }
    }

 //划分数组的优化算法,把一个数组分为三个区，大于区，小于区和等于区
    public static int[] partition1(int[] arr,int l,int  r){
        int i = l-1;
        int j = r;
        while (l < j){
            //每次把最右边的设置为哨兵，这样减少了额外空间
            if (arr[l]<arr[r]){
                swap1(arr,++i,l++);
            }else if (arr[l]>arr[r]){
                swap1(arr,--j,l);
            }else {
                l++;
            }
        }
        swap1(arr,j,r);
        return new int[] {i+1,j};
    }

 完整代码如下：

package study.tao.sort;

import java.util.Arrays;

/**
 * Created by Taoyongpan on 2017/11/13.
 * 快速排序及其优化，我们一般快排的时候会把一个数组 分为两个区
 * 大于等于和小于两个区，现在我们要做的是讲一个数组分为三个区，大于，等于和小于三个区
 * 这样做的好处是每次把相等的数放在中间位置，这样会减少比较次数
 */
public class QuickSort {

    //随机产生一个数组 大小为maxSize，最大值为maxValue的数组
    public static int[] generateRandomArray(int maxSize,int maxValue){
        if (maxSize<=0){
            return null;
        }
        int[] arr = new int[(int)((maxSize+1)*Math.random())];

        for (int i = 0 ; i < arr.length ; i++){
            arr[i] = (int) ((maxValue+1)*Math.random());
        }
        return arr;
    }

    //数组的输出函数
    public static void printArray(int[] arr){
        if (arr==null){
            return;
        }
        for (int j = 0 ; j < arr.length ; j++){
            System.out.print(arr[j]+" ");
        }
        System.out.println();
    }

    //复制函数
    public static int[] copyArray(int[] arr){
        int[] res = new int[arr.length];
        if (arr == null){
            return null;
        }
        for (int i = 0 ; i < arr.length ; i++){
            res[i] = arr[i];
        }
        return res;
    }

    //交换函数
    //位运算进行交换
    public static void swap(int[] arr,int i,int j){
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }
    //需要额外空间的交换函数
    public static void swap1(int[] arr,int i,int j){
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //系统的比较函数
    public static void arraySort(int[] arr){
        Arrays.sort(arr);
    }

    //比较自己写的排序函数和系统的排序函数结果是否相等
    public static boolean isEqual(int[] arr1,int[] arr2){
        if ((arr1 == null && arr2 !=null)||(arr1 !=null && arr2 ==null)||( arr1 == null && arr2 == null)){
            return false;
        }
        if (arr1.length != arr2.length){
            return false;
        }
        for (int i = 0 ; i <arr1.length;i++){
            if (arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }
    //快速排序
    public static void quickSort(int[] arr,int l,int r){

        if ( l < r ){
            swap1(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int q = partition(arr ,l , r);
            quickSort(arr,l,q-1);
            quickSort(arr,q+1,r);
        }
    }
    public static void quickSort1(int[] arr,int l,int r){

        if ( l < r ){
            swap1(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] q = partition1(arr,l,r);
            quickSort(arr,l,q[0]-1);
            quickSort(arr,q[0]+1,r);
        }
    }
    public static void quickSort2(int[] arr,int l,int r){

        if ( l < r ){
            swap1(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int q = partition2(arr,l,r);
            quickSort(arr,l,q-1);
            quickSort(arr,q+1,r);
        }
    }
    //定位函数
    //划分数组，用两个哨兵的方法
    public static int partition(int[] arr,int l,int r){
        int p = arr[l];//设置哨兵位置
        int i = l;
        int j = r;
        while (i < j){
            while (arr[j] >= p && i < j){
                j--;
            }
            if (i<j){
                swap1(arr,i,j);
            }
            while (arr[i] <= p && i < j){
                i++;
            }
            if (i<j){
                swap1(arr,i,j);
            }
        }
        return i;
    }
    //划分数组的优化算法,把一个数组分为三个区，大于区，小于区和等于区
    public static int[] partition1(int[] arr,int l,int  r){
        int i = l-1;
        int j = r;
        while (l < j){
            //每次把最右边的设置为哨兵，这样减少了额外空间
            if (arr[l]<arr[r]){
                swap1(arr,++i,l++);
            }else if (arr[l]>arr[r]){
                swap1(arr,--j,l);
            }else {
                l++;
            }
        }
        swap1(arr,j,r);
        return new int[] {i+1,j};
    }
    //划分数组的一级优化
    public static int partition2(int[] arr,int l,int r){
        int i = l-1;
        int j = r;
        while (l < j){
            //每次把最右边的设置为哨兵，这样减少了额外空间
            if (arr[l]<=arr[r]){
                i++;
                swap1(arr,i,l);
                l++;
            }else{
                j--;
                swap1(arr,j,l);
            }
        }
        swap1(arr,j,r);
        return i+1;
    }
    //主函数
    public static void main(String[] args){

        int maxSize = 100;
        int maxValue = 100;
        int maxTime = 3;
        boolean flag = true;
        int[] arr1 = generateRandomArray(maxSize,maxValue);//随机生成数组
        int[] arr2 = copyArray(arr1);//把数组1中的值复制到arr2中

        quickSort(arr1,0,arr1.length-1);
        arraySort(arr2);

        quickSort1(arr1,0,arr1.length-1);
        arraySort(arr2);

        quickSort2(arr1,0,arr1.length-1);
        arraySort(arr2);
        System.out.println(isEqual(arr1,arr2)?"succeed":"failed");
        printArray(arr1);
    }
}