C++ 歸並排序(merge sort)案例詳解
核心思想:“分”與“合”。
主體流程
先將一個序列分成很多個不能再分割的子序列,將各個子序列分別排序後再將子序列合並。其實就是重復兩個步驟:【1】分【2】合並。
首先是第一個小問題,怎麼分?
比如說一個序列:12 ,23,1,44,233,10,9,8。我們先分成兩段:12 ,23,1,44 和 233,10,9,8,
發現還能再分成4段:12 ,23 和 1,44——233,10 和 9,8。
再分成8段:12–23–1–44 和233–10–9–8。
這時候開始把子序列進行排序合並,一個元素就是有序的。所以不用排序。
合並成2個一組排序得到:12,23—-1,44—10,233—8,9。
再合並成4個一組排序得到:1,12,23,44—8,9,10,233。
最後合並得到最終結果:1,8,9,10,12,23,44,233。
下面是分段的代碼,用遞歸實現。
void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左邊有序 mergesort(a, mid + 1, last, temp); //右邊有序 mergearray(a, first, mid, last, temp); //再將二個有序數列合並 } }
整體思路很清晰,還差一個小問題沒解決,怎麼合並?
現在問題就變成瞭怎麼合並兩個有序序列,思路是比較兩個有序序列的第一個元素,誰小把誰放進最終序列的結尾,並把它從原來的隊列裡面刪掉直到有個序列為空。
這時候另一個序列可能還有剩餘的數據。沒關系,因為他們本身是有序的,所以我們隻要按順序把他們添加到最終序列的尾部就好瞭。
這樣兩個有序序列就合並成一個有序序列瞭。
實現代碼:
void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; }
整體測試代碼:
#include<iostream> #include<math.h> #include<stdlib.h> using namespace std; //將有二個有序數列a[first...mid]和a[mid...last]合並。 void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); //左邊有序 mergesort(a, mid + 1, last, temp); //右邊有序 mergearray(a, first, mid, last, temp); //再將二個有序數列合並 } } bool MergeSort(int a[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); delete[] p; //刪除p臨時數組 return true; } int main() { int i=0,temp=0; int a[10]={0}; for(i=0;i<10;i++) { a[i]=rand(); cout<<a[i]<<" "; } cout<<endl; MergeSort(a,10); for(i=0;i<10;i++) { cout<<a[i]<<" "; } return 0; }
到此這篇關於C++ 歸並排序(merge sort)案例詳解的文章就介紹到這瞭,更多相關C++ 歸並排序(merge sort)內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!