归并排序是分治算法的一个典型的体现：
将原问题分解为若干的子问题进行求解就可以了。
分治算法的步步骤：
归并排序的步骤：
第2-4行将原问题分成子问题，第5行将这些子问题进行合并。
原代码：
#ifndef MERGE_SORT_H#define MERGE_SORT_Hvoid mergeArr(int left,int mid,int right,int *arr); void mergeSort(int left,int right,int *arr); void mergeArr(int left,int mid,int right,int *arr){ int leftLen=mid-left+1; int rightLen=right-mid; int *leftsubArr=new int[leftLen]; int *rightsubArr=new int[rightLen]; for(int i=left;i<=mid; i++){ leftsubArr[i-left]=arr[i]; } for(int i=mid+1;i<=right; i++){ rightsubArr[i-mid-1]=arr[i]; } int i=0; int j=0; while(i<leftLen&&j<rightLen){ if(leftsubArr[i]<=rightsubArr[j]){ arr[left+i+j]=leftsubArr[i]; i++; }else{ arr[left+i+j]=rightsubArr[j]; j++; } } while(i<leftLen||j<rightLen){ if(i==leftLen&&j<rightLen){ arr[left+i+j]=rightsubArr[j]; j++; } if(j==rightLen&&i<leftLen){ arr[left+i+j]=leftsubArr[i]; i++; } }}void mergeSort(int left,int right,int *arr){ if(left<right){ int mid=(left+right)/2; mergeSort(left,mid,arr); mergeSort(mid+1,right,arr); mergeArr(left,mid,right,arr); }}#endif
测试代码：
int main(){ int arr[11]={9,5,10,5,4,12,7,3,2,1,6}; mergeSort(0,10,arr); for(int i=0;i<11; i++){ std::cout<<arr[i]<<std::endl; }}
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655545.html
相关资源：归并排序 C语言实现
