题解 | #排序#

1.直接插入排序，该方法的时间复杂度为O(n²)，可能会在时间上超出限制，慎用。

直接插入排序的思想：依次将待排序序列中的每一个记录插入到排序好了的序列中，知道全部记录排序好了为止。

public int[] MySort (int[] arr) {
        int i,j,temp;
        for(i=1;i<arr.length;i++){
            //初始化有序区为数组第一个元素arr[0]，故从下标为1的开始循环。
            temp=arr[i];
            //扩大有序区间到i，从后往前，将记录后移，在判断到暂存值大于循环中的有序区的某记录后停止循环，将暂存值插入
            for(j=i-1;j>=0&&temp<arr[j];j--) arr[j+1]=arr[j];
            arr[j+1]=temp;
        }
    return arr;
     }

2.用库函数Arrays.sort实现排序

public int[] MySort (int[] arr) {
    Arrays.sort(arr);
    return arr;
}

3. 进行冒泡排序 ,一种交换排序，是最简单的排序方法，但如果有非常大的数据量需要处理的话，需要的时间会相对其他排序方法大的多。

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

代码：

public int[] MySort (int[] arr) {
         int temp;//定义一个临时变量
        for(int i=0;i<arr.length-1;i++){//冒泡趟数
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j+1]<arr[j]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        return arr;
    }

3.进行 快速排序 (是对冒泡排序的一种改进)

public int[] MySort (int[] arr) {
      recursion(0,arr.length-1,arr);
        return arr;
    }

    //一次划分
    public int partition(int first,int last,int []arr){
         int temp=arr[first];
        while(first<last){
            while(first<last && arr[last]>=temp)
                last--;
            arr[first]=arr[last];
            while(first<last && arr[first]<=temp)
                first++;
            arr[last]=arr[first];
        }
        arr[first]=temp;
        return first;
    }

    //递归
    public void  recursion(int first,int last,int []arr){
        if(first>=last) return ;
        if(first<last){
            int mid=partition(first,last,arr);
            recursion(first,mid-1,arr);
            recursion(mid+1,last,arr);
        }
    }

4. 进行 希尔排序 （可以看成是 直接排序的改进，在直接排序的前提下进行增量为d(最后必须为1)的查找。(这里应该这么理解：相邻之间隔着一个d的为一个子序列，这个序列进行排序，将所有子序列进行排序完成后，增量d折半继续进行排序直至d为1)

   //希尔排序，是直接插入排序的一种改进
    public int[] MySort (int[] arr) {
        int d,i,j,temp;  
        //增量为d进行直接插入排序
        for(d= arr.length/2;d>=1;d=d/2){
            for(i=d;i<arr.length;i++){
                temp=arr[i];
                //记录后移，可以参考直接排序，从有序区最后一个进行判断
                for(j=i-d;j>=0&& temp<arr[j];j=j-d)
                    arr[j+d]=arr[j];
                arr[j+d]=temp;
            }
        }
        return arr;
    }