题目描述：
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

快速排序

class Solution {
    
    /** 
    (1):随机选中一个[l,r]之间的下标值作为基元值
    (2):交换基元值与nums[r]
    (3):从l-1开始从左往右扫描，找到一个小于pivot的值就交换i和j
    (4):重复第3步，直到所有小于pivot的值都在i+1的左边，大于pivot的值都在i+1的右边，返回i+1作为基元值的下标
    (5):递归排序[l, pos - 1]和[pos + 1, r]
    **/
    public int[] sortArray(int[] nums) {
       randonizeQuickSort(nums, 0, nums.length - 1);
       return nums;
    }

    public void randonizeQuickSort(int []nums, int l, int r){
        if(l < r){
            int pos = randonizePartition(nums, l, r);
            randonizeQuickSort(nums, l, pos - 1);
            randonizeQuickSort(nums, pos + 1, r);
        }
    }

    public int randonizePartition(int []nums, int l, int r){
        int pos = new Random().nextInt(r-l+1) + l;
        swap(nums, pos, r);
        return partition(nums, l, r);
    }

    public int partition(int []nums, int l, int r){
        int pivot = nums[r];
        int i = l - 1;
        for(int j=l;j<=r-1;j++){
            if(nums[j] <= pivot){
                i = i + 1;
                swap(nums,i,j);
            }
        }
        swap(nums, i+1, r);
        return i+1;
    }

堆排序

class Solution {
    /** 
    (1):用数组元素构建一个最大堆结构，从下标len/2开始，到下标未0结束
    (2):每次交换堆顶与堆最后一个元素，swap(nums, 0, len),len -= 1,交换完调整堆为最大堆
    (3):堆调整函数：
        a.以i节点为起点，每次从i和左右孩子large = max（i, i * 2 + 1, i * 2 + 2）中找到最大的值,直到i是叶子节点
        b.如果最大值就是i，表示不需要再做调整,调整结束
        c.否则交换large与i对应的值，i调整为较大的孩子节点下标继续调整
    **/
    public int[] sortArray(int[] nums) {
       heapSort(nums);
       return nums;
    }

    public void heapSort(int []nums){
        int len = nums.length - 1;
        buildHeap(nums, len);
        for(int i = len;i >= 1;i--){
            swap(nums, i, 0);
            len -= 1;
            heapify(nums, 0, len);
        }
    }

    public void buildHeap(int []nums, int len){
        for(int i=len/2;i>=0;i--){
            heapify(nums, i, len);
        }
    }

    public void heapify(int []nums, int i, int len){
        for(;(i<<1)+1 <= len;){
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;
            int large = i;
            if(lson <= len && nums[lson] > nums[large]){
                large = lson;
            }
            if(rson <= len && nums[rson] > nums[large]){
                large = rson;
            }
            if(i != large){
                swap(nums, i, large);
                i = large;
            }else{
                break;
            }
        }
    }
    public void swap(int []nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

归并排序

class Solution {
     /**
    MergeSort:
        (1):分，每次将数据二分成左右两部分，直到每部分数据最多只包含一个元素
        (2):并，将二分的左右两部分数据按顺序加入临时数组中，临时数组[l-r]部分数据覆盖原来数据的[l-r]元素
     */
     int []tmp;
    public int[] sortArray(int[] nums) {
        int l = 0, r = nums.length - 1;
        tmp = new int[nums.length];
        mergeSort(nums, l, r);
        return nums;
    }

    public void mergeSort(int []nums, int l, int r){
        if(l >= r){
            return;
        }
        int mid = (r - l)/2 + l;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int i = l, j = mid + 1;
        int cnt = 0;
        while(i <= mid && j <= r){
            if(nums[i]<=nums[j]){
                tmp[cnt++]=nums[i++];
            } else {
                tmp[cnt++]=nums[j++];
            }
        }
        while(i <= mid){
            tmp[cnt++]=nums[i++];
        }
        while(j <= r){
            tmp[cnt++]=nums[j++];
        }
        for(int k=0;k<r - l + 1;k++){
            nums[k+l] = tmp[k];
        }
    }
}