基础排序算法-（5）-归并排序

一、概念

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

二、算法步骤

1、申请一个大小为两个数列长度之和的空间，用来存放合并后的数列。
2、设定两个指针，最初指向两个已经排序的数列起始位置。
3、比较两个指针指向的元素，选择相对较小的元素放入到合并空间，并将指针移到下一个位置。
4、重复步骤3直到指针指向数列未。
5、将另一数列剩下的所有元素直接复制到合并数列的末尾。

三、代码实现

 public static int[]  MergeSortASC(int [] sourceArray) {int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);if (arr.length < 2) {return arr;}int middle = (int) Math.floor(arr.length / 2);int[] left = Arrays.copyOfRange(arr, 0, middle);int[] right = Arrays.copyOfRange(arr, middle, arr.length);return mergeASC(MergeSortASC(left), MergeSortASC(right));}protected static int[] mergeASC(int[] left, int[] right) {int[] result = new int[left.length + right.length];int i = 0;while (left.length > 0 && right.length > 0) {if (left[0] <= right[0]) {result[i++] = left[0];left = Arrays.copyOfRange(left, 1, left.length);} else {result[i++] = right[0];right = Arrays.copyOfRange(right, 1, right.length);}}while (left.length > 0) {result[i++] = left[0];left = Arrays.copyOfRange(left, 1, left.length);}while (right.length > 0) {result[i++] = right[0];right = Arrays.copyOfRange(right, 1, right.length);}return result;}

四、特征