概念

將陣列切半直至一數,再兩兩比較將小者先排入新序列,此動作稱為合併,重複動做至剩一序列。

實作 (bottom-up)

由於使用botton-up 可以直接使用陣列,所以不必再將陣列切成一塊,只需合併。

  1. 建立指標目的是間接性修改資料,如下:a指向arr陣列,而b為排列後代換的。為什麼不直接替換的原因是:欲比較兩序列中左值若大於右值,交換就會破壞合併時的比較。
  2. 第一層迴圈是枚舉長度,從序列n個,藉序列大小乘二,至序列只有一個。以此模擬合併後的序列。
  3. 第二層迴圈是遍歷兩欲比較序列,當中以指標設置欲比較序列中的數值,start 為左方序列首,mid 為左序列尾、右序列首,high 為右序列尾,start1、start2、end1、end2紀錄當下比較位置、範圍限制。
  4. while迴圈是將比較結果存入b,模擬比較後放入。
  5. 將值替換。
//參考自維基
//https://gist.githubusercontent.com/hsuan1117/a0aac51cd40ca40260fddebfda79c243/raw/37a16ac614cea62b2880088123226f606f252e57/MergeSort%2520(Wiki).cpp
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = new int[len];
    for (int i = 1; i < len; i *= 2) {
        for (int start = 0; start < len; start += i*2) {
            int low = start, 
                mid = min(start + i, len), 
                high = cmp(start + i *2, len),
                k = low,
                start1 = low, end1 = mid,
                start2 = mid, end2 = high;  
            while (start1 < end1 && start2 < end2)
                b[k++] = 
                a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        swap(a,b);
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}
分享見解
我們建議您填寫正確的電子郵件地址,以便您能收到最新的回覆通知。
如果有任何問題需要聯繫我們,歡迎 m.me/cotpear Messenger 聯繫我們。
好耶!還有好多座位ヾ(≧▽≦*)o
Loading...