数据结构与算法基础-学习-33-归并排序

目录

一、基本思想

二、算法思路

1、合并两个有序序列

三、算法源码

1、MergeSortTwoSortData

2、TwoWayMergeSortRecurtionSentryQueue

四、算法效率分析

五、Linux环境编译测试

六、小感慨

排序的其他相关知识点和源码分享可以参考之前的博客：

《数据结构与算法基础-学习-30-插入排序之直接插入排序、二分插入排序、希尔排序》，

《数据结构与算法基础-学习-31-交换排序之冒泡排序、快速排序》，

《数据结构与算法基础-学习-32-选择排序之简单选择排序、堆排序》

一、基本思想

将两个或两个以上的有序子序列“归并”为一个有序序列。

在内部排序中，通常采用的是2路归并排序。

也就是将两个位置相邻的有序子序列R[l..m]和R[m+1..n]归并为一个有序序列R[l..n]。

二、算法思路

归并排序分两个部分进行实现，第一个部分就是将两个有序的序列合并成一个有序的序列。第二部分利用递归的思想将序列拆分成多个元素进行排序。

1、合并两个有序序列

（1）两个有序序列我们放在了一个数组中进行合并。Low和Mid分别表示Pre的起始和结束节点。Mid+1和High分别表示Tail的起始和结束节点。我们这里还是以升序为例，Pre的6和Tail的4进行比较4小，4插入到新的数组中。

（2）Tail前进一，Pre的6和Tail的5进行比较5小，5插入到新的数组中。

（3）Tail前进一，Pre的6和Tail的8进行比较6小，6插入到新的数组中。

（4）Pre前进一，Pre的9和Tail的8进行比较8小，8插入到新的数组中。

（5）Tail前进一，Tail已经超过High了，说明后半段有序序列已经访问完毕，这时只需把前半段的Pre开始遍历插入到新数组即可。

2、分治法

分治法其实就是把一个任务拆成多个小的任务，小的任务都完成了就把整个大任务完成了，是一种思想，上面是给的一个序列前后正好包含两组有序的数组，如果换成是无序数组呢，我们只需要把无需数组分成两半，左边使其有序，右边使其有序，在进行合并即可，左边可以再分为两块，有一种套娃的感觉，这个时候我们是不是会联想到递归，其实递归的练习做多了，就会有这种想法冒出来，希望对大家有帮助。

三、算法源码

1、MergeSortTwoSortData


//将队列中两个有序的序列进行合并。
//例如Low到Mid升序排列，Mid加一到High升序排列。合并为一个升序队列。
Status MergeSortTwoSortData(SqQueue* Queue,QueueLenType Low,QueueLenType Mid,QueueLenType High)
{
    JudgeAllNullPointer(Queue);
 
    if (Queue->Flag != INT_TYPE_FLAG)
    {
        return FailFlag;
    }
    
    QueueLenType Pre       = Low;
    QueueLenType Tail      = Mid + 1;
    int*         Array     = (int*)(Queue->Data);
    SqQueue*     TmpQueue  = NULL;
    QueueLenType i;
 
    InitSqQueue(&TmpQueue, High - Low + 1, INT_TYPE_FLAG);
 
    while (Pre <= Mid && Tail <= High)
    {
        if (Array[Pre] > Array[Tail])
        {
            EnterSqQueue(TmpQueue,&(Array[Tail]));
            Tail++;
        }
        else if (Array[Pre] < Array[Tail])
        {
            EnterSqQueue(TmpQueue,&(Array[Pre]));
            Pre++;
        }
        else//等于
        {
            EnterSqQueue(TmpQueue,&(Array[Tail]));
            EnterSqQueue(TmpQueue,&(Array[Pre]));
            Tail++;
            Pre++;
        }
    }
    
    while (Pre <= Mid)
    {
        EnterSqQueue(TmpQueue,&(Array[Pre]));
        Pre++; 
    }
 
    while (Tail <= High)
    {
        EnterSqQueue(TmpQueue,&(Array[Tail]));
        Tail++; 
    }
    
    for (i = Low; i <= High; i++)
    {
        LeaveSqQueue(TmpQueue,&(Array[0]));
        Array[i] = Array[0];
    }
 
    DestroySqQueue(&TmpQueue); 
 
    LogFormat(Debug,"Merge Sort Two Sort Data OK.\n");
 
    return SuccessFlag;
}

2、TwoWayMergeSortRecurtionSentryQueue


void TwoWayMergeSortRecurtionSentryQueue(SqQueue* Queue,QueueLenType Low,QueueLenType High)
{
    JudgeAllNullPointer(Queue);
 
    if (Low == High)
    {
        return;
    }
    else
    {
        QueueLenType Mid = (Low + High) / 2;
        TwoWayMergeSortRecurtionSentryQueue(Queue,Low,Mid);
        TwoWayMergeSortRecurtionSentryQueue(Queue,Mid + 1,High);
        MergeSortTwoSortData(Queue,Low,Mid,High);
    }
}

四、算法效率分析

情况	时间复杂度	是否稳定
最好	O(n * log2^n)	稳定
最坏	O(n * log2^n)
平均	O(n * log2^n)

五、Linux环境编译测试


[gbase@czg2 Sort]$ make
gcc -Wall -Wextra -O3 InsertSort.c SwapSort.c SelectSort.c MergeSort.c BucketSort.c main.c -o TestSort -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/Log/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/HashTable/include/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/SqQueue/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/SqStack/ -L /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Make/Libs/ -lPublicFunction -lLog -lSqQueue
[gbase@czg2 Sort]$ ./TestSort 
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Info  ]--SqQueue Data   :
Data           : [ 0 ,5 ,6 ,7 ,8 ,9 ,0 ,1 ,2 ,3 ,4 ]
FrontIndex     : 0
RearIndex      : 0
SqQueueLen     : 11
SqQueueMaxLen  : 11
Flag           : INT_TYPE_FLAG
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Init SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Enter SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Leave SqQueue OK
2023-9-11--[ Debug ]--Destroy SqQueue OK
2023-9-11--[ Debug ]--Merge Sort Two Sort Data OK.
2023-9-11--[ Debug ]--Two Way Merge Sort Sentry Queue OK.
2023-9-11--[ Info  ]--Sort Function Elapsed Time   : 0 s
2023-9-11--[ Info  ]--SqQueue Data   :
Data           : [ 9 ,0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ]
FrontIndex     : 0
RearIndex      : 0
SqQueueLen     : 11
SqQueueMaxLen  : 11
Flag           : INT_TYPE_FLAG
2023-9-11--[ Debug ]--Destroy SqQueue OK

六、小感慨

《C语言学习-20-归并排序》这篇是一年前写的，虽然实现方法上差不多，但是看到现在和之前的变化，感觉自己又进步了一小点，开心，大家一起加油。

相关阅读:
MYSQL 数据库企业级架构演变史
 如何以最快速度将Vue接入在线客服系统？
Nacos注册中心10-Server端（处理服务心跳请求）
金九银十，刷完这个笔记，17K不能再少了....
基于springboot人事管理系统java项目介绍
 Java代码审计——ClassLoader 类加载机制
 STM32 | 方式1:手机发送指令，开发板向手机发送温湿度；方式2:手机发送指令，开发板定时向手机发送温湿度。
数据中台：数据治理概述
 互联网摸鱼日报（2022-12-03）
java：使用Jedis操作redis
原文地址：https://blog.csdn.net/qq_45111959/article/details/132802052