[数据结构与算法] 第八章——常用数据排序算法之归并排序

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 第八章——常用数据排序算法之归并排序 -> 正文阅读

[数据结构与算法]第八章——常用数据排序算法之归并排序

第八章常用数据排序算法

概述

插入排序、选择排序和冒泡排序这些算法有一个共同的特点，为了将N个无序数据进行排序最多需进行N-1轮处理，每轮处理范围大小不同（2~N-1），平均约N/2个数据元素，因此，当N比较大时，工作量和N*(N-1)/2成正比。所以这些用以小规模的数据排序整理。

在高档嵌入式应用系统中，当处理比较大量的数据时，为了提高效率就必须采用其他更高效的方法。这些算法的特点是都采用了“分治”的方法。也就是将整个排序范围分为若干小块。比如：归并排序和快速排序

归并排序

原理

将两个或者两个以上的有序数列合并成一个新的有序数列的过程被称为归并排序

对于一个含有N个元素的无序数列

首先把它看成各自只包含一个元素的有序子数列
每两个相邻的子列作为一组，对一组中的两个子序列进行归并，形成一个新的有序子序列
从第一个子列到最后一个子列，每两两归并被称为一轮归并

规律：每轮归并后，新子列长度增加一倍，子列数目减少一半

在归并过程中，需一块大小与原数列相等的存储空间，用于存放归并的结果
存放原始数列的空间称为原列，新开辟的用于存放归并中间结果的空间被称为新列。
一轮归并结束后，再对新列进行一轮归并，结果存放在原列，使两块空间交替使用

算法概述

第一步内层算法

目标

完成两个有序子列的归并操作

具体方法

? 左右两个子列各有一个动态指针，指向它们尚未处理的最小元素，将两个元素进行比较，将小者转抄到目标列中，然后将指针后移。当某个子列中的元素都被处理完成之后，将另一个子列中剩余的元素直接转抄到目标列中，便完成了两个有序列的归并操作。

程序

/********************************************************
* @函数:Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
* @描述:把两个有序子列进行归并
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
  		low:指向左子列的起始单元
  		mid:指向右子列的起始单元
  		high:指向右子列后面的单元
* @返回值:无
* @备注:左子列的范围:SourBuf[low]~SourBuf[mid-1]
	    右子列的范围:SourBuf[mid]~SourBuf[high-1]
*******************************************************/
void Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
{
    //初始化三个动态指针 分别指向左子列、右子列和目标列
    int left,right,target;
    left = low;		//指向左子列起始位置
    right = mid;	//指向右子列起始位置
    target = low;
    
    while(left<mid && right<high)
    {
        if(SourBuf[left] < SourBuf[right])
        {
            DestBuf[target++] = SourBuf[left++];
        }
        else
        {
            DestBuf[target++] = SourBuf[right++];
        }
    }
    //当其中一个子列的元素完成后
    while(left<mid)		//左子列有剩余元素
    {
        DestBuf[target++] = SourBuf[left++];
    }
    while(right<high)	//右子列有剩余元素
    {
        DestBuf[target++] = SourBuf[right++];
    }
}

第二部中层算法

目标

对全列进行一轮归并操作

具体方法

从头开始，以此将相邻的两个子列进行归并操作，如果最后还单独剩余一个子列，则直接转抄

程序

/********************************************************
* @函数:MergerCircle(int SourBuf[],int DestBuf[],int ElemLength)
* @描述:把两个有序子列进行归并
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
  		ElemLength:待排序的子列的长度
* @返回值:无
* @备注:无
*******************************************************/
#define AllElemNum	100		//要排列的总的元素数量

