题解 | #排序#

排序

http://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896

看了一下各位coder发出来的题解，发现不少人出现了以下几个问题，

① 关于排序算法的选择，此题明确要求了时间复杂度是 O(nlogn)，空间复杂度是 O(n)，

满足这个时空复杂度要求的排序算法是———归并排序，所以那些用了快排和堆排序的

同学，需要注意哟，它俩的空间复杂度不满足要求哟！！！

② 对于直接调用 Arrays.sort() 这种API 的同学，也是不行的哟，因为这种算法题是为了

考查你的算法思维和编码能力，要求你能自己构造并实现满足要求的算法，而不是调用

已有的API。

下面附上我自己的答案，仅供参考：

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        /* 要求：时间复杂度 O(nlogn)，空间复杂度 O(n)
                满足这种时间和空间复杂度的排序算法是——归并排序
                本次采用二路归并排序算法
        */
        int low = 0;
        int high = arr.length - 1;
        int[] temp = new int[arr.length];
        return mergeSort(arr,low,high,temp);
    }
    private int[] mergeSort(int[] arr,int low,int high,int[] temp){
        if(low > high){
            return null;
        }else if(low == high){
            return arr;
        }else{
            int mid = (low + high) / 2;
            mergeSort(arr,low,mid,temp);
            mergeSort(arr,mid+1,high,temp);
            return mergeArr(arr,low,mid,high,temp);
        }
    }
    private int[] mergeArr(int[] arr,int low,int mid,int high,int[] temp){
        int i = low;
        int j = mid + 1;
        int k = low;
        while(i <= mid && j <= high){
            if(arr[i] <= arr[j]){
                temp[k] = arr[i];
                i++;
                k++;
            }else{
                temp[k] = arr[j];
                j++;
                k++;
            }
        }
        while(i <= mid){
            temp[k] = arr[i];
            k++;
            i++;
        }
        while(j <= high){
            temp[k] = arr[j];
            k++;
            j++;
        }
        for(int index = low; index <= high;index++){
            arr[index] = temp[index];
        }
        return arr;
    }
}