一.兩個(gè)有序數(shù)組的排順
如果有兩個(gè)有序的數(shù)組合并為一個(gè)有序數(shù)組巾陕，我們可以用下面的代碼實(shí)現(xiàn)：
public void merge(int[] a, int[] b, int[] c){
int i=0,j=0,k=0;
while (i<a.length && j<b.length){
if (a[i]<=b[j]){
c[k++]=a[i++];
} else{
c[k++]=b[j++];
}
}
while (i<a.length){
c[k++]=a[i++];
}
while (j<b.length){
c[k++]=b[j++];
}
其中數(shù)組a,b為我們已經(jīng)排好序的兩個(gè)升序數(shù)組，c為我們新建的一個(gè)長(zhǎng)度為a,b兩數(shù)組相加的一個(gè)空數(shù)組。
??我們用一組測(cè)試用例來(lái)測(cè)試上述算法，并加上log使之更加清晰：
public class TwoListSort {
public static void main(String args[]){
int[] a = {2,6,11 }; //聲明數(shù)組
int[] b = {8,9,9,15};
int[] c = new int[7];
merge(a,b,c);
}
public static void merge(int[] a, int[] b, int[] c){
int i=0,j=0,k=0;
while (i<a.length && j<b.length){
if (a[i]<=b[j]){
c[k++]=a[i++];
test(c,i,j,k);
} else{
c[k++]=b[j++];
test(c,i,j,k);
}
}
while (i<a.length){
c[k++]=a[i++];
test(c,i,j,k);
}
while (j<b.length){
c[k++]=b[j++];
test(c,i,j,k);
}
}
public static void test(int[] c, int i, int j, int k){
for(int h = 0; h < c.length ; h++) {
System.out.print( c[h] + "," );
}
System.out.print( " "+ " i = "+i +", "+" j = "+j +", "+" k = "+k );
System.out.println("");
}
}
log輸出為：
2,0,0,0,0,0,0, i = 1, j = 0, k = 1
2,6,0,0,0,0,0, i = 2, j = 0, k = 2
2,6,8,0,0,0,0, i = 2, j = 1, k = 3
2,6,8,9,0,0,0, i = 2, j = 2, k = 4
2,6,8,9,9,0,0, i = 2, j = 3, k = 5
2,6,8,9,9,11,0, i = 3, j = 3, k = 6
2,6,8,9,9,11,15, i = 3, j = 4, k = 7
我們對(duì)照l(shuí)og來(lái)分析一下上述過(guò)程:
初始：i=0，j=0,k=0;
a[0]<b[0]
c[0] = a[0] = 2;
c = 2,0,0,0,0,0,0, i = 1, j = 0, k = 1
a[1]<b[0]
c[1] = a[1] = 6;
c = 2,6,0,0,0,0,0, i = 2, j = 0, k = 2
a[2]>b[0]
c[2] = b[0] = 8;
c = 2,6,8,0,0,0,0, i = 2, j = 1, k = 3
a[2]>b[1]
c[3] = b[1] = 9;
c = 2,6,8,9,0,0,0, i = 2, j = 2, k = 4
a[2]>b[2]
c[4] = b[2] = 9;
c = 2,6,8,9,9,0,0, i = 2, j = 3, k = 5
a[2]<b[3]
c[5] = a[2] = 11;
c = 2,6,8,9,9,11,0, i = 3, j = 3, k = 6
此時(shí)拟赊，不滿足while (i<a.length && j<b.length){這個(gè)條件，跳出最上面的循環(huán)粹淋，進(jìn)入下面的循環(huán)中：
while (j<b.length){
c[k++]=b[j++];
test(c,i,j,k);
}
c[6] = b[3] = 15
c = 2,6,8,9,9,11,15, i = 3, j = 4, k = 7
上面算法設(shè)置的非常巧妙吸祟，大家可以多測(cè)試幾組用例，針對(duì)不同情況做出分析桃移。
二.無(wú)序數(shù)組的排序
現(xiàn)在假設(shè)有一個(gè)無(wú)序數(shù)組需要排序屋匕，但是可以人為的通過(guò)一定操作劃分為兩個(gè)有序的數(shù)組A和B，那么我們借助上述算法可以很快的將A和B兩個(gè)有序的子數(shù)組進(jìn)行歸并排序借杰。
??現(xiàn)在有一個(gè)無(wú)序數(shù)組需要排序过吻，并且他是完全無(wú)序的，不能劃分為任何有序數(shù)組蔗衡，這個(gè)時(shí)候需要怎么排序呢纤虽？這個(gè)問(wèn)題可以轉(zhuǎn)換為，上一種情況中绞惦，A和B兩個(gè)子數(shù)組也是無(wú)序的逼纸，那么我們可以繼續(xù)將A和B兩個(gè)數(shù)組拆分下去，拆成更小的子數(shù)組：a1,a2和b1,b2...如此下去翩隧，我們一直將子數(shù)組拆分到最小元素樊展，即一個(gè)子數(shù)組只有一個(gè)元素（也就是拆分成一個(gè)個(gè)元素呻纹，每個(gè)元素視為長(zhǎng)度為1的數(shù)組）堆生，那么這一個(gè)個(gè)長(zhǎng)度為1的數(shù)組，就可以視為有序數(shù)組了(畢竟他只有一個(gè)元素)雷酪。
??那么此時(shí)我們可以兩個(gè)元素淑仆，視為“一.兩個(gè)有序數(shù)組的排順”情況中的A.B兩個(gè)數(shù)組，然后兩兩合并哥力，知道合并為最初長(zhǎng)度的數(shù)組蔗怠，可以看到，這實(shí)際上是一個(gè)遞歸的過(guò)程吩跋。
看到這里不理解的話沒(méi)關(guān)系寞射，我們會(huì)在代碼中帶大家一步步分析：
public class MergeSort {
public static void main(String args[]){
int[] nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2 }; //聲明數(shù)組
mergeSort(nums);
}
//歸并排序
public static void mergeSort(int[] arr){
int[] temp =new int[arr.length] ;
internalMergeSort(arr, temp, 0, arr.length-1);
}
private static void internalMergeSort(int[] a, int[] b, int left, int right){
if (left<right){ //當(dāng)left==right的時(shí)，已經(jīng)不需要再劃分了
int middle = (left+right)/2;
internalMergeSort(a, b, left, middle); //左子數(shù)組
internalMergeSort(a, b, middle+1, right); //右子數(shù)組
mergeSortedArray(a, b, left, middle, right); //合并兩個(gè)子數(shù)組
}
}
// 合并兩個(gè)有序子序列 arr[left, ..., middle] 和 arr[middle+1, ..., right]锌钮。temp是輔助數(shù)組桥温。
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
int i=left;
int j=middle+1;
int k=0;
while ( i<=middle && j<=right){ // 逐個(gè)歸并
if (arr[i] <=arr[j]){
temp[k++] = arr[i++];
} else{
temp[k++] = arr[j++];
}
}
while (i <=middle){ // 將左邊剩余的歸并
temp[k++] = arr[i++];
}
while ( j<=right){ // 將右邊剩余的歸并
temp[k++] = arr[j++];
}
for (i=0; i<k; ++i){ //把數(shù)據(jù)復(fù)制回原數(shù)組
arr[left+i] = temp[i];
}
}
}
上面展示的就是一個(gè)歸并排序的過(guò)程，internalMergeSort(int[] a, int[] b, int left, int right)該方法就是拆分?jǐn)?shù)組為一個(gè)個(gè)最小子元素的方法梁丘，可以看到該方法中動(dòng)用了遞歸調(diào)用侵浸；mergeSortedArray(int arr[], int temp[], int left, int middle, int right)則是“一.兩個(gè)有序數(shù)組的排順”情況中將兩個(gè)有序數(shù)組排序的算法旺韭，也就是歸并方法：
我們給上述兩個(gè)方法加上必要的log：
private static void internalMergeSort(int[] a, int[] b, int left, int right){
//當(dāng)left==right的時(shí)，已經(jīng)不需要再劃分了
if (left<right){
int middle = (left+right)/2;
System.out.println("");
System.out.println( "(left左 , middle左掏觉，right左) = " + " (" + left + "," + middle + "," + right + ") " );
for(int i = left; i < right +1; i++) {
System.out.print(a[i] + ",");
}
internalMergeSort(a, b, left, middle); //左子數(shù)組
System.out.println("");
System.out.println( "(left右 , middle右区端，right右) = " + " (" + left + "," + (middle+1) + "," + right + ") " );
for(int i = middle+1; i < right +1; i++) {
System.out.print(a[i] + ",");
}
internalMergeSort(a, b, middle+1, right); //右子數(shù)組
mergeSortedArray(a, b, left, middle, right); //合并兩個(gè)子數(shù)組
}
}
private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){
System.out.println("");
System.out.println( "(left合并 , middle合并，right合并) = " + " (" + left + "," + middle + "," + right + ") " );
System.out.print("排序前：");
for(int h = left; h < right +1; h++) {
System.out.print( arr[h] + ",");
}
int i=left;
int j=middle+1;
int k=0;
while ( i<=middle && j<=right){ // 逐個(gè)歸并
if (arr[i] <=arr[j]){
temp[k++] = arr[i++];
} else{
temp[k++] = arr[j++];
}
}
while (i <=middle){ // 將左邊剩余的歸并
temp[k++] = arr[i++];
}
while ( j<=right){ // 將右邊剩余的歸并
temp[k++] = arr[j++];
}
for (i=0; i<k; ++i){ //把數(shù)據(jù)復(fù)制回原數(shù)組
arr[left+i] = temp[i];
}
System.out.println("");
System.out.print("排序后：");
for(int h = left; h < right +1; h++) {
System.out.print( arr[h] + ",");
}
}
由于運(yùn)行的結(jié)果比較長(zhǎng)澳腹，我們將在下面的分析中逐步分開(kāi)講解：
下面我們來(lái)分析一遍上面的結(jié)果——首先是第一部分：
(left左 , middle左织盼，right左) = (0,5,10)
27,8,57,9,23,41,65,19,0,1,2,
(left左 , middle左，right左) = (0,2,5)
27,8,57,9,23,41,
(left左 , middle左酱塔，right左) = (0,1,2)
27,8,57,
(left左 , middle左悔政，right左) = (0,0,1)
27,8,
(left右 , middle右，right右) = (0,1,1)
8,
(left合并 , middle合并延旧，right合并) = (0,0,1)
排序前：27,8,
排序后：8,27,
這個(gè)部分的log代表的過(guò)程圖示如下谋国，即第一次循環(huán)遍歷到左子樹(shù)的最底層，開(kāi)始向上歸并一層迁沫，歸并的過(guò)程伴隨著排序：
歸并后的結(jié)果為8,27,然后向上遞歸調(diào)用芦瘾，再歸并一層：
(left右 , middle右，right右) = (0,2,2)
57,
(left合并 , middle合并集畅，right合并) = (0,1,2)
排序前：8,27,57,
排序后：8,27,57,
接著歸并第三層：
(left右 , middle右近弟，right右) = (0,3,5)
9,23,41,
(left左 , middle左，right左) = (3,4,5)
9,23,41,
(left左 , middle左挺智，right左) = (3,3,4)
9,23,
(left右 , middle右祷愉，right右) = (3,4,4)
23,
(left合并 , middle合并，right合并) = (3,3,4)
排序前：9,23,
排序后：9,23,
(left右 , middle右赦颇，right右) = (3,5,5)
41,
(left合并 , middle合并二鳄，right合并) = (3,4,5)
排序前：9,23,41,
排序后：9,23,41,
(left合并 , middle合并，right合并) = (0,2,5)
排序前：8,27,57,9,23,41,
排序后：8,9,23,27,41,57,
這一步就是合并8,27,57和9,23,41這兩個(gè)有序子數(shù)組媒怯，畢竟這兩個(gè)子數(shù)組的底層已經(jīng)遞歸調(diào)用完了订讼，然后合并的過(guò)程中伴隨著排序，最終得到第二層有序的左子數(shù)組：8,9,23,27,41,57,
接著是同樣的遞歸合并第二層右子數(shù)組：
(left右 , middle右扇苞，right右) = (0,6,10)
65,19,0,1,2,
(left左 , middle左欺殿，right左) = (6,8,10)
65,19,0,1,2,
(left左 , middle左，right左) = (6,7,8)
65,19,0,
(left左 , middle左鳖敷，right左) = (6,6,7)
65,19,
(left右 , middle右脖苏，right右) = (6,7,7)
19,
(left合并 , middle合并，right合并) = (6,6,7)
排序前：65,19,
排序后：19,65,
(left右 , middle右定踱，right右) = (6,8,8)
0,
(left合并 , middle合并棍潘，right合并) = (6,7,8)
排序前：19,65,0,
排序后：0,19,65,
(left右 , middle右，right右) = (6,9,10)
1,2,
(left左 , middle左，right左) = (9,9,10)
1,2,
(left右 , middle右蜒谤，right右) = (9,10,10)
2,
(left合并 , middle合并山宾，right合并) = (9,9,10)
排序前：1,2,
排序后：1,2,
(left合并 , middle合并，right合并) = (6,8,10)
排序前：0,19,65,1,2,
排序后：0,1,2,19,65,
最后是歸并第二層已經(jīng)拍好隊(duì)的兩個(gè)有序子數(shù)組：8,9,23,27,41,57,和0,1,2,19,65,鳍徽，最終得到有序的原數(shù)組：
(left合并 , middle合并资锰，right合并) = (0,5,10)
排序前：8,9,23,27,41,57,0,1,2,19,65,
排序后：0,1,2,8,9,19,23,27,41,57,65,
