Java排序算法——归并排序(Merge Sort)

简介：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。二路归并排序是一种稳定的算法。

两个有序的数组合并的思路：

假设有两个已经排好序的数组arr1[ ]，arr2[ ]，且均是升序或者降序，那么可以进行以下操作：以升序为例，先创建一个尺寸大小为arr1[ ]与arr2[ ]尺寸之和的数组temp[ ]，然后同时从两数组的第0个元素开始遍历，若arr1[i] < arr2[j]，则可以把arr1[i]放入temp[k]中后，执行i++，k++，继续往后比较；若arr1[i] > arr2[j]，则可以把arr2[j]放入temp[k]中后，执行j++，k++，继续往后比较；最终直到把两个数组中的所有元素放入数组temp[ ]中。

上图说话

现比如有集合：{3, 1, 10, 2, 5, 4, 11, 33, 5}

分而治之：

首先先将元素分成大概数量相等的2个子集合，下面就是“分”的过程：

看上面的，可以深度为log2(n) = 4。

当分到最后只能一个元素时，则将两两子集合合并成一个集合，下面就是“治”的过程：

以下面这两个子集合作为例子，作为“治”的例子。

a[0] <= b[0]，则将a[0]移到数组：

a的索引变为1。

a[1] > b[0]，则将b[0]移到数组：

b的索引变为1。

a[1] <= b[1]，则将a[1]移到数组：

a的索引变为2。

a[2] > b[1]，则将b[1]移到数组：

b的索引变为2。

int[] b已经循环完了，则将int[] a的元素移到数组：

最后治到最后结果为：[1,2,3,5,10]

通过循环的“治”过程，最后得到排序的结果：[1,2,3,4,5,5,10,11,33]

Java代码

因为屏幕原因截图截不全，下面是上面方法参数说明

以下代码方便复制粘贴

public class MergeSort {
 public static void main(String[] args) {
 int[] array = new int[]{0,53,63,38,71,25,22,11,95,38};
 sort(array,0,array.length-1);
 System.out.println(Arrays.toString(array));
 }
 private static void sort(int[] array, int start, int end) {
 //跳出递归的条件
 if (start >= end) { return; }
 int mid = (start + end) / 2;
 // 递归实现归并排序
 sort(array, start, mid);
 sort(array, mid + 1, end);
 mergerSort(array, start, mid, end);
 }
 /**
 * 将两个有序序列归并为一个有序序列(二路归并)
 * @param array
 * @param start 开始数组开始的位置
 * @param mid 中间位置(因为合的必定是相挨的数组)
 * @param end 结束的位置
 */
 private static void mergerSort(int[] array, int start, int mid, int end) {
 // 定义一个临时数组，用来存储排序后的结果
 int[] arr = new int[end - start + 1];
 //零时数组的下标
 int low = 0;
 //记录开始的位置，方便后面替换用
 int left = start;
 int center = mid + 1;
 // 取出最小值放入临时数组中
 while (start <= mid && center <= end) {
 //如果第一个数组的数大于第二个数组，则取第二哥数组中的数据
 arr[low++] = array[start] > array[center] ? array[center++] : array[start++];
 }
 // 若还有段序列不为空，则将其加入临时数组末尾
 while (start <= mid) {
 arr[low++] = array[start++];
 }
 while (center <= end) {
 arr[low++] = array[center++];
 }
 // 将临时数组中的值copy到原数组中
 for (int i = left , j = 0; i <= end && j < arr.length; i++,j++) {
 array[i] = arr[j];
 }
 }
}