排序算法-快排

1、快速排序

①首先随机选出一个数组中的数，当做参考值

②分成三个区域，比参考值小的区域，等于参考值的区域，比参考值大的区域

③进行快排

④quickSort过程和partition过程

public class QuickSort {
    public static void quickSort(int[] arr){
//        if(arr == null || arr.length<2){
//            return;
//        }
//        quickSort(arr,0,arr.length-1);
        //1、判断是否是个长度大于2或者为空的数组,如果是的话，不用进行排序
        if(arr.length<2 || arr == null){
            return;
        }
        quickSort(arr,0,arr.length-1);
    }
    //arr[]排好序
    public static void quickSort(int[] arr,int L,int R){
//        if(Lp 
p
    //返回等于区域（左边界，右边界），所以返回一个长度为2的数组res，res[0] res[1]
    public static int[] partition(int[] arr,int L,int R){
//        int less = L-1;
//        int more = R;
//        while(L < more){
//            if(arr[L] < arr[R]){
//                swap(arr,++less,L++);
//            }else if(arr[L] > arr[R]){
//                swap(arr,--more,L);
//            }else{
//                L++;
//            }
//        }
//        swap(arr,more,R);
//        return new int[]{less+1,more};
        //定义一个变量，是指小于参考值的左边界，和大于参考值的右边界
        int less = L-1;
        int more = R;
        while(Larr[R]){
                swap(arr,--more,L);
            }else{
                L++;
            }
        }
        //将最后一个存放的参考值与大于参考值的区域的左边界交换
        swap(arr,more++,R);
        //将最后得到的排序完的参考值的区域的左右边界返回
        return new int[]{less+1,more-1};
    }

    private static void swap(int[] arr, int j, int i) {
//        arr[j] = arr[j]^arr[i];
//        arr[i] = arr[j]^arr[i];
//        arr[j] = arr[j]^arr[i];
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args){
        int[] arr = new int[]{12,4,6,8,3,8,56};
        QuickSort.quickSort(arr);
        for(int j=0;j