void MergerCircle(int SourBuf[],int DestBuf[],int ElemLength)
{
    int index,j;
    index = 0;
    while(index+2*ElemLength-1 < AllElemNum)//将要归并的元素数量超过两个ElemLength
    {
        Merger(SourBuf,DestBuf,index,index+ElemLength,index+2*ElemLength);
        index+=2*ElemLength;
    }
    //到这里说明剩余的元素数量不够两个ElemLength
    if(index+ElemLength < AllElemNum)//剩余最后一个右子列
    {
        Merger(SourBuf,DestBuf,index,index+ElemLength,AllElemNum);
    }
    else							//右子列不存在，只剩一个左子列
    {
        for(j=index;j<AllElemNum;j++)
        {
            DestBuf[j] = SourBuf[j];
        }
    }
}

第三步外层算法

目标

控制各轮归并操作的方向（原列归并到新列或者新列归并到原列）和子列的长度

具体方法

每调用一次一轮归并算法，就改变归并方向并将子列的长度加倍

程序

#define MAX 100			//元素个数最大值
int R[MAX],R1[MAX];		//待排序数据存放在数组R中，R1为辅助数组
int AllElemNum;			//实际元素个数
void MergerSort(void)	//对数组R进行归并排序，结果仍然在数组R中
{
	int CurLength = 1;
    while(CurLength < AllElemNum)//只要整个数组还可以分成两个以上子列
    {
        MergerCircle(R,R1,CurLength);//进行一轮归并，从R到R1
        CurLength *= 2;				//长度增加一倍
        MergerCircle(R1,R,CurLength);//在进行一轮归并，结果返回到R中
        CurLength *= 2;
    }
}

算法程序

#include <iostream>

using namespace std;

#define MAX 100			//元素个数最大值
int R[MAX],R1[MAX];		//待排序数据存放在数组R中，R1为辅助数组
int AllElemNum;					//实际元素个数

/********************************************************
* @函数:Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
* @描述:把两个有序子列进行归并
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
  		low:指向左子列的起始单元
  		mid:指向右子列的起始单元
  		high:指向右子列后面的单元
* @返回值:无
* @备注:左子列的范围:SourBuf[low]~SourBuf[mid-1]
	    右子列的范围:SourBuf[mid]~SourBuf[high-1]
*******************************************************/
void Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
{
    //初始化三个动态指针 分别指向左子列、右子列和目标列
    int left,right,target;
    left = low;		//指向左子列起始位置
    right = mid;	//指向右子列起始位置
    target = low;
    
    while(left<mid && right<high)
    {
        if(SourBuf[left] < SourBuf[right])
        {
            DestBuf[target++] = SourBuf[left++];
        }
        else
        {
            DestBuf[target++] = SourBuf[right++];
        }
    }
    //当其中一个子列的元素完成后
    while(left<mid)		//左子列有剩余元素
    {
        DestBuf[target++] = SourBuf[left++];
    }
    while(right<high)	//右子列有剩余元素
    {
        DestBuf[target++] = SourBuf[right++];
    }
}

/********************************************************
* @函数:MergerCircle(int SourBuf[],int DestBuf[],int ElemLength)
* @描述:把两个有序子列进行归并
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
  		ElemLength:待排序的子列的长度
* @返回值:无
* @备注:无
*******************************************************/

void MergerCircle(int SourBuf[],int DestBuf[],int ElemLength)
{
    int index,j;
    index = 0;
    while(index+2*ElemLength-1 < AllElemNum)//将要归并的元素数量超过两个ElemLength
    {
        Merger(SourBuf,DestBuf,index,index+ElemLength,index+2*ElemLength);
        index+=2*ElemLength;
    }
    //到这里说明剩余的元素数量不够两个ElemLength
    if(index+ElemLength < AllElemNum)//剩余最后一个右子列
    {
        Merger(SourBuf,DestBuf,index,index+ElemLength,AllElemNum);
    }
    else							//右子列不存在，只剩一个左子列
    {
        for(j=index;j<AllElemNum;j++)
        {
            DestBuf[j] = SourBuf[j];
        }
    }
}

/*
显示数组元素
*/
void Display(int Buf[])
{
    int i=0;
    printf("\r\n");
    for(i=0;i<AllElemNum;i++)
    {
        printf("%d ",Buf[i]);
    }
    printf("\r\n");
}

