排序

1. 快速排序

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    public void quickSort(int[] nums,int left,int right){
        if(left>=right){return;}
        int i = left;
        int j = right;
        int index = i;
        while(i<j){
            while(i<j&&nums[j]>=nums[index]){
                j--;
            }
            while(i<j&&nums[i]<=nums[index]){
                i++;
            }
            if(i<j){
                swap(nums,i,j);
            }
        }
        swap(nums,i,index);
        quickSort(nums,left,i-1);
        quickSort(nums,i+1,right);
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

2. 堆排

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums,0,nums.length-1);
        return nums;
    }

    public void heapSort(int[] nums,int left,int right){
        // 构建堆,自下往上构建堆;
        for(int i=right/2;i>=0;i--){
            heapfy(nums,i,right);
        }
        // 交换位置;重新构建;
        for(int j=right;j>=left;j--){
            swap(nums,0,j);
            heapfy(nums,0,j-1);
        }
    }

    public void heapfy(int[] nums,int i,int end){
        int left = 2*i+1;
        int right = 2*i+2;
        int LargeIndex = i;
        if(left<=end&&nums[left]>nums[LargeIndex]){
            LargeIndex = left;
        }
        if(right<=end&&nums[right]>nums[LargeIndex]){
            LargeIndex = right;
        }
        if(i!=LargeIndex){
            swap(nums,i,LargeIndex);
            heapfy(nums,LargeIndex,end);
        }
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

3. 归并排序

class Solution {
    public int[] sortArray(int[] nums) {
        int[] temp = new int[nums.length];
        MergeSort(nums,0,nums.length-1,temp);
        return nums;
    }
    // 归并
    public void MergeSort(int[] nums,int start, int end,int[] temp){
        if(start>=end){return;}
        int mid = (start+end)/2;
        MergeSort(nums,start,mid,temp);
        MergeSort(nums,mid+1,end,temp);
        Merge(nums,start,mid,mid+1,end,temp);
    }
    public void Merge(int[] nums,int leftStart,int leftEnd,int rightStart,int rightEnd,int[] temp){
        int tempIndex = leftStart;
        int i = tempIndex;
        int j = leftStart;
        while(leftStart<=leftEnd&&rightStart<=rightEnd){
            if(leftStart<=leftEnd&&nums[leftStart]<nums[rightStart]){
                temp[tempIndex++] = nums[leftStart++];
            }else{
                temp[tempIndex++] = nums[rightStart++];
            }
        }
        while(leftStart<=leftEnd){
            temp[tempIndex++] = nums[leftStart++];
        }
        while(rightStart<=rightEnd){
            temp[tempIndex++] = nums[rightStart++];
        }
        //
        while(j<=rightEnd){
            nums[j++] = temp[i++];
        }
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}