# 归并排序

## 递归算法思想

1）将数组平分为2等份，对这两个子数组进行从小大到有序归并。 2）递归对左半部分进行2路归并 3）递归对右半部分进行2路归并

```//一趟归并
void Merge(int* data,int* tmp,int left,int right,int rightend)
{
int leftend = right-1;
int size = rightend-left+1;
int cnt = left;
while(left <= leftend && right <= rightend){
if(data[left] < data[right]){
tmp[cnt++] = data[left++];
}else{
tmp[cnt++] = data[right++];
}
}
while(left <= leftend){
tmp[cnt++] = data[left++];
}
while(right <= rightend){
tmp[cnt++] = data[right++];
}
for(int i = 0 ; i < size ; i++,rightend--){
data[rightend] = tmp[rightend];
}
}

//归并排序
void Msort(int* data,int* tmp,int left,int rightend)
{
if(left < rightend){
int mid = (left+rightend)/2;
Msort(data,tmp,left,mid);
Msort(data,tmp,mid+1,rightend);
Merge(data,tmp,left,mid+1,rightend);
}
}

//归并排序(递归版本)
void Merge_Sort(int* data,int size)
{
int* tmp = new int[size];
if(tmp != NULL){
Msort(data,tmp,0,size-1);
}
}```

## 非递归算法思想

1）首先构造一个与原数组大小一样的临时数组 2）设置归并长度length = 1，从头开始堆两个length长度的数组进行归并到tmp直至倒数第二组。由于原数组长度与length布置时候能整除，如果能整除，那么把最后一组归并到数组了，若不能，那么就直接导入tmp数组。 3）更新length，使之翻倍，重复上述2）操作，只不过是把tmp的数组归并到原数组。 4）重复上述2）与3）操作，直至length大于数组长度。

```//一趟归并
void Merge(int* data,int* tmp,int left,int right,int rightend)
{
int leftend = right-1;
int size = rightend-left+1;
int cnt = left;
while(left <= leftend && right <= rightend){
if(data[left] < data[right]){
tmp[cnt++] = data[left++];
}else{
tmp[cnt++] = data[right++];
}
}
while(left <= leftend){
tmp[cnt++] = data[left++];
}
while(right <= rightend){
tmp[cnt++] = data[right++];
}
for(int i = 0 ; i < size ; i++,rightend--){
data[rightend] = tmp[rightend];
}
}

//一趟归并排序
void Merge_Pass(int* data,int* tmp,int size,int length)
{
int i;
for(i = 0 ; i <= size-2*length ; i += 2*length){
Merge(data,tmp,i,i+length,i+2*length-1);
}
if(i+length < size){//归并最后两个子序列
Merge(data,tmp,i,i+length,size-1);
}else{//归并最后一个子序列
for(int j = i ; j < size ; j++){
tmp[j] = data[j];
}
}
}
//归并排序(非递归排序)
void Merge_Sort1(int* data,int size)
{
int* tmp = new int[size];
int length = 1;
if(tmp != NULL){
while(length < size){
Merge_Pass(data,tmp,size,length);
length*=2;
Merge_Pass(tmp,data,size,length);
length*=2;
}
delete tmp;
}
}```

## 全部代码

```#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

//初始化数组
void SetArray(int* data,int size)
{
//srand(time(0));
cout<<"随机初始化"<<size<<"个数"<<endl;
for(int i = 0 ; i < size ; i++){
data[i] =rand()%100+1;
}
}

//打印函数
void Print(int* data ,int size)
{
for(int i = 0 ; i < size ; i++){
cout<<data[i]<<" ";
}
cout<<endl;
}

//一趟归并
void Merge(int* data,int* tmp,int left,int right,int rightend)
{
int leftend = right-1;
int size = rightend-left+1;
int cnt = left;
while(left <= leftend && right <= rightend){
if(data[left] < data[right]){
tmp[cnt++] = data[left++];
}else{
tmp[cnt++] = data[right++];
}
}
while(left <= leftend){
tmp[cnt++] = data[left++];
}
while(right <= rightend){
tmp[cnt++] = data[right++];
}
for(int i = 0 ; i < size ; i++,rightend--){
data[rightend] = tmp[rightend];
}
}

//归并排序
void Msort(int* data,int* tmp,int left,int rightend)
{
if(left < rightend){
int mid = (left+rightend)/2;
Msort(data,tmp,left,mid);//递归归并排序左半部分
Msort(data,tmp,mid+1,rightend);//递归归并排序右半部分
Merge(data,tmp,left,mid+1,rightend);//对左右部分进行有序归并
}
}

//归并排序(递归版本)
void Merge_Sort(int* data,int size)
{
int* tmp = new int[size];
if(tmp != NULL){
Msort(data,tmp,0,size-1);
}
}

//一趟归并排序
void Merge_Pass(int* data,int* tmp,int size,int length)
{
int i;
for(i = 0 ; i <= size-2*length ; i += 2*length){
Merge(data,tmp,i,i+length,i+2*length-1);
}
if(i+length < size){//归并最后两个子序列
Merge(data,tmp,i,i+length,size-1);
}else{//归并最后一个子序列
for(int j = i ; j < size ; j++){
tmp[j] = data[j];
}
}
}
//归并排序(非递归排序)
void Merge_Sort1(int* data,int size)
{
int* tmp = new int[size];
int length = 1;
if(tmp != NULL){
while(length < size){
Merge_Pass(data,tmp,size,length);
length*=2;
Merge_Pass(tmp,data,size,length);
length*=2;
}
delete tmp;
}
}

int main()
{
cout<<"请输入数组长度:"<<endl;
int size,*data;
cin>>size;
data = new int[size];

SetArray(data,size);
cout<<"归并排序（递归版本）前："<<endl;
Print(data,size);
cout<<"归并排序（递归版本）后："<<endl;
Merge_Sort(data,size);
Print(data,size);

SetArray(data,size);
cout<<"归并排序（非递归版本）前："<<endl;
Print(data,size);
cout<<"归并排序（非递归版本）后："<<endl;
Merge_Sort1(data,size);
Print(data,size);

return 0;
}  ```

0 条评论

• ### 简单排序

排序是数据处理中十分常见且核心的操作，虽说实际项目开发中很小几率会需要我们手动实现，毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我...

• ### 九度OJ——1447最短路

题目描述： 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！...

• ### 时间序列(三)

(时间序列模型中的ARMA模型由于原理对我来说理解有些困难，加之最近的北美数学建模大赛即将开始，自己为了顾全大局，多看掌握几个重要模型，所以ARMA模型的...

• ### 简单排序

排序是数据处理中十分常见且核心的操作，虽说实际项目开发中很小几率会需要我们手动实现，毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我...

• ### 0 到 n-1 的数组判重

首先我们想到的就是hash,通过hash判断一个数字是否在之前出现过只需要O(1)的时间复杂度，我们知道hashset的底层过就是hashmap的key，即ha...

• ### 2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素

题目：以时间复杂度O(n)从长度为n的数组中找出同时满足下面两个条件的所有元素： （1）该元素比放在它前面的所有元素都大； （2）该元素比放在它后面的所...

• ### 微信小程序中wv:html的方法

在微信小程序开发过程中，我们有没有遇到这种情况，数据接口返回的是字符串，字符串中还包含了普通html便签，例如：

• ### 自己动手写数据结构之封装动态数组

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

• ### Educational Codeforces Round 98 (Rated for Div. 2)

里，每秒你有5种决策：选择移动到上下左右四个格子中的一个或者停留在原地。你不能连续两秒做相同的决策，问最短时间走到格子