iT邦幫忙

1

【小馬的資結演算法秘笈】(2)合併排序法- mergeSort

續上一篇【小馬的資結演算法秘笈】(1)二分搜索法(Binary Search)
我們知道若是在一個有排序過的陣列中找東西是較簡單的,
所以今天就要來教這個經典的問題- 排序

我們希望把一個陣列上的數字,
由小到大排序好,
具體做法是「將大問題切割成小問題」的想法

Divide and Conquer -分而治之法

假設我們有陣列數字是1,5,6,3,2,8,10,7
https://ithelp.ithome.com.tw/upload/images/20200312/201171149nWlVq75fB.png

但是原本的問題很大,
我們便想說能不能把問題變小,
先只排序一半就好了,
於是我們把陣列切成左右兩半,

https://ithelp.ithome.com.tw/upload/images/20200312/201171145kkUwcapFR.png

然後切成兩半各自排序:

https://ithelp.ithome.com.tw/upload/images/20200312/201171146SOCtxzcfa.png

然後再嘗試把各自排好的陣列合併起來,
底下我們會細講具體該怎麼做

一、合併(merge)- 把兩個排序的陣列合為一個

我們發現,如果左半邊的陣列和右半邊的陣列都各自排序好的話,
那麼對於排序整個陣列是很有幫助的
我們可以每次都把兩個陣列中最小的數字抓出來放到新的陣列中,
譬如一開始,12比較,
1比較小抓出來放到陣列中,
然後換下一個數字3出來比較

https://ithelp.ithome.com.tw/upload/images/20200312/20117114RviTpYTlOA.png

接著我們比較322比較小,
2抓出來放到陣列中,…
以此類推,
https://ithelp.ithome.com.tw/upload/images/20200312/201171144kG5HOZWWG.png

直到左右兩陣列的數都用完,排序就完成了
我們可以這樣定義merge函數:

//結合兩陣列排序好的結果,
//左陣列為arr[l..m],右陣列為 arr[m+1..r]
void merge(int* arr, int left, int medium, int right)
{
    int lnum = medium-left+1, rnum=right-medium;
    int larr[lnum], rarr[rnum]; //這邊先將原陣列複製一份放到larr, rarr兩個陣列中
    for(int i=0; i<lnum;i++){
        larr[i]=arr[left+i];
    }
    for(int i=0; i<rnum;i++){
        rarr[i]=arr[medium+1+i];
    }
    int idx = left;
    int left_idx = 0, right_idx = 0;
    //如果左邊的陣列或右邊的陣列還有數字,就把各自最小的數拿出來比較
    while(left_idx<lnum && right_idx<rnum){
        if(larr[left_idx]<= rarr[right_idx]){
            arr[idx]= larr[left_idx];
            left_idx++;
        }
        else{
            arr[idx]= rarr[right_idx];
            right_idx++;
        }
        idx++;
    }
    
    //若左邊陣列裡還有數字,將剩下的數放進原陣列
    while(left_idx<lnum){
        arr[idx]= larr[left_idx];
        idx++;
        left_idx++;
    }
    
    //若右邊陣列裡還有數字,將剩下的數放進原陣列
    while(right_idx<rnum){
        arr[idx]= rarr[right_idx];
        idx++;
        right_idx++;
    }
}

二、合併排序(mergeSort)

再來是合併排序的部分,
假設我們定義了這樣一個函數:

// 希望此函數可以將arr[l...r]的範圍排序好(包含left, right邊界)
void mergeSort(int* arr, int left, int right);

那麼我們可以這樣遞迴去實作這個函數:

void mergeSort(int* arr, int left, int right)
{
    if(left<right){
        int mid = left+(right-left)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

首先判斷if(left<right)(當陣列還可以再切割時),
我們就繼續將大問題化為小問題:
mergeSort(arr, left, mid);意思就是說把陣列左邊的範圍排好,
mergeSort(arr, mid+1, right);意思就是說把陣列右邊的範圍排好,
再透過剛剛介紹的merge(arr, left, mid, right);函數將左右排好的陣列合併起來即可

完整可測試的程式碼如下

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

//結合兩陣列排序好的結果,
//左陣列為arr[l..m],右陣列為 arr[m+1..r]
void merge(int* arr, int left, int medium, int right)
{
    int lnum = medium-left+1, rnum=right-medium;
    int larr[lnum], rarr[rnum];
    for(int i=0; i<lnum;i++){
        larr[i]=arr[left+i];
    }
    for(int i=0; i<rnum;i++){
        rarr[i]=arr[medium+1+i];
    }
    int idx = left;
    int left_idx = 0, right_idx = 0;
    //如果左邊的陣列或右邊的陣列還有數字,就把各自最小的數拿出來比較
    while(left_idx<lnum && right_idx<rnum){
        if(larr[left_idx]<= rarr[right_idx]){
            arr[idx]= larr[left_idx];
            left_idx++;
        }
        else{
            arr[idx]= rarr[right_idx];
            right_idx++;
        }
        idx++;
    }
    
    while(left_idx<lnum){
        arr[idx]= larr[left_idx];
        idx++;
        left_idx++;
    }
    
    while(right_idx<rnum){
        arr[idx]= rarr[right_idx];
        idx++;
        right_idx++;
    }
}

// 將arr[l...r]的範圍排序好(包含left, right邊界)
void mergeSort(int* arr, int left, int right)
{
    if(left<right){
        int mid = left+(right-left)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

//單純將一個陣列印出來做測試
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

int main()
{
    int arr[]= {1,5,6,3,2,8,10,7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    mergeSort(arr, 0, arr_size-1);
    printArray(arr, arr_size);
    return 0;
}

參考資料

  1. Comparison Sort: Merge Sort(合併排序法)

小馬覺得這篇參考資料中寫mergeSort的程式碼更為簡短漂亮,有興趣可點閱學習


尚未有邦友留言

立即登入留言