排序

思路：快速排序，具体如下：两个移动的指针和一个基准值，一次排序后应达到基准值是一个分水岭，按从小到大排序，左边应该比基准值小，右边应该比基准值大。基本思路是：开始left不动，如果right指向的值大于等于基准值（基准值的大小可以等于一开始left指向的值），就right--；如果不满足上述条件，就right指向的值赋给left，同时left++；如果left指向的值小于等于基准值，就left++；如果不满足，就left指向的值赋给right，同时right--；循环结束条件：left<rigth。
代码：

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;
    }
    public void quickSort(int[] arr,int low,int high){
        if(low<high){
            //快排
            int i=low,j=high,key = arr[low];
            while(i<j){
                while(i<j&&arr[j]>=key){
                    j--;
                }
                if(i<j){
                    arr[i] = arr[j];
                }
                while(i<j&&arr[i]<=key){
                    i++;
                }
                if(i<j){
                    arr[j] = arr[i];
                }
            }
            arr[i] = key;
            quickSort(arr,low,i-1);
            quickSort(arr,i+1,high);
        }
    }
}