题解 | #排序# JAVA版本 快排

为了实现进阶需求，实现了Java版本快排

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        quick(arr, 0, arr.length-1);
        return arr;
    }
    
    private void quick(int[] arr, int left,int right) {
        if (left < right) {
            int baseIndex = getBaseIndex(arr, left, right);
            quick(arr, left, baseIndex - 1);
            quick(arr, baseIndex + 1, right);
        }
    }
    
    private int getBaseIndex(int[] arr, int left,int right) {
        int baseIndex = left;
        while (left < right) {
            if (arr[right] >= arr[baseIndex]) {
                right--;
                continue;
            }
            if (arr[left] <= arr[baseIndex]) {
                left++;
                continue;
            }
            swap(arr, left, right);
        }
        //最终将基准数归位
        swap(arr, left, baseIndex);
        return left;
    }

    private void swap(int[] arr, int left,int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}