mergeSort的關鍵是 merge。但是一個數組怎么來merge？所以，它是分兩步走的，首先它要把所給的數組分割開來，然后對分割開來的子數組進行合并。之前我們講過快排也要分割數組，但是這里的分割數組相對簡單。重點是如何將分割開來的數組合并起來

?先上圖，看圖比較容易理解：

MergeSort過程分析

經過我們的演示可以發現，我們的合并是沿著當初分割的原路合并的，在合并的時候將元素的大小順序排好。

將數組從中間分開得到新的兩子數組，對子數組重復進行分割操作，直至子數組足夠小（數組大小為1）。然后原路合并操作。

當需要合并的兩個子數組都只有一個元素時，比較大小，誰小誰在前，誰大誰在后，合并成一個新的數組

當需要合并的兩個子數組元素大于1 時，

• 假如兩個子數組為left[i] , right[j]
• 先使用兩個數組的第一個元素比較大小，例如left[0]和right[0]比較大小，如果left[0]<=right[0],則在組成新數組時，left[0]為新數組的第一個元素；right[0]再和left[1]比較大小。如此進行下去
• 如過left[] 的元素已經全部假如新的數組，而right[]還沒有全部假如新數組，則之間將right[]的剩余元素按其本身的順序關系添加到新數組后面即可
• ?

? ? 4.重復合并操作，直至重新生成的數組和數組大小一樣，MergeSort結束。

代碼演示

#include <stdio.h> #include <iostream>using namespace std; void merge(int arr[], int left,int mid, int right){int size_l = mid-left+1;int size_r = right- mid;int subArrLeft[size_l],subArrRight[size_r];for(int index = 0;index < size_l;index++){subArrLeft[index] = arr[left + index];}for(int index = 0;index < size_r;index++){subArrRight[index] = arr[mid + 1 + index];}int i = 0, j = 0;int k = left;// 按順序合并兩個子數組while (i < size_l && j < size_r){if(subArrLeft[i]<=subArrRight[j]){arr[k] = subArrLeft[i];i++;}else{arr[k] = subArrRight[j];j++;}k++;}// 如果比較的連個子數組中一個已經為空，另一個還有剩余元素，則直接追加到合并數組的后面while (i < size_l){arr[k] = subArrLeft[i];i++;k++;}while (j < size_r){arr[k] = subArrRight[j];j++;k++;} }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 arr[], int size) {int i;for (i = 0; i < size; i++) cout << arr[i] << " ";cout << endl; } int main() {int arr[] = {10, 7, 82, 9, 13, 5, 2, 34, 54, 3, 26, 6, 37, 6, 48, 11};int arrSize = sizeof(arr)/sizeof(arr[0]);cout << "perpare sort array is "<<endl;printArray(arr, arrSize);mergeSort(arr, 0, arrSize - 1);cout<<"MergeSorted array is "<<endl;printArray(arr, arrSize);return 0; }

代碼關鍵就在merge()函數.

運行結果

?

總結

以上是生活随笔為你收集整理的MergeSort(合并排序)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。