這次要來介紹的是稍微複雜一點的排序法，相比於前面提到的泡沫排序、選擇排序、插入排序，他的效率好非常多( O(nlogn) )—Merge sort，中文叫合併排序。這個排序法用了一種做法叫「分而治之」(Divide And Conquer)，那什麼叫分而治之？
岔個題，其實這個概念不只是程式上的概念，他在各式各樣的行業都非常適用，當你遇到一個很困難的問題時，你可能沒辦法馬上解決，這時的你就可以嘗試把問題一一分解，如果還是很難，那就再分解，分解到你覺得你可以解決時，把他一一擊破，在你解決小問題時，也間接了解決大問題。
回到主題，其實從名字上也可以看出端倪，其運作原理就是把陣列的元素切成一個一個的，再來兩個元素比較後排列，形成長度2的陣列，再來用兩個長度2的陣列排列，形成長度4的陣列，一直這樣比較排序，最後組織成完整的陣列。
例如這樣:
(如果是第一次聽到這個的，請先不要想程式碼的實做，看懂概念比較重要，所以我下面的例子我盡量不會提到程式碼的部分)
array[10] = {8,5,1,3,8,6,4,7,1,10}
假設我們目標是要由小排到大
也就是最後要變{1,1,3,4,5,6,7,8,8,10}
第一步就照我說的「把陣列的元素切成一個一個的」
接著開始兩兩比較、排序、合併
第一輪如下
再來第二輪
再來第三輪
再來第四輪
這樣就完成排序了!
我相信理解這個絕對不難，最困擾各位的絕對是程式碼要怎麼實做。一般來說，合併排序主要是利用遞迴的方式，一直把自己對半切，切到不能再切為止，接著開始return ，然後再合併排序。
關鍵是這個合併排序的部分要怎麼寫，我們先想想流程，在合併之前，我們有兩坨「已排序的」陣列，為什麼說已排序的，各位可以往上看那個例子觀察看看。此時的我們可以作兩個指針，我們只要把兩個指針指到的數字比較，然後把結果放到另一個陣列就好。
以下開始程式碼的概念(用電腦版看比較好)
拿上面的例子來舉
宣告兩個整數leftIndex, rightIndex，分別存取左陣列和右陣列的索引值
{1,3,5,8} {4,6,7,8}
^ ^
比較arr[leftIndex]和arr[rightIndex]的值
在這個例子裡是1跟4比
1<4
所以把1新增到暫存的陣列裡面
同時leftIndex++
{1,3,5,8} {4,6,7,8}
^ ^
3<4
3新增到暫存陣列
leftIndex++
{1,3,5,8} {4,6,7,8}
^ ^
4<5
4新增到暫存陣列
rightIndex++
{1,3,5,8} {4,6,7,8}
^ ^
...
...
...略
最後暫存陣列就是我們這個合併排序的結果了
下面是我用Java寫的code 簡單參考就好 測試的時候有出錯幾次 但找不出原因
| public static void mergeSort(int[] arr, int beginI, int endI){ if(beginI >= endI){ // recursion stop condition return; } mergeSort(arr, beginI, (endI+beginI)/2); // sorts left side of the array mergeSort(arr, ((endI+beginI)/2)+1, endI); // sorts right side of the array int[] tempArr = new int[endI-beginI+1]; // stores the sorted array temporarily int leftIndex = beginI; // the left array's index int rightIndex = ((endI+beginI)/2)+1; // the right array's index int i = 0; // the tempArr's index while(i <= endI-beginI){ if(leftIndex == ((endI+beginI)/2)+1 || (rightIndex != endI+1 && arr[rightIndex] <= arr[leftIndex])){ tempArr[i] = arr[rightIndex]; rightIndex++; } else{ tempArr[i] = arr[leftIndex]; leftIndex++; } i++; } for(int j = beginI;j<=endI;j++){ // overwrite the original array arr[j] = tempArr[j-beginI]; } } |
達人
