MergeSort

归并排序(Merge sort),是创建在归并操作上的一种基于比较的排序算法。1945 年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

基本原理

归并排序算法是分治策略实现对 n 个元素进行排序的算法。

其基本思想是:将待排序元素分成大小大致相同的 2 个子集合,分别对 2 个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。

算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤 3 直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

算法图解

参考 dreamcatcher-cx 博客 图解排序算法(四)之归并排序

采用经典的分治(divide-and-conquer)策略(分治法将问题分解成规模更小、解法相同的子问题,然后通过子问题的解构造出原问题的解)。

divide-and-conquer

分阶段是递归拆分子序列的过程,递归深度为 \(log_2 n\).

对于治阶段,需要将两个已经有序的子序列合并成一个有序序列,例如上图中的最后一次合并,要将 [4,5,7,8] 和 [1,2,3,6] 两个已经有序的子序列,合并为最终序列 [1,2,3,4,5,6,7,8] ,具体实现步骤如下:

merge-1 merge-2

动画演示

MergeSort

参考实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Arrays;

/**
* @author wylu
*/
public class MergeSort {

public static void merge(int[] arr, int left, int mid, int right, int[] tmp) {
int i = left, j = mid + 1, t = 0;
while (i <= mid && j <= right) tmp[t++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
while (i <= mid) tmp[t++] = arr[i++];
while (j <= right) tmp[t++] = arr[j++];
t = 0;
while (left <= right) arr[left++] = tmp[t++];
}

//递归
public static void recursiveSort(int[] arr, int left, int right, int[] tmp) {
if (left < right) {
int mid = (left + right) / 2;
recursiveSort(arr, left, mid, tmp);
recursiveSort(arr, mid + 1, right, tmp);
merge(arr, left, mid, right, tmp);
}
}

//非递归
public static void nonRecursiveSort(int[] arr) {
int[] tmp = new int[arr.length];
for (int size = 1; size < arr.length; size *= 2) {
int left, mid, right;
for (left = 0; left + size < arr.length; left = right + 1) {
mid = left + size - 1;
right = Math.min(mid + size, arr.length - 1);
merge(arr, left, mid, right, tmp);
}
}
}

public static void main(String[] args) {
int[] arr = {3, 1, 4, 9, 6, 0, 7, 2, 5, 8};
// MergeSort.recursiveSort(arr, 0, arr.length - 1, new int[arr.length]);
MergeSort.nonRecursiveSort(arr);
System.out.println(Arrays.toString(arr));
}
}

复杂度分析

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
归并排序 \(O(nlogn)\) \(O(nlogn)\) \(O(nlogn)\) \(O(n)\) Out-place 稳定

References

https://en.wikipedia.org/wiki/Merge_sort

https://www.cnblogs.com/chengxiao/p/6194356.html

https://youliao.163yun.com/api-server/rss/xiaomi/item/IN2WDOMKAWVNTZV.html?ref=browser_news&s=mb&cp=cn-netease-youliao-browser&docid=44797c69e120935b2c4790d933d02a9b&itemtype=news&cateCode=rec&category=%E7%A7%91%E6%8A%80