概述
如果一個數(shù)組有n個數(shù)據(jù)厢塘，則可以把這個數(shù)組看作n個有序的子序列，每個子序列的長度為1肌幽，然后兩兩歸并晚碾，就能得到[n/2]個長度為2或1的子序列，再不斷地兩兩歸并喂急，直到得到一個長度為n的有序數(shù)組格嘁。
這種排序方法稱為2路歸并排序
遞歸，java實現(xiàn)
public class MergeSort {
public static void main(String[] args) {
int[] array = {98, 21, 62, 48, 33, 6, 55, 17};
System.out.print("MergeSort\n");
printArray(array);
System.out.print("start:\n");
mergeSort(array, 0, array.length - 1);
System.out.print("end:\n");
}
static void mergeSort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
static void merge(int[] arr, int low, int mid, int high) {
//temp數(shù)組用于暫存合并的結(jié)果
int[] temp = new int[high - low + 1];
//左半邊的指針
int i = low;
//右半邊的指針
int j = mid+1;
//合并后數(shù)組的指針
int k = 0;
//將記錄由小到大地放進temp數(shù)組
for(; i <= mid && j <= high; k++)
{
if(arr[i] < arr[j])
temp[k] = arr[i++];
else
temp[k] = arr[j++];
}
//接下來兩個while循環(huán)是為了將剩余的（比另一邊多出來的個數(shù)）放到temp數(shù)組中
while(i <= mid)
temp[k++] = arr[i++];
while(j <= high)
temp[k++] = arr[j++];
//將temp數(shù)組中的元素寫入到待排數(shù)組中
for(int l = 0; l < temp.length; l++)
arr[low + l] = temp[l];
printArray(arr);
}
static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("\n");
}
}
排序效果
MergeSort
98 21 62 48 33 6 55 17
start:
21 98 62 48 33 6 55 17
21 98 48 62 33 6 55 17
21 48 62 98 33 6 55 17
21 48 62 98 6 33 55 17
21 48 62 98 6 33 17 55
21 48 62 98 6 17 33 55
6 17 21 33 48 55 62 98
end:
復(fù)雜度
時間復(fù)雜度: O(nlogn)
空間復(fù)雜度: O(n+nlogn)
