【数据结构】八大排序之归并排序算法

简介: 【数据结构】八大排序之归并排序算法

一.归并排序简介及思想

"归并"一词的中文含义就是合并,并入的意思,而在数据结构中的定义将两个或两个以上的有序表组合成一个新的有序表.

归并排序(Merging Sort)就是利用归并的思想实现的排序方法.

它的原理是:

      假设初始序列含有n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到 ( 表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,......,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序.

算法动图演示如下:

算法逻辑演示:


二.归并排序的代码实现

算法实现步骤:(以升序为例)

  1. 将数组中的n个数据看成n个有序子序列
  2. 然后将其两两归并到新数组内,得到 +1或 个长度为1或2的有序子序列,将新数组的数据拷贝回原数组.
  3. 重复步骤2,直到归并得到一个长度为n的有序序列为止.

综上,归并排序的代码实现如下:

//归并递归子函数
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if ( begin >= end )
    return;
 
  int mid = (begin + end) / 2;
  
  //先递归后访问进行操作,类似于树的后序遍历
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid+1, end, tmp);
 
  //递归到叶子数组后,开始归并
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int i = begin;
 
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])//循环将小值尾插进新数组
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
 
    //防止合并时有数组没拷贝完
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
 
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
 
  //拷贝tmp回原数组
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
 
}
 
//归并排序
void MergeSort(int* a, int n)//不写区间,因为该函数不递归自己,否则每次都要malloc
{
  //开数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
 
  _MergeSort(a, 0, n - 1, tmp);//归并递归子函数
 
  free(tmp);
}

三.归并排序的非递归代码实现

算法实现思路:(以升序为例)

      因为归并排序递归是将完整的数组不断分割成只有一个元素的数组进行归并的,那么我们实现非递归的时候,就可以在一开始直接将数组视为n个只有一个元素的子序列进行归并,然后再按照两个两个元素的数组进行归并,一直向上归并,直到归并成为一个有n个元素的有序数组为止.

       归并排序在非递归实现时需要额外注意当n不是2的次方倍时归并数组末尾的越界现象,并对此错误现象做出及时的修正.

归并排序的非递归实现代码如下:

//归并排序非递归
void MergeSortNonR(int* a, int n)
{
  //开数组
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
 
  int gap = 1;
 
  while (gap < n)
  {
    for (int i = 0; i < n; i =i+ 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
 
      //修正数组非2的次方倍数时的越界现象
      if (end1 >= n)
      {
        end1 = n - 1;
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;
      }
 
      int j = i;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
    }
    memcpy(a, tmp, sizeof(int) * n);
    gap *= 2;
  }
 
  free(tmp);
}

四.归并排序的复杂度分析

📌时间复杂度

从最开始的示意图我们可以看出,归并排序一趟总共处理n个元素,而总共要处理logn趟,因此归并排序的最好,最坏,以及平均时间复杂度都是一样的,那就是O(nlogn).


📌空间复杂度

而我们在排序过程中需要一个和原数组相同大小的临时数组来对数组进行归并排序,因此归并排序的空间复杂度为O(n).


结语

希望这篇归并排序算法详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

数据结构排序算法篇思维导图:



相关文章
|
1月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
70 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
13天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
56 8
|
13天前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
45 7
|
1月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
33 4
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
31 0
|
1月前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
28天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
13天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
14天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
15天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。