十大排序算法之归并排序

发表于 | 分类于
字数统计: 1.3k 字 | 阅读时长 ≈ 5 分钟

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

  • 使用的语言为：Java
  • 结构为：
    定义抽象类Sort里面实现了，交换，大小比较等方法。例如交换两个值，直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
	 * 返回值等于0，代表 array[i1] == array[i2]
	 * 返回值小于0，代表 array[i1] < array[i2]
	 * 返回值大于0，代表 array[i1] > array[i2]
	 */
	protected int cmp(int i1, int i2) {
		return array[i1].compareTo(array[i2]);
	}
	
	protected int cmp(T v1, T v2) {
		return v1.compareTo(v2);
	}
	
	protected void swap(int i1, int i2) {
		T tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}

什么是归并排序

  • 归并排序（mergesort）是创建在归并操作上的一种有效的排序算法，效率为O(nlog n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

概述

  • 采用分治法:

    • 分割：递归地把当前序列平均分割成两半。
    • 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

归并操作

  • 归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

递归法（Top-down）

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

迭代法（Bottom-up）

原理如下（假设序列共有n个元素）：

  • 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
  • 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
  • 重复步骤2，直到所有元素排序完毕，即序列数为1

时空复杂度

  • 最好时间复杂度：O(nlogn)
  • 最坏、平均时间复杂度：O(nlogn)
  • 空间复杂度：O(n)

算法稳定性

  • 归并排序是一种稳定排序算法。

是否是原地算法

  • 何为原地算法？
    • 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
    • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
  • 非原地算法，称为 Not-in-place 或者 Out-of-place
  • 归并排序不属于 In-place

代码

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
47
48
package YZ.Sort;

public class MergeSort <T extends Comparable<T>> extends Sort<T> {

	private T[] leftArray;
	@Override
	protected void sort() {
		// TODO Auto-generated method stub
		leftArray = (T[]) new Comparable[array.length>>1];
		sort(0, array.length);
	}

	/**
	 * 对 [begin, end) 范围的数据进行归并排序
	 */
	private void sort(int begin,int end) {
		if (end-begin<2) {
			return;
		}
		int mid = (begin + end)>>1;
		sort(begin, mid);
		sort(mid,end);
		
		merge(begin, mid, end);
		
	}
	/**
	 * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
	 */
	private void merge(int begin, int mid, int end) {
		int li = 0, le = mid-begin; //左边数组（基于leftArray）
		int ri = mid,re=end;//右边数组(基于array)
		int ai = begin; //array的索引
		//备份左边数组
		for (int i = li; i < le; i++) {//拷贝左边数组到leftArray
			leftArray[i] = array[begin+i];
		}
		
		while (li<le) { //左边没有结束
			if (ri<re && cmp(array[ri], leftArray[li])<0) {
				array[ai++] = array[ri++];//拷贝右边数组到array
			}else {
				array[ai++] = leftArray[li++];//拷贝左边数组到array
			}
			
		}//注意，如果cmp比较那里改成<= 就会失去稳定性
	}
}

结果

数据源：从1到20000之间随机生成10000个数据来测试

Integer[] array = Integers.random(10000, 1, 20000);

结果如下：

【BubbleSort】
稳定性：true 耗时：0.481s(481ms) 比较次数：4999.50万 交换次数：2467.42万

【BubbleSort1】
稳定性：true 耗时：0.428s(428ms) 比较次数：4998.82万 交换次数：2467.42万

【BubbleSort2】
稳定性：true 耗时：0.405s(405ms) 比较次数：4993.60万 交换次数：2467.42万

【InsertionSort1】
稳定性：true 耗时：0.239s(239ms) 比较次数：2468.42万 交换次数：2467.42万

【InsertionSort2】
稳定性：true 耗时：0.186s(186ms) 比较次数：2468.42万 交换次数：0

【InsertionSort3】
稳定性：true 耗时：0.114s(114ms) 比较次数：11.90万 交换次数：0

【HeapSort】
稳定性：false 耗时：0.005s(5ms) 比较次数：23.53万 交换次数：9999

【MergeSort】
稳定性：true 耗时：0.004s(4ms) 比较次数：12.05万 交换次数：0

可以看到归并排序的性能还是很高的。

代码地址：