歸并排序( Merging Sort) 就是利用歸并的思想實(shí)現(xiàn)的排序方法牵寺。它的原理是假設(shè)初始序列含有n 個(gè)記錄畔派， 則可以看成是n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1然后兩兩歸并，得到【n/2】個(gè)長(zhǎng)度為2或1 的有序子序列; 再兩兩歸并解藻，……，如此重復(fù)咐容， 直至得到一個(gè)長(zhǎng)度為n 的有序序列為止舆逃，這種排序方法稱(chēng)為2 路歸并排序。
圖片.png
public static void main(String[] args) {
int[] array = {14, 12, 13, 5, 1, 7, 9};
sort(array, 0, array.length-1);
for (int i=0; i< array.length; i++) {
System.out.print(array[i] + ", ");
}
}
private static void sort(int[] array, int left, int right) {
if (left < right) {
int mid = (left + right)/2;
//分割
sort(array, left, mid);
sort(array, mid+1, right);
//歸并
merge(array, left, mid, right);
}
}
private static void merge (int[] array, int left, int mid, int right) {
//new一個(gè)臨時(shí)存儲(chǔ)空間
int[] temp = new int[right-left+1];
int p1=left;
int p2= mid+1;
int k=0;
//把較小的數(shù)移到新數(shù)組中
while (p1<=mid && p2<=right) {
if(array[p1]<array[p2]) {
temp[k] = array[p1];
k++;
p1++;
} else {
temp[k] = array[p2];
k++;
p2++;
}
}
//把剩余的數(shù)直接移到新數(shù)組中
while (p1<=mid) {
temp[k] = array[p1];
k++;
p1++;
}
while (p2<=right) {
temp[k] = array[p2];
k++;
p2++;
}
//把新數(shù)組覆蓋array數(shù)組
for (int i=0; i<temp.length; i++) {
array[i+left] = temp[i];
}
}
