排序

第一种：快排

public int[] MySort (int[] arr) {
        // write code here
        sort(arr,0,arr.length-1);
        return arr;
    }
    private void sort(int[] arr, int start, int end) {
        if(start>=end) return;
        int index = partion(arr,start,end);
        sort(arr,start,index-1);
        sort(arr,index+1,end);
    }
    //找到下标start的元素在数组排完序之后的位置 并替换
    private int partion(int[] arr, int start, int end) {
        int temp=arr[start];
        int left=start;
        int right=end;
        while (left<right){
            //从右往左找第一个小于temp的数
            while (right>left && arr[right]>=temp){
                right--;
            }
            arr[left]=arr[right];
            while (left<right && arr[left]<temp){
                left++;
            }
            arr[right]=arr[left];
        }
        //相遇的位置就是temp的排序后位置
        arr[left]=temp;
        return left;
    }

第二种：归并排序

 public int[] MySort (int[] arr){
        if(arr==null) return arr;
        int[] temp=new int[arr.length];//辅助空间
        sort(arr,0,arr.length-1,temp);
        return arr;
    }

    private void sort(int[] arr, int start, int end,int[] temp) {
        if (start>=end) return;
        int mid=(end-start)/2+start;
        //对左边进行排序
        sort(arr,start,mid,temp);
        //对右边进行排序
        sort(arr,mid+1,end,temp);
        //合并左右两边
        hebing(arr,start,mid,end,temp);
    }
    //将原数组链两个有序的序列进行比较排序并赋值到辅助数组temp，最后再依次赋值回原数组
    private void hebing(int[] arr, int start, int mid, int end, int[] temp) {
        //start--mid
        //mid+1--end
        int i=start;
        int j=mid+1;
        int res = start;
        while (i<=mid && j<=end){
            if(arr[i]<arr[j]){
                temp[res++]=arr[i];
                i++;
            }else {
                temp[res++]=arr[j];
                j++;
            }
        }
        if (i<=mid){
            for(int y=i;y<=mid;y++){
                temp[res++]=arr[y];
            }
        }
        if(j<=end){
            for(int y=j;y<=end;y++){
                temp[res++]=arr[y];
            }
        }
        for (int y=start;y<=end;y++){
            arr[y]=temp[y];
        }
    }