题解 | #排序#

//JAVA 快速排序，挖坑法，搬运的菜鸟教程的题解思路。仅供参考

import java.util.*;

//快速排序，双指针挖坑法+ 分治
//填坑法这个解法比较容易理解，可以耐心看注释。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        return quickSort(arr, 0, arr.length-1);
    }
    private int[] quickSort(int[] arr, int low, int high) {
        if(low>=high) return arr;
        int i=low, j= high, x = arr[i]; //把基准值拎出来，这时候i=0的地方产生一个坑、
        //第一轮
        while(i < j){
            //从基准点的另一边开始比,如果比基准大就把由指针往前移。
            while(i < j && arr[j] >= x)
                j--;
            //经过上面while循环，如果基准右边的都比基准大的话，就会一直j-- 到和基准i相遇
            //如果j还是比i大，说明遇到了比基准小的，
            //这时候就把这个值填到基准的那个坑里，同时这个值就变成了一个坑。
            if(j > i){
                //用比基准小的值去填坑。
                arr[i] = arr[j];
                i++;
            }
            //左侧开始类似的上面的操作。
            while(i < j && arr[i] < x)
                i++;
            if(i < j){
                //用比基准值大的去填上面产生的那个坑。
                arr[j] = arr[i];
                j--;
            }
        }
        //全部走完到i和j相遇时，把基准值填入坑。
        arr[i]=x;
        //递归
        arr = quickSort(arr,low,i-1);
        arr = quickSort(arr,i+1,high);
        return arr; 
    }
}