C++数据结构--归并排序

墨蓝 2021-11-10 16:54 555阅读 0赞

**1.归并算法图解  
Example：对向量数组v\{...,7,10,19,25,12,17,21,30,48,...\}进行局部归并  
![20130808131515703][]  
  
step1:  
![20130808131529218][]  
  
step2-step3  
![20130808131543531][]  
  
  
step4-step8  
![20130808131558687][]  
  
step9  
![20130808131608031][]  
  
  
  
  
2.归并排序  
Example：对向量数组v\{25,10,7,19,3,48,12,17,56,30,21\}调用mergeSort（）递归图解  
()内表示子表划分  
\[\]内表示归并  
![20130808131625640][]  
  
  
实现代码：  
\#include<iostream>  
\#include<vector>  
using namespace std;  
template<typename T>  
/\*合并向量数组\[first,mid),\[mid,last)  
\*该算法假设first,mid),\[mid,last)分别已经是有序序列  
\*注意，first并不一定是0  
\*/   
void merge(vector<T> &v,int first,int mid,int last)  
\{  
vector<T> tem; //临时向量数组  
int index1=first;  
int index2=mid;  
while(index1<mid&&index2<last) //同时从first,mid开始往后扫描   
\{   
if(v\[index1\]<=v\[index2\])  
 tem.push\_back(v\[index1++\]);  
else  
 tem.push\_back(v\[index2++\]);  
\}   
while(index1<mid)  //把剩余\[index1,mid)范围内的数据拷贝到tem   
tem.push\_back(v\[index1++\]);  
while(index2<last)   
tem.push\_back(v\[index2++\]);//把剩余\[index2,last)范围内的数据拷贝到tem   
  
 for(index1=first,index2=0;index2<tem.size();index1++,index2++)   
 v\[index1\]=tem\[index2\]; //把临时向量tem的数据拷回v  
  
  
\}  
  
  
  
  
  
  
template<typename T>  
//对向量数组v范围\[first,last)进行归并排序   
void mergeSort(vector<T> &v,int first,int last)  
\{  
  
if(first+1==last) //当下标划分到不能再划分时结束递归   
 return;  
  
int mid=(first+last)/2;  
mergeSort(v,first,mid);  
mergeSort(v,mid,last);  
merge(v,first,mid,last); //合并向量数组\[first,mid),\[mid,last)  
\}  
  
  
  
  
测试代码：  
int main()  
\{  
vector<int> vec\{25,10,7,19,3,48,12,17,56,30,21\};  
mergeSort(vec,0,vec.size());  
for(int x:vec)  
\{  
cout<<x<<ends;  
\}  
  
return 0;  
\}  
  
  
output:  
 3 7 10 12 17 19 21 25 30 48 56**

[20130808131515703]: /images/20211109/b855c6139c104ffc943cf8330a09f999.png
[20130808131529218]: /images/20211109/27df26b0eed441bb9ffa3a2dffcd3d1b.png
[20130808131543531]: /images/20211109/d9f16aafa885452cbd921826c0176ff4.png
[20130808131558687]: /images/20211109/83bc889c2e454904a1c9e971f4e53b76.png
[20130808131608031]: /images/20211109/07a15ecb41364e10b60721a86188aa57.png
[20130808131625640]: /images/20211109/0d7a548cd98f408d9e79685c229c3695.png