ETH官方钱包

切換
舊版
前往
大廳
主題

高效排序法之一 合併排序(Merge Sort)

魔化鬼鬼 | 2020-07-07 21:15:59 | 巴幣 1002 | 人氣 409

這次要來介紹的是稍微複雜一點的排序法,相比於前面提到的泡沫排序、選擇排序、插入排序,他的效率好非常多( O(nlogn) )—Merge sort,中文叫合併排序。這個排序法用了一種做法叫「分而治之」(Divide And Conquer),那什麼叫分而治之?

岔個題,其實這個概念不只是程式上的概念,他在各式各樣的行業(yè)都非常適用,當(dāng)你遇到一個很困難的問題時,你可能沒辦法馬上解決,這時的你就可以嘗試把問題一一分解,如果還是很難,那就再分解,分解到你覺得你可以解決時,把他一一擊破,在你解決小問題時,也間接了解決大問題。

回到主題,其實從名字上也可以看出端倪,其運作原理就是把陣列的元素切成一個一個的,再來兩個元素比較後排列,形成長度2的陣列,再來用兩個長度2的陣列排列,形成長度4的陣列,一直這樣比較排序,最後組織成完整的陣列。

例如這樣:
(如果是第一次聽到這個的,請先不要想程式碼的實做,看懂概念比較重要,所以我下面的例子我盡量不會提到程式碼的部分)

array[10] = {8,5,1,3,8,6,4,7,1,10}
假設(shè)我們目標(biāo)是要由小排到大
也就是最後要變{1,1,3,4,5,6,7,8,8,10}

第一步就照我說的「把陣列的元素切成一個一個的」
接著開始兩兩比較、排序、合併
第一輪如下


再來第二輪


再來第三輪


再來第四輪

這樣就完成排序了!

我相信理解這個絕對不難,最困擾各位的絕對是程式碼要怎麼實做。一般來說,合併排序主要是利用遞迴的方式,一直把自己對半切,切到不能再切為止,接著開始return ,然後再合併排序。

關(guān)鍵是這個合併排序的部分要怎麼寫,我們先想想流程,在合併之前,我們有兩坨「已排序的」陣列,為什麼說已排序的,各位可以往上看那個例子觀察看看。此時的我們可以作兩個指針,我們只要把兩個指針指到的數(shù)字比較,然後把結(jié)果放到另一個陣列就好。

以下開始程式碼的概念(用電腦版看比較好)

拿上面的例子來舉
宣告兩個整數(shù)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}
        ^                 ^
...
...
...略

最後暫存陣列就是我們這個合併排序的結(jié)果了


下面是我用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];
    }


}


創(chuàng)作回應(yīng)

鄧董
你好,想請問一下是如何把code embed進(jìn)文章中的?
2020-09-20 03:24:06
魔化鬼鬼
外框的部分是用1*1的表格 至於顏色大小那些.. 我是從intelliJ ide 裡copy出來 然後paste上去就有這些顏色了
2020-09-20 08:43:08
鄧董
感謝,這樣看起來還以為巴哈有支援貼code哈哈
2020-09-20 10:30:00
???\~O_O~/???
那個...圖片的切法跟程式碼好像不太一樣
圖片是bottom-up合併
(tempArr.length=2,tempArr.length=4,tempArr.length=8,...)
程式碼是top-down切
(tempArr.length=arr.length/2,tempArr.length=arr.length/4,tempArr.length=arr.length/8,...)
2020-11-29 08:40:21
魔化鬼鬼
你沒這麼說,我還沒發(fā)現(xiàn)呢!切法好像真的有錯,不過merge概念應(yīng)該還是差不多啦[e12]
2020-11-29 09:57:16

相關(guān)創(chuàng)作

更多創(chuàng)作