高级排序算法-归并排序
辅助工具
数组工具类代码 : https://blog.****.net/love905661433/article/details/83106078
用于对比的基础排序代码 : https://blog.****.net/love905661433/article/details/83117977
归并排序
- O(nlogn)级别算法
- 需要额外的辅助空间
- 稳定的排序算法
对于排序算法稳定性的定义, 这里直接引用百度词条:
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
排序步骤 :
-
首先将一个数组递归进行分解, 知道分解为每一部分都是一个元素, 这时每一部分都是有序的了
-
然后两两进行归并, 递归进行, 直到再归并成一个数组, 排序就完成了, 如下图所示:
代码实现
package sort.merge;
import sort.Sort ;
/**
* 归并排序
* @author 七夜雪
*
*/
public class MergeSort implements Sort {
@Override
public void sort(int [] arr) {
mergeSort(arr, 0, arr.length - 1);
}
/**
* 对数组arr的[l, r]的区间进行排序
* @param arr
* @param l
* @param r
*/
private void mergeSort(int[] arr, int l, int r){
// 递归终止条件
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
// 对[l, mid]部分进行归并排序
mergeSort(arr, l, mid);
// 对[mid + 1, r]进行归并排序
mergeSort(arr, mid + 1, r);
// 对[l, mid], [mid + 1, r]这两部分进行归并
merge(arr, l, mid, r);
}
/**
* 对数组[l, mid], [mid + 1, r]这两部分进行归并
* @param arr
* @param l
* @param mid
* @param r
*/
private void merge(int[] arr, int l, int mid, int r){
// 用于归并排序的辅助空间, 因为[l, r]是前闭后闭的区间, 所以aux的大小是r - l + 1
int[] aux = new int[r - l + 1];
for (int i = 0; i < aux.length; i++) {
aux[i] = arr[i + l];
}
// for (int i = l; i <= r; i++) {
// aux[i - l] = arr[i];
// }
// 用于记录左半部分数组下标
int leftIndex = l;
// 用于记录右半部分数组下标
int rightIndex = mid + 1;
// 循环进行归并
for (int k = l; k <= r; k++) {
// 表示左侧部分已经完成归并, 直接使用右侧部分进行归并
if (leftIndex > mid) {
arr[k] = aux[rightIndex - l];
rightIndex++;
// 表示右侧部分已经完成归并, 直接使用左侧部分进行归并
} else if (rightIndex > r) {
arr[k] = aux[leftIndex - l];
leftIndex++;
// 左侧元素小于右侧元素, 使用左边元素进行归并
} else if (aux[leftIndex - l] < aux[rightIndex - l]) {
arr[k] = aux[leftIndex - l];
leftIndex++;
} else {
arr[k] = aux[rightIndex - l];
rightIndex++;
}
}
}
}
归并排序优化
虽然归并排序是nlogn级别的算法, 但是在数组数据量比较小的时候, 插入排序的效率仍然是高于归并排序的, 所以可以在对数组分解到足够小之后, 使用插入排序, 然后再递归进行归并排序, 具体代码如下 :
package sort.merge;
import sort.Sort ;
import utils.ArrayUtil ;
/**
* 归并排序
* 优化 : 对于较小的数组使用插入排序性能要优于归并排序,
* 所以可以在分解到较小的部分时, 使用插入排序对数组进行排序
* @author 七夜雪
*
*/
public class MergeSort2 implements Sort {
@Override
public void sort(int [] arr) {
mergeSort(arr, 0, arr.length - 1);
}
/**
* 对数组arr的[l, r]的区间进行排序
* @param arr
* @param l
* @param r
*/
private void mergeSort(int[] arr, int l, int r){
// 递归终止条件, 小于等于16个元素时使用插入排序
if (r - l < 16) {
// 对arr数组的[l,r]区间进行排序, 插入排序算法
ArrayUtil.insertSort(arr, l, r);
return;
}
int mid = l + (r - l) / 2;
// 对[l, mid]部分进行归并排序
mergeSort(arr, l, mid);
// 对[mid + 1, r]进行归并排序
mergeSort(arr, mid + 1, r);
// 对[l, mid], [mid + 1, r]这两部分进行归并
merge(arr, l, mid, r);
}
/**
* 对数组[l, mid], [mid + 1, r]这两部分进行归并
* @param arr
* @param l
* @param mid
* @param r
*/
private void merge(int[] arr, int l, int mid, int r){
// 用于归并排序的辅助空间, 因为[l, r]是前闭后闭的区间, 所以aux的大小是r - l + 1
int[] aux = new int[r - l + 1];
for (int i = 0; i < aux.length; i++) {
aux[i] = arr[i + l];
}
// for (int i = l; i <= r; i++) {
// aux[i - l] = arr[i];
// }
// 用于记录左半部分数组下标
int leftIndex = l;
// 用于记录右半部分数组下标
int rightIndex = mid + 1;
// 循环进行归并
for (int k = l; k <= r; k++) {
// 表示左侧部分已经完成归并, 直接使用右侧部分进行归并
if (leftIndex > mid) {
arr[k] = aux[rightIndex - l];
rightIndex++;
// 表示右侧部分已经完成归并, 直接使用左侧部分进行归并
} else if (rightIndex > r) {
arr[k] = aux[leftIndex - l];
leftIndex++;
// 左侧元素小于右侧元素, 使用左边元素进行归并
} else if (aux[leftIndex - l] < aux[rightIndex - l]) {
arr[k] = aux[leftIndex - l];
leftIndex++;
} else {
arr[k] = aux[rightIndex - l];
rightIndex++;
}
}
}
}
如果一个数组是近乎有序的, 或者说是完全有序的, 上述步骤会有很多无用的merge操作, 所以可以在进行merge前增加一个判断, 效率也会有一定的提高, 代码如下 :
/**
* 对数组arr的[l, r]的区间进行排序
* @param arr
* @param l
* @param r
*/
private void mergeSort(int[] arr, int l, int r){
// 递归终止条件, 小于等于16个元素时使用插入排序
if (r - l < 16) {
ArrayUtil.insertSort(arr, l, r);
return;
}
int mid = l + (r - l) / 2;
// 对[l, mid]部分进行归并排序
mergeSort(arr, l, mid);
// 对[mid + 1, r]进行归并排序
mergeSort(arr, mid + 1, r);
// 判断是否需要进行merge, 因为[l, mid], [mid + 1, r]这两部分都是排好序的数组
if (arr[mid] > arr[mid + 1]) {
// 对[l, mid], [mid + 1, r]这两部分进行归并
merge(arr, l, mid, r);
}
}
自底向上的归并排序
上面的归并排序是自顶向下的归并排序, 对于归并排序也可以自底向上进行归并, 排序方法如下 :
- 从下往上分解成小块, 然后一层层往上进行归并, 最终归并成一整个数组, 如下图所示 :
上图从下往上步骤如下:
- 每个元素作为一部分, 进行归并, 归并后结果如第三行
- 然后按照每两个元素作为一部分, 进行归并, 归并后结果如第二行
- 最后对每四个元素作为一部分, 进行归并, 归并后结果如第一行, 整个数组已经有序了
代码实现 :
public void sort(int [] arr) {
int length = arr.length;
// 数组元素个数小于等于16时, 直接使用插入排序
if (length <= 16) {
ArrayUtil.insertSort(arr, 0, length);
return;
}
for (int sz = 8; sz < length; sz += sz) {
// 每次遍历2*sz个长度
for (int i = 0; i + sz < length; i +=sz + sz) {
if (sz == 8 ) {
ArrayUtil.insertSort(arr, i, Math.min(i + sz + sz -1, length - 1));
} else {
if (arr[i + sz - 1] > arr[i + sz]) {
// 对[i, i + sz -1]和[i + sz, 2*sz + i -1]区间进行merge操作
merge(arr, i, i + sz - 1, Math.min(i + sz + sz -1, length - 1));
}
}
}
}
}
测试
对插入排序, 进行了优化的各个版本的归并排序进行性能测试, 这里使用了Junit进行测试, 代码如下 :
/**
* 测试插入排序和归并排序性能
*/
@Test
public void testSort(){
// 生成一个随机数组
int[] arr = ArrayUtil.generateArray(100000, 0, 100000);
int[] arr1 = ArrayUtil.copyArray(arr);
int[] arr2 = ArrayUtil.copyArray(arr);
int[] arr3 = ArrayUtil.copyArray(arr);
int[] arr4 = ArrayUtil.copyArray(arr);
System.out.println("随机数组->插入排序 : " + ArrayUtil.testSort(arr, new InsertSort2()) + "s") ;
System.out.println("随机数组->归并排序1 : " + ArrayUtil.testSort(arr1, new MergeSort()) + "s") ;
System.out.println("随机数组->归并排序2 : " + ArrayUtil.testSort(arr2, new MergeSort2()) + "s") ;
System.out.println("随机数组->归并排序3 : " + ArrayUtil.testSort(arr3, new MergeSort3()) + "s") ;
System.out.println("随机数组->自底向上的归并排序 : " + ArrayUtil.testSort(arr4, new MergeSortBU()) + "s") ;
/*
* 生成一个近乎有序的数组
* 100000 : 数组元素个数
* 10 : 在一个完全有序的数组上进行多少次元素交换
*/
arr = ArrayUtil.generateNearlyOrderedArray(100000, 10);
arr1 = ArrayUtil.copyArray(arr);
arr2 = ArrayUtil.copyArray(arr);
arr3 = ArrayUtil.copyArray(arr);
arr4 = ArrayUtil.copyArray(arr);
System.out.println("近乎有序的数组->插入排序:" + ArrayUtil.testSort(arr, new InsertSort2()) + "s") ;
System.out.println("近乎有序的数组->归并排序1:" + ArrayUtil.testSort(arr1, new MergeSort()) + "s") ;
System.out.println("近乎有序的数组->归并排序2:" + ArrayUtil.testSort(arr2, new MergeSort2()) + "s") ;
System.out.println("近乎有序的数组->归并排序3:" + ArrayUtil.testSort(arr3, new MergeSort3()) + "s") ;
System.out.println("近乎有序的数组->自底向上的归并排序:" + ArrayUtil.testSort(arr4, new MergeSortBU()) + "s") ;
}
测试结果 :
随机数组->插入排序 : 2.353s
随机数组->归并排序1 : 0.016s
随机数组->归并排序2 : 0.017s
随机数组->归并排序3 : 0.017s
随机数组->自底向上的归并排序 : 0.015s
近乎有序的数组->插入排序:0.002s
近乎有序的数组->归并排序1:0.007s
近乎有序的数组->归并排序2:0.005s
近乎有序的数组->归并排序3:0.002s
近乎有序的数组->自底向上的归并排序:0.003s
从上面的测试结果来看, 对于随机数组来说, 归并排序的效率是远远高于插入排序的, 对于近乎有序的数组来说, 归并排序的性能也是可观的, 测试结果说明:
- 归并排序1是最初始的归并排序版本
- 归并排序2是底层使用了插入排序的版本
- 归并排序3是在2的基础上加入了判断是否需要进行归并操作的版本