归并排序，是分治算法的一个经典应用， 归并排序，利用分治的思想，将一个数组先一半一半分解为规模更小的数组，直至规模为1，然后小数组进行排序，在将已经排序的小数组逐渐合并为大数组，直至最终合并为原数组大小的已排好序的新数组。 实现代码如下（c++）
#include<iostream> #include<cmath> #include<vector> using namespace std; // sort ang then merge void merge(vector<int> &nums,int l,int mid, int r){ if ( (l+1)==r ){ if(nums[l]>nums[r]) { int temp=nums[l]; nums[l]=nums[r]; nums[r]=temp; } return; } int n=r-l+1; vector<int> tempa(n); int i=l,j=mid+1,k=0; while(i<=mid && j<=r){ if (nums[i]<nums[j]) tempa[k++]=nums[i++]; else tempa[k++]=nums[j++]; } while(i<=mid) tempa[k++]=nums[i++]; while(j<=r) tempa[k++]=nums[j++]; for(k=0;k<n;k++) nums[l+k]=tempa[k]; } // recursion decompose void decompose(vector<int> &nums,int l,int r){ if ( r==l) return; int mid=(l+r)/2; decompose(nums,l,mid); decompose(nums,mid+1,r); merge(nums,l,mid,r); } int main(){ vector<int> nums{2,3,1,28,11,4,6,88,6,7,5,4,8}; cout<<"the original array: " ; for(auto it=nums.begin();it!=nums.end();it++) cout<<*it<<" "; cout<<endl; auto n=nums.size(); decompose(nums,0,n-1); cout<<"the sorted array: "; for(auto it=nums.begin();it!=nums.end();it++) cout<<*it<<" "; cout<<endl; }运行结果如下： the original array: 2 3 1 28 11 4 6 88 6 7 5 4 8 the sorted array: 1 2 3 4 4 5 6 6 7 8 11 28 88
Process exited after 0.1731 seconds with return value 0 请按任意键继续…
