JAVA十大排序算法之归并排序详解_Java教程

JAVA十大排序算法之归并排序详解

2021-11-30 10:43阿粤Ayue Java教程

这篇文章主要介绍了java中的归并排序，本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下

归并排序

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

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

JAVA十大排序算法之归并排序详解

怎么分

对于排序最好的情况来讲，就是只有两个元素，这时候比较大小就很简单，但是还是需要比较
如果拆分为左右各一个，无需比较即是有序的。

怎么治

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

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

JAVA十大排序算法之归并排序详解

代码实现

				?

									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));

									    }

									}