歸并排序是創(chuàng)建在歸并操作上的一種有效的排序算法掉弛，效率為O(nlogn)症见，1945年由馮·諾伊曼首次提出。
歸并排序的實現(xiàn)分為遞歸實現(xiàn)與非遞歸(迭代)實現(xiàn)殃饿。遞歸實現(xiàn)的歸并排序是算法設(shè)計中分治策略的典型應(yīng)用谋作，我們將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題乎芳。非遞歸(迭代)實現(xiàn)的歸并排序首先進(jìn)行是兩兩歸并遵蚜，然后四四歸并，然后是八八歸并奈惑，一直下去直到歸并了整個數(shù)組吭净。
歸并排序算法主要依賴歸并(Merge)操作。歸并操作指的是將兩個已經(jīng)排序的序列合并成一個序列的操作,歸并操作步驟如下：
申請空間肴甸，使其大小為兩個已經(jīng)排序序列之和寂殉，該空間用來存放合并后的序列
設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
比較兩個指針?biāo)赶虻脑卦冢x擇相對小的元素放入到合并空間友扰，并移動指針到下一位置
重復(fù)步驟3直到某一指針到達(dá)序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾
將兩個（或兩個以上）有序表合并成一個新的有序表 即把待排序序列分為若干個子序列，每個子序列是有序的庶柿。然后再把有序子序列合并為整體有序序列
public class MergeSort {
/**
* 歸并排序
* 簡介:將兩個（或兩個以上）有序表合并成一個新的有序表 即把待排序序列分為若干個子序列村怪，每個子序列是有序的。然后再把有序子序列合并為整體有序序列
* 時間復(fù)雜度為O(nlogn)
* 穩(wěn)定排序方式
* @param nums 待排序數(shù)組
* @return 輸出有序數(shù)組
*/
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左邊
sort(nums, low, mid);
// 右邊
sort(nums, mid + 1, high);
// 左右歸并
merge(nums, low, mid, high);
}
return nums;
}
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指針
int j = mid + 1;// 右指針
int k = 0;
// 把較小的數(shù)先移到新數(shù)組中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左邊剩余的數(shù)移入數(shù)組
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右邊邊剩余的數(shù)移入數(shù)組
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新數(shù)組中的數(shù)覆蓋nums數(shù)組
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
// 歸并排序的實現(xiàn)
public static void main(String[] args) {
int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };
MergeSort.sort(nums, 0, nums.length-1);
System.out.println(Arrays.toString(nums));
}
}
739525-20160328211504519-1388466622.gif
