👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜歡《數據結構》部分筆記的小伙伴可以訂閱專欄，今后還會不斷更新。🧑?💻
感興趣的小伙伴可以點一下訂閱、收藏、關注！🚀
謝謝大家！🙏

定義

合并：把兩個或多個已經有序的序列合并成一個

設置三個指針 $i,j,k$ ，對比$i,j$所指元素，選擇一個更小的放入 $k$ 所指的位置

只剩一個子表未合并時，可以將該表中剩余元素全部加到總表

二路歸并

也就是上面的過程↑：二合一

四路歸并

設置五個指針 $p_1,p_2,p_3,p_4,k$ ，對比 $p_1,p_2,p_3,p_4$ 所指元素，選擇一個更小的放入 $k$ 所指位置

四路歸并 —— 每選出一個小元素需要對比關鍵字3次

代碼實現

int *B = (int *) malloc (n * sizeof(int));  // 輔助數組B// A[low...mid]和A[mid+1,...,high]各自有序，將兩個部分合并
void Merge(int A[], int low, int mid, int high){int i, j, k;for(k = low; k <= high; k++)B[k] = A[k];  // 將A中所有元素復制到B中for(i = low, j = mid + 1, k = i; i <= mid && j <= high; k++){if(B[i] <= B[j])A[k] = B[i++];  // 將較小的值復制到A中elseA[k] = B[j++];}while(i <= mid) A[k++] = B[i++];while(j <= high) A[k++] = B[j++];
}void MergeSort(int A[], int low, int high){if(low < high){int mid = (low + high) / 2;  // 從中間劃分MergeSort(A, low, mid);  // 對左半部分歸并排序MergeSort(A, mid + 1, high);  // 對右半部分歸并排序Merge(A, low, mid, high);  // 歸并}
}

算法效率分析

2路冰柜的歸并樹，形態上就是一棵倒立的二叉樹

結論：
n個元素進行2路歸并排序，歸并趟數$=lo{g}_{2}n$
每趟歸并時間復雜度為 $O(n)$，則算法時間復雜度為 $O(nlo{g}_{2}n)$
空間復雜度$=O(n)$，來自輔助數組B