十大排序算法之归并排序

本文首发于个人博客

前言

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

  • 使用的语言为: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

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

代码地址: