几种O(Nlog(N))的排序

排序

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

归并排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        mergeSort(arr, 0, arr.length-1);
        return arr;
    }

    public void mergeSort(int[] arr, int l, int r){
        if(l == r){
            return;
        }

        int mid = l + ((r-l) >> 1);    //中点位置
        mergeSort(arr, l, mid);
        mergeSort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

    public void merge(int[] arr, int l, int mid, int r){
        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;    //左半数组的下标
        int p2 = mid + 1;    //右半数组的下标

        //判断是否越界
        while(p1 <= mid && p2 <= r){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        //p1没有越界,说明p2越界了,将左边剩余元素拷贝到辅助数组
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }

        //p2没有越界,说明怕越界了
        while(p2 <= r){
            help[i++] = arr[p2++];
        }

        //将辅助数组元素拷贝还原数组
        for(i = 0; i < help.length; i++){
            arr[l+i] = help[i]; 
        }


    }
}
全部评论

相关推荐

服从性笔试吗,发这么多笔,现在还在发。
蟑螂恶霸zZ:傻 x 公司,发两次笔试,两次部门匹配挂,
投递金山WPS等公司10个岗位 >
点赞 评论 收藏
分享
10-07 23:57
已编辑
电子科技大学 Java
八街九陌:博士?客户端?开发?啊?
点赞 评论 收藏
分享
10-09 00:50
已编辑
长江大学 算法工程师
不期而遇的夏天:1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务