歸并排序是分治演算法一個非常典型的例子，歸并排序的思想是將待排序序列遞回分為左右兩個子序列，遞回到子序列只有一個數的時候，停下來，這就是分治演算法的分的意思，將問題化簡，當子序列只有一個元素的時候是不是可以認為這個序列為有序序列了，然后再將左右有序子序列通過遞回合并起來，最終讓整個序列有序，這是分治演算法治的程序，下面我們通過圖片來理解這個程序：
通過動圖理解就是：
線面看代碼：
public class MergeSort {
public static void mergeSort(long[] array) {
mergeSortRange(array, 0, array.length);
}
// [from, to)
private static void mergeSortRange(long[] array, int from, int to) {
int size = to - from;
if (size <= 1) {
return;
}
//int mid = (from + to) / 2;
int mid = from + (to - from) / 2;
// 左半邊: [from, mid)
// 右半邊: [mid, to)
// 先讓左右區間各自有序
mergeSortRange(array, from, mid);
mergeSortRange(array, mid, to);
// 合并兩個有序區間 [from, mid) [mid, to)
merge(array, from, mid, to);
}
private static void merge(long[] array, int from, int mid, int to) {
// 需要額外空間，需要兩個區間的大小之和
int size = to - from;
long[] array2 = new long[size];
int k1 = from; // array
int k2 = mid; // array
int k3 = 0; // array2
while (k1 < mid && k2 < to) {
if (array[k1] <= array[k2]) { // 加等號是為了保證穩定性
array2[k3++] = array[k1++];
} else {
array2[k3++] = array[k2++];
}
}
// 有一個區間內的元素全部取完了
if (k1 < mid) {
// 左邊區間還有元素
while (k1 < mid) {
array2[k3++] = array[k1++];
}
} else {
// 右邊區間還有元素
while (k2 < to) {
array2[k3++] = array[k2++];
}
}
// 我們還需要把資料搬回原陣列中
for (int i = 0; i < size; i++) {
array[from + i] = array2[i];
}
}
}
歸并排序的說簡單也很簡單，說難他不好理解的點就是將待排序序列一直分解到只含一個資料的子序列然后在依次合并這個遞回操作上，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/297879.html
標籤：其他
上一篇：C經典書籍筆記——C陷阱與缺陷②(語法陷阱之優先級)
下一篇：關于MVVM和MVC架構模式