写点什么

十大排序算法 -- 归并排序

用户头像
阿粤Ayue
关注
发布于: 20 小时前
十大排序算法--归并排序

归并排序

归并,指合并,合在一起。归并排序(Merge Sort)是建立在归并操作上的一种排序算法。其主要思想是分而治之。什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总。即“分”就是把一个大的通过递归成若干个小的,“治”就是将分后的结果在在一起。


若将两个有序集合并成一个有序表,称为 2-路归并,与之对应的还有多路归并。


怎么分

  • 对于排序最好的情况来讲,就是只有两个元素,这时候比较大小就很简单,但是还是需要比较

  • 如果拆分为左右各一个,无需比较即是有序的。

怎么治

借助一个辅助空数组,把左右两边的数组按照大小比较,按顺序放入辅助数组中即可。


以下面两个有序数组为例:


代码实现

public class MergeSort {    public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};    public static int[] sort(int[] array) {        if (array.length < 2) return array;        int mid = array.length / 2;        //分成2组        int[] left = Arrays.copyOfRange(array, 0, mid);        int[] right = Arrays.copyOfRange(array, mid, array.length);        //递归拆分        return merge(sort(left), sort(right));    }    //治---合并    public static int[] merge(int[] left, int[] right) {        int[] result = new int[left.length + right.length];        //i代表左边数组的索引,j代表右边        for (int index = 0, i = 0, j = 0; index < result.length; index++) {            if (i >= left.length) {//说明左侧的数据已经全部取完,取右边的数据                result[index] = right[j++];            } else if (j >= right.length) {//说明右侧的数据已经全部取完,取左边的数据                result[index] = left[i++];            } else if (left[i] > right[j]) {//左边大于右边,取右边的                int a = right[j++];                result[index] = a;            } else {//右边大于左边,取左边的                result[index] = left[i++];            }        }        return result;    }    public static void print(int[] array) {        for (int i : array) {            System.out.print(i + "  ");        }        System.out.println("");    }    public static void main(String[] args) {        print(ARRAY);        System.out.println("============================================");        print(sort(ARRAY));    }}
复制代码

时间复杂度

归并排序方法就是把一组 n 个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为 n 个长度为 1 的序列。然后两两按大小归并。如此反复,直到最后形成包含 n 个数的一个数组。


归并排序总时间 = 分解时间 + 子序列排好序时间 + 合并时间
复制代码


无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计,则:


归并排序总时间 = 子序列排好序时间 + 合并时间
复制代码


假设处理的数据规模大小为 n,运行时间设为:T(n),则 T(n) = n,当 n = 1 时,T(1) = 1


由于在合并时,两个子序列已经排好序,所以在合并的时候只需要 if 判断即可,所以 n 个数比较,合并的时间复杂度为 n。


  • 将 n 个数的序列,分为两个 n/2 的序列,则:T(n) = 2T(n/2) + n

  • 将 n/2 个数的序列,分为四个 n/4 的序列,则:T(n) = 4T(n/4) + 2n

  • 将 n/4 个数的序列,分为八个 n/8 的序列,则:T(n) = 8T(n/8) + 3n

  • ......

  • 将 n/2k 个数的序列,分为 2k 个 n/2k 的序列,则:T(n) = 2kT(n/2k) + kn


当 T(n/2k) = T(1)时, 即 n/2k = 1(此时也是把 n 分解到只有 1 个数据的时候),转换为以 2 为底 n 的对数:k = log2n,把 k 带入到 T(n)中,得:T(n) = n + nlog2n。


使用大 O 表示法,去掉常数项 n,省略底数 2,则归并排序的时间复杂度为:O(nlogn)

算法稳定性

从原理分析和代码可以看出,为在合并的时候,如果相等,选择前面的元素到辅助数组,所以归并排序是稳定的。

发布于: 20 小时前阅读数: 4
用户头像

阿粤Ayue

关注

微信搜:Javatv 2019.10.16 加入

秘密基地:javatv.net

评论

发布
暂无评论
十大排序算法--归并排序