/*
归并排序
*/
void MergerSort(void)	//对数组R进行归并排序，结果仍然在数组R中
{
	int CurLength = 1;
    while(CurLength < AllElemNum)//只要整个数组还可以分成两个以上子列
    {
        MergerCircle(R,R1,CurLength);//进行一轮归并，从R到R1
        CurLength *= 2;				//长度增加一倍
        Display(R1);				//打印当前数组的元素
        MergerCircle(R1,R,CurLength);//在进行一轮归并，结果返回到R中
        CurLength *= 2;
        Display(R);
    }
}

int main(int argc,char *argv[])
{
    int i;
    while(1)
    {
        printf("\n请输入实际元素个数:");
        scanf("%d",&AllElemNum);
        if(AllElemNum<=MAX)break;
        printf("\n实际元素个数不能超过%d\r\n",MAX);
    }
    for(i=0;i<AllElemNum;i++)
    {
        printf("\n输入第%d个元素的值:",i+1);
        scanf("%d",&R[i]);
    }
    Display(R);
    MergerSort();
}

算法程序改进V1.0

原理

未排序的原始数据通常存在大量局部有序子列，而经典归并排序从长度为1的子列开始，没有充分利用这个有利条件，现对其优化，利用原始数据本身已存在的有序子列作为归并起点

具体方法

改进1.0在归并排序之前需对原始数据进行一次扫描，标记出各个有序子列的起始位置和结束位置。
由于一个子列的结束位置就是下一个子列的起始位置的前一个位置，所以只需要标记出各个有序子列的起始位置即可。
使用一个顺序队列来保存这些有序子列的起始位置，在最后一个有序子列的起始位置后面存放数据“-1”，用以表示结束
每次归并操作都从这个顺序队列中取出两个数据，得到两个有序子列的起始位置，进行归并操作后，再将归并后的新的有序子列的起始位置放到队列中，供以后继续归并操作使用

改进1.0程序

#include<iostream>
using namespace std;

#define MAX			100
#define QUEUE_MAX	MAX+2

int SR[MAX],TR[MAX];
int AllElemNum;

typedef struct{
    int date[QUEUE_MAX];
    int front,rear;
}SEQUEUE;
SEQUEUE sq;

//入队
int PushQueue(int x)
{
    if(sq.front == (sq.rear+1)%QUEUE_MAX)
    {
        return NULL;
    }
    else
    {
        sq.rear = (sq.rear+1)%QUEUE_MAX;
        sq.date[sq.rear] = x;
    }
    return 1;
}

//出队
int PopQueue(void)
{
    if(sq.front == sq.rear)
    {
        return NULL;
    }
    else
    {
        sq.front = (sq.front+1)%QUEUE_MAX;
        return (sq.date[sq.front]);
    }
}
/********************************************************
* @函数:Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
* @描述:把两个有序子列进行归并
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
  		low:指向左子列的起始单元
  		mid:指向右子列的起始单元
  		high:指向右子列后面的单元
* @返回值:无
* @备注:左子列的范围:SourBuf[low]~SourBuf[mid-1]
	    右子列的范围:SourBuf[mid]~SourBuf[high-1]
*******************************************************/
void Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
{
    //初始化三个动态指针 分别指向左子列、右子列和目标列
    int left,right,target;
    left = low;		//指向左子列起始位置
    right = mid;	//指向右子列起始位置
    target = low;
    
    while(left<mid && right<high)
    {
        if(SourBuf[left] < SourBuf[right])
        {
            DestBuf[target++] = SourBuf[left++];
        }
        else
        {
            DestBuf[target++] = SourBuf[right++];
        }
    }
    //当其中一个子列的元素完成后
    while(left<mid)		//左子列有剩余元素
    {
        DestBuf[target++] = SourBuf[left++];
    }
    while(right<high)	//右子列有剩余元素
    {
        DestBuf[target++] = SourBuf[right++];
    }
}
/********************************************************
* @函数:MergerCircle(int SourBuf[],int DestBuf[],int ElemLength)
* @描述:首先对数据进行扫描，把有序子序列的起始地址入队
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
  		ElemLength:待排序的子列的长度
* @返回值:无
* @备注:无
*******************************************************/

