首页 > 编程语言 > 详细

归并排序

时间:2018-02-12 20:41:51      阅读:214      评论:0      收藏:0      [点我收藏+]

地将数组不断分为两个子数组,然后对子数组排序后进行合

/*
    思路就是将两个有序数组进行组合,通过递归得到左右排序好的数组
     */
    //组合函数
    public void combine(int[] a,int sta,int mid,int end,int[] res)
    {
        int f = sta;
        int sta2 = mid+1;
        int i = 0;
        //两个数组都没有遍历完
        while (sta<=mid&&sta2<=end)
        {
            if (a[sta]<a[sta2]) res[i++] = a[sta++];
            else res[i++] = a[sta2++];
        }
        while (sta<=mid) res[i++] = a[sta++];
        while (sta2<=end) res[i++] = a[sta2++];
        //将排序结果添加到a中,让a形成有序数组
        for (int j = 0; j < i; j++) {
            a[j+f] = res[j];
        }
    }
    public void sort(int[] a ,int sta,int end,int[] res)
    {
        //分治思想把子数组排为有序数组
        if (sta<end)
        {
            int mid = (sta+end)/2;
            sort(a,sta,mid,res);
            sort(a,mid+1,end,res);
            combine(a,sta,mid,end,res);
        }
    }
    public void mergeSort(int[] a)
    {
        int[] res = new int[a.length];
        sort(a,0,a.length-1,res);
    }

 

归并排序

原文:https://www.cnblogs.com/stAr-1/p/8445377.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!