归并排序

归并排序

1. 将两个已经排序的数组合并为顺序数组
2. 如果两个数组没有排序，则使用分治法完成排序
3. 分治法，将数组不断分为1/2，直到数组元素为1，则左右两段数组都是已排序

可以运行的归并排序代码

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& num, int M, int L, int R)
{
int LEFT_SIZE=M-L;
int RIGHT_SIZE=R-M+1;

vector<int> left;
vector<int> right;

for(int i=L; i<M; ++i)
left.push_back(num[i]);
for(int j=M; j<=R; ++j)
right.push_back(num[j]);

int i=0;
int j=0;
int k=L;
while(i<LEFT_SIZE && j<RIGHT_SIZE)
{
if(left[i]<right[j])
{
num[k]=left[i];
++i;
++k;
}
else
{
num[k]=right[j];
++j;
++k;
}
}

while(i<LEFT_SIZE)
{
num[k]=left[i];
++i;
++k;
}
while(j<RIGHT_SIZE)
{
num[k]=right[j];
++j;
++k;
}
}

void merge_sort(vector<int>& num, int L, int R)
{
if(L==R)
return;
else{
int M=(L+R)/2;

merge_sort(num,L,M);
merge_sort(num,M+1,R);
merge(num,M+1,L,R);
}

}
int main()
{
vector<int> num{2,5,7,9,3,6,8,9};
int L=0;
int R=num.size()-1;
merge_sort(num,L,R);

for(auto c:num)
cout<<c<<" ";
cout<<endl;
return 0;
}