int MergerCircle(int SourBuf[],int DestBuf[])
{
    int low,mid,high,i;
    int w = 0;
    low = PopQueue();
    while(1)
    {
        mid = PopQueue();
        if(mid == -1)
        {
            for(i=low;i<AllElemNum;i++)
            {
                DestBuf[i] = SourBuf[i];
            }
            w++;
            PushQueue(low);
            PushQueue(-1);
            return w;
        }
        
        high = PopQueue();
        if(high == -1)
        {
            high = AllElemNum;
            Merger(SourBuf,DestBuf,low,mid,high);
            w++;
            PushQueue(low);
            PushQueue(-1);
            return w;
        }
        Merger(SourBuf,DestBuf,low,mid,high);
        w++;
        PushQueue(low);
        low = high;
    }
}

/*
显示数组元素
*/
void Display(int Buf[])
{
    int i=0;
    printf("\r\n");
    for(i=0;i<AllElemNum;i++)
    {
        printf("%d ",Buf[i]);
    }
    printf("\r\n");
}

/*
归并排序
*/
void MergerSort(void)	//对数组R进行归并排序，结果仍然在数组R中
{
	int i;
    sq.front = sq.rear = MAX-1;
    PushQueue(0);
    for(i=1;i<AllElemNum;i++)//扫描数据
    {
        if(SR[i]<SR[i-1])//后面数比前面数小，则记录一个子列，记录此时i的值
        {
            PushQueue(i);
        }
    }
    PushQueue(-1);//扫描完成，队列中加入-1，表示结束
    while(1)
    {
        MergerCircle(SR,TR);//进行一轮归并，结果在TR中
        Display(TR);
        if(MergerCircle(TR,SR)==1)
        {
            return;
        }
        Display(SR);
    }
}

int main(int argc,char *argv[])
{
    int i;
    while(1)
    {
        printf("\n请输入实际元素个数:");
        scanf("%d",&AllElemNum);
        if(AllElemNum<=MAX)break;
        printf("\n实际元素个数不能超过%d\r\n",MAX);
    }
    for(i=0;i<AllElemNum;i++)
    {
        printf("\n输入第%d个元素的值:",i+1);
        scanf("%d",&SR[i]);
    }
    Display(SR);
    MergerSort();
    Display(SR);
}

算法程序改进V2.0

原理

? 改进1.0的归并排序与经典归并排序相比，多了一个保存有序子列起始地址的队列，但是，当处于极端情况下，该队列所需要的存储单元甚至超过了待排序数据的存储单元（当源数据为从大到小的有序数据时，结尾还要存一个“-1”作为结束符，存储队里就比源数据的存储单元还多一个），当然，这种极端情况通常不会出现，但是要考虑这种情况。

具体方法

改进2.0的归并排序，在扫描原始数据的同时对源数据进行归并，将归并后的有序子列的起始地址入队，这样队列单元的开销可以节省一半。

改进2.0程序

#include<iostream>
using namespace std;

#define MAX			100
#define QUEUE_MAX	MAX+2

int SR[MAX],TR[MAX];
int AllElemNum;

typedef struct{
    int date[QUEUE_MAX];
    int front,rear;
}SEQUEUE;
SEQUEUE sq;

//入队
int PushQueue(int x)
{
    if(sq.front == (sq.rear+1)%QUEUE_MAX)
    {
        return NULL;
    }
    else
    {
        sq.rear = (sq.rear+1)%QUEUE_MAX;
        sq.date[sq.rear] = x;
    }
    return 1;
}

