快排

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;
    }

    void quickSort(int[] arr, int left, int right) {
        if(left < right) {
            int lo = left, hi = right, base = arr[left];
            while(lo < hi) {
                // 从右到左寻找第一个小于base的下标，补坑
                while(lo < hi && arr[hi] >= base) {
                    hi--;
                }
                if(lo < hi) {
                    arr[lo++] = arr[hi];
                }
                // 从左到右寻找第一个大于base的下标，补坑
                while(lo < hi && arr[lo] <= base) {
                    lo++;                    
                }
                if(lo < hi) {
                    arr[hi--] = arr[lo];
                }
            }
            // 此时 base 左边和右边的元素分别都小于和等于base
            arr[lo] = base;
            quickSort(arr, left, lo - 1);
            quickSort(arr, hi + 1, right);

        }
    }
}