#include <iostream>
#include <vector>
using namespace std;
void mymerge(vector<int> &A,vector<int> L, vector<int> R)
{
//功能 为把两个数组有序放入到一个第三方数组中
int l = L.size();
int r = R.size();
int i=0,j=0,k=0;
while(i!=l&&j!=r)
{
if(L[i]<R[j])
A[k++] = L[i++];
else if (R[j]<L[i])
A[k++] = R[j++];
}
while(j!=r)
A[k++] = R[j++];
while(i!=l)
A[k++] = L[i++];
}
void mymergesort(vector<int> &arr)
{
//功能为把一个数组拆分为两个成员数量大致相等的数组
int len = arr.size();
if(len<2)
return;
int mid = len/2;
vector<int> L(mid);
vector<int> R(len-mid);
int i = 0;
for(;i<mid;i++)
{
L[i] = arr[i];
}
for(;i<len;i++)
{
R[i-mid] = arr[i];
}
//对这两个刚刚拆好的数组再这样循环折下去，直到不能再折
mymergesort(L);
mymergesort(R);
//一层一层的两两组装（有序组装）
mymerge(arr,L,R);
}
int main()
{
int N;
cout << "输入数组长度:";
cin >> N;
int a[N] = {0};
cout << "输入数组内容：" << endl;
for(int i=0;i<N;i++)
{
cin >> a[i];
}
vector<int> myarr(a,a+N);
//归并排序
mymergesort(myarr);
cout << "排过序之后：";
for(int i=0;i<N;i++)
{
cout << endl << myarr[i] << " ";
}
return 0;
}
2019-08-21（归并排序）
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 核心思想就是，左边红色的数组，和右边绿色数组需要有序的合并成下面那个大数组。那插入方式也很简单，只要你先把左边儿的...
- 常见的排序算法总结 1，冒泡排序 冒泡排序算法的运作如下：（从后往前） 比较相邻的元素。如果第一个比第二个大，就交...
