思路

快速选择排序

步骤

1. 选择基准值pivot，默认为待排序列的最左值
2. 从右往左循环查找，找出小于基准值pivot的元素，下标为j
3. 从左往右循环查找，找出大于基准值皮草他的元素，下标为i
4. 交换i和j；继续循环，直到i和j相遇
   1. 用下标为i的元素代替最左值
   2. 用基准值代替下标为i的元素
5. 此时基准值来到了他最终的位置，递归快排基准值两边的待排序列

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        quickSort(arr,0,arr.length-1);
        return arr;
    }
    private void quickSort(int[] arr,int left,int right){
        if(left>=right) return;
        int i=left;
        int j=right;
        int pivot_index = i;
        int pivot = arr[pivot_index];
        while(i<j){
            while(i<j && arr[j]>=pivot) j--;
            while(i<j && arr[i]<=pivot) i++;
            if(i<j) swap(arr,i,j);
        }
        arr[pivot_index] = arr[i];
        arr[i]=pivot;
        quickSort(arr,left,j-1);
        quickSort(arr,j+1,right);
    }
    private void swap(int[] arr,int i,int j){
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }
}