美文网首页
归并排序

归并排序

作者: Neymar_ | 来源:发表于2016-10-09 10:59 被阅读0次

    优点:所需时间和NlogN成正比

    缺点:需要额外的内存用来存储辅助数组


    /**
     * Created by Administrator on 2016/10/8.
     */
    public class MergeSort {
        private static int copy[];
    
    
        /*
           原地归并
         */
        private static void merge(int[] a, int l, int m, int h) {
            int i = l, j = m + 1;//i,j分别为左右数组的第一个
            for (int k = l; k <= h; k++)
                copy[k] = a[k];
            for (int k = l; k <= h; k++) {
                if (i > m) a[k] = copy[j++];//左边取完
                else if (j > h) a[k] = copy[i++];//右边取完
                else if (copy[i] > copy[j]) a[k] = copy[j++];//右边最小 小于 左边最小
                else a[k] = copy[i++];//右边最小 大于 左边最小
            }
        }
    
        private static void mergeSort(int[] a, int l, int h) {
            int m = (l + h) / 2;
            if (h <= l) return;
            mergeSort(a, l, m);
            mergeSort(a, m + 1, h);
            merge(a, l, m, h);
        }
    
        private static void mergeSort(int[] a) {
            copy = new int[a.length];
            mergeSort(a,0,a.length-1);
        }
    
        public static void main(String[] args) {
            int[] a = {12,30,59,74,39,85,681,234,9444,55,46,39,1,69,2346,4545,55,31};
            mergeSort(a);
            for (int i : a)
                System.out.print(i + ", ");
        }
    
    }
    
    

    相关文章

      网友评论

          本文标题:归并排序

          本文链接:https://www.haomeiwen.com/subject/xpppyttx.html