-
merge
（歸併排序算法）
鎖定
merge是建立在歸併操作上的一種有效的排序算法。它將多個排序列表作為輸入並生成單個列表作為輸出，包含按排序順序排列的輸入列表的所有元素。
- 中文名
- 歸併排序算法
- 外文名
- merge
- 別 名
- 歸併算法
- 性 質
- 一種有效的排序算法
merge簡介
將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。
merge歸併操作
歸併操作(merge)，也叫歸併算法，指的是將兩個已經排序的序列合併成一個序列的操作。
如 設有數列{6，202，100，301，38，8，1}
初始狀態： [6] [202] [100] [301] [38] [8] [1] 比較次數
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3
i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4
i=3 [ 1 6 8 38 100 202 301 ] 4
總計： 11次代碼
merge代碼
package sort;
import static sort.SortUtils.print;
/**
* 此方法實現通用歸併排序
*/
class MergeSort implements SortAlgorithm {
/**
* 此方法實現通用歸併排序
* @param unsorted [array] 要進行排序的數組
* @param <T> Comparable class
* @return sorted array
*/
public <T extends Comparable<T>> T[] sort(T[] unsorted) {
T[] tmp = (T[]) new Comparable[unsorted.length];
doSort(unsorted, tmp, 0, unsorted.length - 1);
return unsorted;
}
/**
* @param arr 將要進行排序的數組
* @param temp 實際數據的副本
* @param left 數組的第一個索引
* @param right 數組的最後一個索引
* 按遞增順序對數組進行遞歸排序
**/
private static <T extends Comparable<T>> void doSort(T[] arr, T[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
doSort(arr, temp, left, mid);
doSort(arr, temp,mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
/**
* 此方法實現歸併排序的歸併步驟
*
* @param arr 將要進行排序的數組
* @param temp 實際數據的副本
* @param left 數組的第一個索引
* @param mid 數組的中間索引
* @param right 數組的最後一個索引
* 按遞增順序歸併數組的兩部分
**/
private static <T extends Comparable<T>> void merge(T[] arr, T[] temp, int left, int mid, int right) {
System.arraycopy(arr, left, temp, left, right - left + 1);
int i= left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (temp[i].compareTo(temp[j]) <= 0) {
arr[k] = temp[i];
i++;
}
else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}
while (j <= right) {
arr[k] = temp[j];
j++;
k++;
}
}
public static void main(String[] args) {
// Integer Input
Integer[] arr = {4, 23, 6, 78, 1, 54, 231, 9, 12};
MergeSort mergeSort = new MergeSort();
mergeSort.sort(arr);
// Output => 1 4 6 9 12 23 54 78 231
print(arr);
// String Inpu
String[] stringArray = {"c", "a", "e", "b","d"};
mergeSort.sort(stringArray);
//Output => a b c d e
print(stringArray);
}
}
