leaflet hello world

简介

记录自己的学习的算法

归并排序（Merge Sort）该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列合并为有序序列

排序算法JAVA实现

代码如下

    int[] doSort(int[] array) {
        //如果数组只剩下一个元素直接返回
        if (array.length < 2) {
            return array;
        }
        int mid = array.length / 2;
        //拆分
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        //递归对拆分的数组继续进行归并排序
        return merge(doSort(left), doSort(right));
    }

    /**
     * 由于递归结束条件为元素为1，所以调用栈是从一个元素向上拼成有序数组，
     * 每次传入的 left 和 right 都是有序的
     */
    public int[] merge(int[] left, int[] right) {
        int size = left.length + right.length;
        //merge 结果
        int[] merge = new int[size];
        //left 遍历索引
        int l = 0;
        //right 便理索引
        int r = 0;
        //merge 索引
        int m = 0;
        //遍历两个数组，知道某一个数组遍历完毕结束
        while (l < left.length && r < right.length) {
            System.out.println("left    " + printFun(left, l));
            System.out.println("right   " + printFun(right, r));
            //判断大小并插入 merge
            if (left[l] <= right[r]) {
                merge[m++] = left[l++];
            } else {
                merge[m++] = right[r++];
            }
            System.out.println("merge   " + printFun(merge, m - 1));
        }
        //由于是有序的，如果 left 剩下元素，直接插入 merge 后面
        while (l < left.length) {
            merge[m++] = left[l++];
        }
        //由于是有序的，如果 right 剩下元素，直接插入 merge 后面
        while (r < right.length) {
            merge[m++] = right[r++];
        }
        System.out.println("merge   " + printFun(merge, m, m + 1));
        return merge;
    }

输出结果

未排序 [9, 6, 0, 2, 3]
left    [9]
right   [6]
merge   [6] 0
merge   6 9
left    [2]
right   [3]
merge   [2] 0
merge   2 3
left    [0]
right   [2] 3
merge   [0] 0 0
merge   0 2 3
left    [6] 9
right   [0] 2 3
merge   [0] 0 0 0 0
left    [6] 9
right   0 [2] 3
merge   0 [2] 0 0 0
left    [6] 9
right   0 2 [3]
merge   0 2 [3] 0 0
merge   0 2 3 6 9
已排序 [0, 2, 3, 6, 9]

源码地址

https://github.com/RockeyCui/learn-normal

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 rockeycui@163.com