归并排序

概述

归并排序是典型的分而治之策略的应用。主要是把一个数组分成若干个子数组进行从小到大的归并直至有序。下面所说的归并排序默认为2路归并排序。


递归算法思想

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多种关于排序算法的实现。但是了解这些精妙的思想对我...

    AI那点小事
  • 九度OJ——1447最短路

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

    AI那点小事
  • 时间序列(三)

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

    AI那点小事
  • 简单排序

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

    AI那点小事
  • 数据结构--堆

    良辰美景TT
  • 0 到 n-1 的数组判重

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

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

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

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

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

    天天_哥
  • 自己动手写数据结构之封装动态数组

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

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

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

    ACM算法日常

扫码关注云+社区

领取腾讯云代金券