本文首发于个人博客
前言
本系列排序包括十大经典排序算法。
- 使用的语言为:Java
- 结构为:
定义抽象类
Sort
里面实现了,交换,大小比较等方法。例如交换两个值,直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort
。这样我们就能专注于算法本身。
/*
* 返回值等于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
代码
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
可以看到归并排序的性能还是很高的。
代码地址:
- 文中的代码在git上:github地址