题解 | #排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        //异常判断
        if(arr == null || arr.length < 2){
            return arr;
        }
        quickSort(arr,0,arr.length-1);//注意数组长度与下标的关系
        return arr;
    }
    private  void quickSort(int[] arr, int start, int end ) {
        if (end<=start){     //***********递归终止条件
            return;
        }
        //基准数后移
        swap(arr,end,start+(int)(Math.random()*(end-start+1)));//*******明确基准书调整之后位置
        int[] bounds = partition(arr,start,end);

        quickSort(arr,start,bounds[0]-1);
        quickSort(arr,bounds[1]+1,end);

    }

    private  int[] partition(int[] arr, int start, int end) {
        int value = arr[end];
        int less = start-1;
        int more = end;
        int eq = start;
        while(eq<more){
            if(arr[eq]< value){
                swap(arr,++less,eq++);
            }
            else if (arr[eq] > value){
                swap(arr,--more,eq);
            }else{
                eq++;
            }
        }
        swap(arr,end,eq);
        return new int[]{less+1,eq};
    }

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