歸并排序
- 原理：
- 分解：
- 合并：
- 非遞回：
原理：
歸并排序（mergeSort）是建立在歸并操作上的一種有效的排序演算法，該演算法采用分治法，將以有序的子序列合并，得到一個完全有序的序列，即：先使得每個子序列有序，再使得子序列段間有序，如果將兩個有序表合成一個有序表，稱為：二路歸并，
我們采用二路歸并如圖演示：
分解的程序，我們可以借助遞回，不停的往下分解，直到只有一個元素分解完成，
合并的程序，就是我們合并兩個有序的陣列，我們主要是比較兩個元素，小的先放，然后放較大的元素，
分解：
public static void mergeSort(long[] array) {
mergeSortRange(array, 0, array.length);
}
private static void mergeSortRange(long[] array, int from, int to) {
if (to - from <= 1) {
return;
}
int mid = (to + from) / 2;
mergeSortRange(array, from, mid);
mergeSortRange(array, 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;
int k2 = mid;
int k3 = 0;
while (k1 < mid && k2 < to) {
if (array[k1] <= array[k2]) {
array2[k3++] = array[k1++];
} else {
array2[k3++] = array[k2++];
}
}
while (k1 < mid) {
array2[k3++] = array[k1++];
}
while (k2 < to) {
array2[k3++] = array[k2++];
}
for (int i = 0; i < size; i++) {
array[from + i] = array2[i];
}
}
非遞回：
public static void mergeSort(long[] array) {
for (int i = 1; i < array.length; i = i * 2) {
for (int j = 0; j < array.length; j = j + 2 * i) {
int low = j;
int mid = j + i;
if (mid >= array.length) {
continue;
}
int high = mid + i;
if (high > array.length) {
high = array.length;
}
merge(array, low, mid, high);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/273618.html
標籤：其他