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)
備注：部落客微信公衆号，不定期更新文章，歡迎掃碼關注。