1、核心思想
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 若将两个有序表合并成一个有序表，称为 2-路归并，与之对应的还有多路归并。
对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。
为了提升性能，有时我们在半子表的个数小于某个数（比如 15）的情况下，对半子表的排序采用其他排序算法，比如插入排序。
归并排序图示（降序）：
2、代码示例
输入：int[] array = {22, 28, 15, 15, 21, 3, 11, 2, 25, 28, 28};
输出结果：[2, 3, 11, 15, 15, 21, 22, 25, 28, 28, 28]
通过两种方式实现归并排序：一种使用Fork-Join工具类实现，另一种未使用工具类，通过测试发现，当数据量在百万级甚至千万级的时候使用ForkJoin方式效率更佳。
InsertionSort 类：归并排序通用工具类，满足阈值时使用插入排序算法。
package cn.lspj.ch2.forkjoin.sort;
import java.util.Arrays;
/**
* 类说明：插入排序（升序）
*/
public class InsertionSort {
public static int[] sort(int[] array){
int currentValue; // 当前元素的值
for (int i = 0; i < array.length - 1; i++) {
int prexIndex = i; // 已经排好序的元素位置
currentValue = array[prexIndex + 1]; // 当前元素值（即待排序元素的值）
// 在已经排好序的元素中倒序寻找合适的位子，如果当前待排序元素值比比较元素值小，则将比较的元素往后移以一位
while (prexIndex >= 0 && currentValue < array[prexIndex]) {
// 将比较的元素往后移一位
array[prexIndex + 1] = array[prexIndex];
prexIndex--;
}
// while循环结束时，说明已经找到了当前元素合适的位置，插入即可
array[prexIndex+1] = currentValue;
}
return array;
}
}
- MergeSort 类：归并排序逻辑类
package cn.lspj.ch2.forkjoin.sort;
import java.util.Arrays;
/**
* 类说明：归并排序
*/
public class MergeSort {
private static int[] sort(int[] array){
if(array.length <= 5){ // 设定一个阈值，满足条件使用插入排序
return InsertionSort.sort(array); // 使用插入排序
} else {
// 拆分数组，递归调用
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array,0,mid);
int[] rigth = Arrays.copyOfRange(array,mid,array.length);
return merge(sort(left),sort(rigth));
}
}
/**
* 归并排序：将两个排序好的数组合并成一个数组
* @param left
* @param right
* @return
*/
public static int[] merge(int[] left, int right[]) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if(i >= left.length){ // 表示左边数组已经取值排序完，直接把右边数组值赋值给result即可
result[index] = right[j++];
} else if(j >= right.length){ // 表示右边数组已经取值排序完，直接把左边数组值赋值给result即可
result[index] = left[i++];
} else if(left[i] > right[j]){ // 如果左边数组值大于右边数组值，则将右边数组值赋值给result
result[index] = right[j++];
} else { // 如果右边数组值大于右边数组值，则将左边数组值赋值给result
result[index] = left[i++];
}
}
return result;
}
public static void main(String[] args) {
int[] array = {22, 28, 15, 15, 21, 3, 11, 2, 25, 28, 28};
int[] sort = sort(array);
System.out.println(Arrays.toString(sort));
}
}
执行结果如下：
- ForkJoinSort 类：使用ForkJoin实现归并排序
package cn.lspj.ch2.forkjoin.sort;
import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
/**
* 类说明：使用ForkJoin实现归并排序
*/
public class ForkJoinSort {
private static class FkTask extends RecursiveTask<int[]> {
private final static int THRESHOLD = 5;
private int[] array;
public FkTask(int[] array){
this.array = array;
}
@Override
protected int[] compute() {
if(array.length <= THRESHOLD){
return InsertionSort.sort(array);
} else {
int mid = array.length / 2;
FkTask leftTask = new FkTask(Arrays.copyOfRange(array,0,mid));
FkTask rightTask = new FkTask(Arrays.copyOfRange(array,mid,array.length));
invokeAll(leftTask,rightTask);
return MergeSort.merge(leftTask.join(),rightTask.join());
}
}
public static void main(String[] args) {
int[] array = {22, 28, 15, 15, 21, 3, 11, 2, 25, 28, 28};
// new出池的实例
ForkJoinPool forkJoinPool = new ForkJoinPool();
// new出task的实例
FkTask fkTask = new FkTask(array);
// 调用池的invoke方法
int[] invoke = forkJoinPool.invoke(fkTask);
System.out.println(Arrays.toString(invoke));
}
}
}
执行结果如下：
3、复杂度
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
备注：博主微信公众号，不定期更新文章，欢迎扫码关注。