Java與算法之(11) - 合并排序
來源：程序員人生 發(fā)布時間：2016-11-17 09:08:15 閱讀次數(shù)：2844次
天下事，合久必分，分久必合。合并排序的基本思想正是先分再合。
例如對3, 1這個數(shù)列排序，首先是分，分為3和1兩個數(shù)列，然后再合并并排序。合并需要額外的輔助空間，即建立1個兩個數(shù)列長度之和的空數(shù)組用于存儲合并結(jié)果。
合并分為3步：
1）兩個數(shù)列在起始位置各分配1個"指針"，對照指針位置的數(shù)字，取較小的數(shù)字存入輔助數(shù)組。數(shù)字被移出的1側(cè)，指針右移1格，再次比較兩個指針位置的數(shù)字，直到某1側(cè)的指針移出數(shù)組之外結(jié)束。
2）把左邊數(shù)組剩余的數(shù)字按順序移動到輔助數(shù)組中
3）把右邊數(shù)組剩余的數(shù)字按順序移動到輔助數(shù)組中
進(jìn)程以下圖：
下面把兩個數(shù)組的長度都增加到2，再看1下合并進(jìn)程：
視察1下這個流程可以看出，這類合并排序的條件是左右兩個數(shù)列本身是有序的。所以如果對4, 2, 3, 1排序，拆成4, 2和3, 1兩個數(shù)列明顯是不行的，需要繼續(xù)拆分4, 2為4和2，然后合并為2, 4；拆分右邊為3, 1，然后合并成1, 3。最后合并2, 4和1, 3。
以4, 3, 6, 2, 7, 1, 5為例，完全的排序進(jìn)程以下圖：
來看代碼：
import java.util.Arrays;
/**
* 合并排序法
* Created by autfish on 2016/9/20.
*/
public class MergeSort {
public static void main(String[] args) {
int[] numbers = new int[] {4, 3, 6, 2, 7, 1, 5};
System.out.println("排序前: " + Arrays.toString(numbers));
MergeSort ms = new MergeSort();
ms.sort(numbers, 0, numbers.length - 1);
System.out.println("排序后: " + Arrays.toString(numbers));
}
public void sort(int[] numbers, int from, int to) {
int middle = (from + to) / 2;
if (from < to) {
sort(numbers, from, middle);
sort(numbers, middle + 1, to);
//左邊數(shù)列最大值小于右邊數(shù)列最小值, 不需要通過合并來調(diào)劑順序
if(numbers[middle] < numbers[middle + 1])
return;
merge(numbers, from, middle, to);
}
}
private void merge(int[] numbers, int from, int middle, int to) {
int[] temp = new int[to - from + 1];
int left = from;
int right = middle + 1;
int i = 0;
//從拆分到兩邊數(shù)列各剩1個數(shù)字開始合并; 當(dāng)數(shù)列中有多個數(shù)字時, 1定是已排好序的
//從兩邊數(shù)列左邊開始順次取數(shù)對照, 挑選小的1個放入臨時數(shù)組
while (left <= middle && right <= to) {
if (numbers[left] < numbers[right]) {
temp[i++] = numbers[left++];
} else {
temp[i++] = numbers[right++];
}
}
//把左側(cè)數(shù)列剩余的數(shù)移入數(shù)組
while (left <= middle) {
temp[i++] = numbers[left++];
}
//把右側(cè)數(shù)列剩余的數(shù)移入數(shù)組
while (right <= to) {
temp[i++] = numbers[right++];
}
System.arraycopy(temp, 0, numbers, from, temp.length);
}
}
運行：
排序前: [4, 3, 6, 2, 7, 1, 5]
排序后: [1, 2, 3, 4, 5, 6, 7]
合并排序平均情況和最壞情況的時間復(fù)雜度都是O(nlogn)，由于需要額外的輔助空間，空間復(fù)雜度為O(n)。
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進(jìn)行捐贈
