算法通关村——归并排序

归并排序

1、归并排序原理

​ 归并排序是一种很经典的分治策略。

​ 归并排序(MERGE-SORT)简单来说就是将大的序列先视为若干小的数组，分成几个比较小的结构，然后是利用归并的思想实现的排序方法。将一个大的问题分解成一些小的问题分别求解，再将求解出来的各个答案合并d到一起。

​ 归并排序的过程如下图所示：

​

​ 可以看到，分阶段可以理解成递归拆分子序列的过程，治阶段就是将两个已经有序的子序列合并成一个有序序列的过程。

​ 遍历递归的过程如下：

​

2、代码实现

​ 归并排序的具体代码如下：

public static void mergeSort(int[] array, int start, int end, int temp[]) {if (start >= end) {return;}mergeSort(array, start, (start + end) / 2, temp);mergeSort(array, (start + end) / 2 + 1, end, temp);merge(array, start, end, temp);
}public static void merge(int[] array, int start, int end, int temp[]) {int middle = (start + end) / 2;int left = start;int right = middle + 1;int index = left;while (left <= middle && right <=end) {if (array[left] < array[right]) {temp[index++] = array[left++];} else {temp[index++] = array[right++];}}while (left <= middle) {temp[index++] = array[left++];}while (right <= end) {temp[index++] = array[right++];}for (int i = start; i <= end; i++) {array[i] = temp[i];}
}