题解 | #排序#

public int[] MySort (int[] arr) {
        //return QuickSort(arr,0,arr.length-1);
        return ShellSort(arr);
    }
    // 1、比较类排序
    //1.1交换类排序--冒泡排序(超时) 时间复杂度 平均O(n^2) 最坏O(n^2) 最好O(n) 空间复杂度O(1) 稳定
    public int[] BubbleSort (int[] arr) {
        boolean flag = true;
        for(int i = 0;i<arr.length-1;i++){
            for(int j = 0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }
            if(flag){
                break;
            }else{
                flag = true;
            }
        }
        return arr;
    }
    //1.2.快速排序(通过) 时间复杂度 平均O(nlogn) 最坏O(n^2) 最好O(nlogn) 空间复杂度O(logn) 不稳定
    public int[] QuickSort (int[] arr,int l,int r) {
        if(l>=r) return null;
        int i = l-1,j = r+1,mid = arr[(l+r)>>1],temp;
        while(i<j){
            do i++;while(arr[i]<mid);
            do j--;while(arr[j]>mid);
            if(i<j){
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        QuickSort(arr,l,j);
        QuickSort(arr,j+1,r);
        return arr;
    }
    //2、插入类排序
    //2.1 简单插入排序(超时) 时间复杂度 平均O(n^2) 最坏O(n^2) 最好O(n) 空间复杂度O(1) 稳定
    public int[] InsertSort (int[] arr) {
        int value,index;
        for(int i = 1;i<arr.length;i++){
            value = arr[i];
            index = i-1;
            while(index >= 0 && value<arr[index]){
                arr[index+1] = arr[index];
                index --;
            }
            if(index+1!=i){
                arr[index+1] = value;
            }
        }
        return arr;
    }
     //2.2 希尔排序(通过) 时间复杂度 平均O(nlogn) 不稳定
    public int[] ShellSort (int[] arr) {
        for(int gap = arr.length/2; gap>0; gap/=2){
            for(int i=gap;i<arr.length;i++){
                int j = i;
                int temp = arr[j];
                if(arr[j]<arr[j-gap]){
                    while(j-gap>=0&&temp<arr[j-gap]){
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
    //3.选择排序(超时) 时间复杂度 平均O(n^2) 不稳定
    public int[] SelectionSort(int arr[]) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) { //查找最小值
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) { //如果开始的最小值一样则不需要交换
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        return arr;
    }