题解 | 排序

import java.util.*;


public class Solution {
    public int[] MySort (int[] arr) {
        // write code here
        return quickSort(arr, 0, arr.length-1);
    }
    public int[] quickSort(int[] arr, int left, int right){
        if(left < right){
            int point = partition(arr, left, right);
            quickSort(arr,left,point-1);
            quickSort(arr,point+1,right);
        }
        return arr;
    }

    // 快速排序，选择一个元素作为基准元素，对待排序元素进行分区，比基准大的放在右边，比基准小的放在左边
    public int partition(int[] arr, int left, int right){
        int base = arr[left];
        while(left < right){
            while(left < right && arr[right] >= base){
                right--;
            }
            swap(arr, left, right);
            while(left < right && arr[left] <= base){
                left++;
            }
            swap(arr, left, right);
        }
        return left;
    }

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