// @Title: 排序数组 (Sort an Array)
// @Author: qisiii
// @Date: 2022-02-20 10:55:44
// @Runtime: 913 ms
// @Memory: 54.9 MB
// @comment: 
// @flag: 
class Solution {
    public int[] sortArray(int[] nums) {
doQuickSort(nums,0,nums.length-1);
return nums;
    }
    public void doQuickSort(int[] nums, int left, int right){
        if (left>=right){
            return;
        }
        int temp=nums[left];
        int min=left;
        int max=right;
        while (min<max){
            //右指针左移
            while (min<max&&nums[max]>=temp){
                max--;
            }
            //将找到的小于标志数的放在左指针上，同时左指针右移
            if (min<max){
                nums[min]=nums[max];
                min++;
            }
            //左指针右移
            while (min<max&&nums[min]<=temp){
                min++;
            }
            //将找到的大于标志数的放在右指针上，同时右指针左移
            if (min<max){
                nums[max]=nums[min];
                max--;
            }
        }
        nums[min]=temp;
        doQuickSort(nums,left,min-1);
        doQuickSort(nums,min+1,right);
    }
}

// @Title: 排序数组 (Sort an Array)
// @Author: qisiii
// @Date: 2023-05-18 23:32:22
// @Runtime: 33 ms
// @Memory: 53.7 MB
// @comment: 归并排序，时间复杂度稳定nlgn
// @flag: GREEN
class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return nums;
    }

    private void mergeSort(int[] nums,int l,int r){
        if(l>=r){
            return;
        }
        int m=l+(r-l)/2;
        mergeSort(nums,l,m);
        mergeSort(nums,m+1,r);
        merge(nums,l,m,r);

    }

    private void merge(int[] nums,int l,int m,int r){
        int[] left=new int[m-l+1],right=new int[r-m];
        for(int i=l,j=0,k=0;i<=r;i++){
            if(i<=m){
                left[j++]=nums[i];
            }else{
                right[k++]=nums[i];
            }
        }
        int i=l,j=0,k=0;
        while(i<=r){
            if(j==left.length){
                nums[i++]=right[k++];
                continue;
            }
            if(k==right.length){
                nums[i++]=left[j++];
                continue;
            }
            if(left[j]<right[k]){
                nums[i++]=left[j++];
            }else{
                nums[i++]=right[k++];
            }
        }
    }
}

// @Title: 排序数组 (Sort an Array)
// @Author: qisiii
// @Date: 2023-05-16 07:39:21
// @Runtime: 2578 ms
// @Memory: 53.3 MB
// @comment: 插入排序，平均n2
// @flag: RED
class Solution {
    public int[] sortArray(int[] nums) {
        for(int i=1;i<nums.length;i++){
            int j=i,temp=nums[i];
            while (j>0&&temp<nums[j-1]){
                nums[j]=nums[j-1];
                j--;
            }
            nums[j]=temp;
        }
        return nums;
    }
}