//出队
int PopQueue(void)
{
    if(sq.front == sq.rear)
    {
        return NULL;
    }
    else
    {
        sq.front = (sq.front+1)%QUEUE_MAX;
        return (sq.date[sq.front]);
    }
}
/********************************************************
* @函数:Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
* @描述:把两个有序子列进行归并
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
  		low:指向左子列的起始单元
  		mid:指向右子列的起始单元
  		high:指向右子列后面的单元
* @返回值:无
* @备注:左子列的范围:SourBuf[low]~SourBuf[mid-1]
	    右子列的范围:SourBuf[mid]~SourBuf[high-1]
*******************************************************/
void Merger(int SourBuf[],int DestBuf[],int low,int mid,int high)
{
    //初始化三个动态指针 分别指向左子列、右子列和目标列
    int left,right,target;
    left = low;		//指向左子列起始位置
    right = mid;	//指向右子列起始位置
    target = low;
    
    while(left<mid && right<high)
    {
        if(SourBuf[left] < SourBuf[right])
        {
            DestBuf[target++] = SourBuf[left++];
        }
        else
        {
            DestBuf[target++] = SourBuf[right++];
        }
    }
    //当其中一个子列的元素完成后
    while(left<mid)		//左子列有剩余元素
    {
        DestBuf[target++] = SourBuf[left++];
    }
    while(right<high)	//右子列有剩余元素
    {
        DestBuf[target++] = SourBuf[right++];
    }
}
/********************************************************
* @函数:MergerCircle(int SourBuf[],int DestBuf[])
* @描述:首先对数据进行扫描，同时对数据进行归并
* @参数:SourBuf:待排序的两个有序子列以此存入SourBuf
  		DestBuf:将排序结果存入DestBuf
* @返回值:无
* @备注:无
*******************************************************/

int MergerCircle(int SourBuf[],int DestBuf[])
{
    int low,mid,high,i;
    int w = 0;
	low = 0;
    while(1)
    {
        for(i=low+1;i<AllElemNum;i++)
        {
            if(SR[i]<SR[i-1])break;
        }
        mid = i;
        if(mid==AllElemNum)
        {
            for(i=low;i<AllElemNum;i++)
            {
                DestBuf[i] = SourBuf[i];
            }
            w++;
            PushQueue(low);
            PushQueue(-1);
            return w;
        }
        for(i=mid+1;i<AllElemNum;i++)
        {
            if(SR[i]<SR[i-1])break;
        }
        high = i;
        if(high == AllElemNum)
        {
            Merger(SourBuf,DestBuf,low,mid,high);
            w++;
            PushQueue(low);
            PushQueue(-1);
            return w;
        }
        Merger(SourBuf,DestBuf,low,mid,high);
        w++;
        PushQueue(low);
        low = high;
    }
}

/*
显示数组元素
*/
void Display(int Buf[])
{
    int i=0;
    printf("\r\n");
    for(i=0;i<AllElemNum;i++)
    {
        printf("%d ",Buf[i]);
    }
    printf("\r\n");
}

/*
归并排序
*/
void MergerSort(void)	//对数组R进行归并排序，结果仍然在数组R中
{
	int i;
    sq.front = sq.rear = MAX-1;
    PushQueue(0);
    for(i=1;i<AllElemNum;i++)//扫描数据
    {
        if(SR[i]<SR[i-1])//后面数比前面数小，则记录一个子列，记录此时i的值
        {
            PushQueue(i);
        }
    }
    PushQueue(-1);//扫描完成，队列中加入-1，表示结束
    while(1)
    {
        MergerCircle(SR,TR);//进行一轮归并，结果在TR中
        Display(TR);
        if(MergerCircle(TR,SR)==1)
        {
            return;
        }
        Display(SR);
    }
}

int main(int argc,char *argv[])
{
    int i;
    while(1)
    {
        printf("\n请输入实际元素个数:");
        scanf("%d",&AllElemNum);
        if(AllElemNum<=MAX)break;
        printf("\n实际元素个数不能超过%d\r\n",MAX);
    }
    for(i=0;i<AllElemNum;i++)
    {
        printf("\n输入第%d个元素的值:",i+1);
        scanf("%d",&SR[i]);
    }
    Display(SR);
    MergerSort();
    Display(SR);
}