归并排序、快速排序、插入排序

class Solution1 {
    private final int SHORT_LENGTH = 7;
    public int[] sortArray(int[] nums) {
        //BubleSort(nums);   冒泡排序超时 
        quickSort(nums , 0 , nums.length - 1);
        return nums;
    }

    //插入排序，当数组长度较小时可不递归，直接使用插入排序
    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = nums[i];
            int j = i;
            while (j > left && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
    }

//快排
    public void quickSort(int[] nums , int left , int right){
        if(right - left <= SHORT_LENGTH){
            insertionSort(nums, left , right);
            return ;
        }
        if(left < right){
            int index = partain(nums , left , right);

            quickSort(nums, left , index - 1);
            quickSort(nums, index + 1 , right);
        }
    }

    public int partain(int[] nums , int left , int right){
        int temp = nums[left];
        while(left < right){
            while(left < right && nums[right] >= temp){        //记住要加等于号
                right--;
            }
            nums[left] = nums[right];
            //left++;  不要移动这里的指针，否则元素赋值会重复

            while(left < right && nums[left] <= temp){
                left++;
            }
            nums[right] = nums[left];
            //right--;  这里不能移动指针，因为还要对该指针指向的位置进行赋值
        }
        nums[left] = temp;
        return left;
    }
}

class Solution {

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        sort(nums,0,len-1,temp);
        return nums;
    }

    //插排，优化当len <= 7 时使用插入排序
    public void insertSort(int[] nums , int left , int right){
        int temp = 0;
        for(int i = left + 1 ; i <= right ; i++){
            int j = i;
            while(j > 0){
                if(nums[j] <= nums[j-1]){
                    temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp;
                    j--;
                }else break;
            }
        }    
    }

    public void sort(int[] nums , int left , int right , int[] temp){
        if(right - left <= 7){
            insertSort(nums,left,right);
            return;
        }
        if(left < right){
        int mid = left + (right - left) / 2;
        sort(nums,left,mid,temp);
        sort(nums,mid+1,right,temp);
        if(nums[mid] <= nums[mid+1]) return;
        mergeSort(nums,left,mid,right,temp);
        }
        return;
    }

    public void mergeSort(int[] nums , int left ,int mid, int right , int[] temp){
        System.arraycopy(nums,left,temp,left,right-left + 1);
        int i = left;
        int j = mid + 1;
        for(int index = left ; index <= right ; index++){
                if(i == mid + 1){
                    nums[index] = temp[j];
                    j++;
                }else if(j == right + 1){
                    nums[index] = temp[i];
                    i++;
                }else if(temp[i] <= temp[j]){
                        nums[index] = temp[i];
                        i++;
                }else{
                    nums[index] = temp[j];
                    j++;
                }
        }
    }
}