說一說歸并排序
歸并排序：歸并排序（英語：Merge sort，或mergesort），是創建在歸并操作上的一種有效的排序算法，效率為O(n log n)。1945年由約翰?馮?諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。
歸并排序的核心思想是將兩個有序的數列合并成一個大的有序的序列。通過遞歸，層層合并，即為歸并。
如圖，從下到上，每一步都需要將兩個已經有序的子數組合并成一個大的有序數組，如下是實現合并的具體代碼，請讀者細細體會
void merge(int arr[],int l,int mid,int r) { int aux[r-l+1];//開辟一個新的數組，將原數組映射進去 for(int m=l;m<=r;m++) { aux[m-l]=arr[m]; } int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分 for(int k=l;k<=r;k++) { if(i>mid) { arr[k]=aux[j-l]; j++; } else if(j>r) { arr[k]=aux[i-l]; i++; } else if(aux[i-l]<aux[j-l]) { arr[k]=aux[i-l]; i++; } else { arr[k]=aux[j-l]; j++; } } } 上圖代碼已經完成了歸并中的“并”這一部分，歸并歸并，有并必有歸，如下實現“歸”的部分
void merge_sort(int arr[],int l,int r){ if(l >=r) return ; int mid=(l+r)/2; merge_sort(arr,l,mid); merge_sort(arr,mid+1,r); merge(arr,l,mid,r);}由于上圖中的l，r不方便使用者調用，于是我們創建一個方便自己調用的my_merge_sort函數
void my_merge_sort(int arr[],int n){ merge_sort(arr,0,n-1); } 以上我們便實現了歸并排序中的歸和并，歸并排序是利用二分法實現的排序算法，時間復雜度為nlogn，是一種比較快速的排序算法。如下是筆者自己寫的歸并排序的全部代碼，
#include <iostream> using namespace std; void merge(int arr[],int l,int mid,int r) { int aux[r-l+1];//開辟一個新的數組，將原數組映射進去 for(int m=l;m<=r;m++) { aux[m-l]=arr[m]; } int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分 for(int k=l;k<=r;k++) { if(i>mid) { arr[k]=aux[j-l]; j++; } else if(j>r) { arr[k]=aux[i-l]; i++; } else if(aux[i-l]<aux[j-l]) { arr[k]=aux[i-l]; i++; } else { arr[k]=aux[j-l]; j++; } } } //遞歸的使用歸并排序，對arr[l....r]排序 void merge_sort(int arr[],int l,int r) { if(l >=r) return ; int mid=(l+r)/2; merge_sort(arr,l,mid); merge_sort(arr,mid+1,r); merge(arr,l,mid,r); } void my_merge_sort(int arr[],int n) { merge_sort(arr,0,n-1); } int main() { int a[6]; for(int i=0;i<6;i++) { cin>>a[i]; } my_merge_sort(a,6); for(int i=0;i<6;i++) { cout<<a[i]<<" "; } return 0; } 上面實現的歸并排序是自頂向下的，我們可以以另外一種方向來實現歸并，改遞歸為迭代。如下實現
#include <iostream> #include <math.h> using namespace std; void merge(int arr[],int l,int mid,int r) { int aux[r-l+1];//開辟一個新的數組，將原數組映射進去 for(int m=l;m<=r;m++) { aux[m-l]=arr[m]; } int i=l,j=mid+1;//i和j分別指向兩個子數組開頭部分 for(int k=l;k<=r;k++) { if(i>mid) { arr[k]=aux[j-l]; j++; } else if(j>r) { arr[k]=aux[i-l]; i++; } else if(aux[i-l]<aux[j-l]) { arr[k]=aux[i-l]; i++; } else { arr[k]=aux[j-l]; j++; } } } void mergesort(int arr[],int n) { for(int sz=1;sz<=n;sz+=sz) { for(int i=0;i+sz<n;i+=sz+sz)//i+sz防止越界 {//對arr[i...sz-1]和arr[i+sz.....i+2*sz-1]進行排序 merge(arr,i,i+sz-1,min(i+sz+sz-1,n-1)); //min函數防止越界 } } } int main() { int a[5]; for(int i=0;i<5;i++) { cin>>a[i]; } mergesort(a,5); for(int i=0;i<5;i++) { cout<<a[i]<<" "; } return 0; } 新聞熱點
疑難解答
圖片精選
