【排序算法】归并排序(C语言)

这篇具有很好参考价值的文章主要介绍了【排序算法】归并排序(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【排序算法】—— 归并排序(C语言)

一、归并排序的原理

归并排序(MergeSort) 是建立在归并操作上的一种有效的排序算法,采用分治法排序,分为分解合并两个步骤。

分解:将数组分割成两个数组,再分别将两个数组又细分成2个数组,直到,最后每个数组都是一个元素,这时将该单元素数组看为有序数组

合并:将分割的有序数组进行排序,排成有序数组后继续为上一个分割它的数组合并,直到数组被合并成原来的数组,此时已经排好序了

【排序算法】归并排序(C语言)

二、两个有序数组排序和合并

1. 原地排序

从头到尾遍历,选最小值放前面

  1. 合并的两个数组是一个数组分割开的,所以它们的首尾是相连的,用箭头i指向合并后数组的当前下标位置

【排序算法】归并排序(C语言)

  1. 将2和1比较,1小,所以将1赋值给合并后数组的第一个元素,此时我们发现,数组arr1的首元素被覆盖,所以不能直接赋值

【排序算法】归并排序(C语言)

  1. 若是将arr1的元素向后挪动一格,则数据正常,但是效率太低,不可取

【排序算法】归并排序(C语言)

从后往前遍历,选最大值放后面

  1. 用箭头i指向合并后数组的后边,从后往前遍历

【排序算法】归并排序(C语言)

  1. 8比7大,赋值给i指向的位置,此时7被覆盖,不行

【排序算法】归并排序(C语言)

  1. 若是将7和8交换呢,看样子可以,那如果是如下数组就不行了,arr1的有序性被破坏,不能继续这样排序了

【排序算法】归并排序(C语言)

2. 创建临时空间

  1. 既然无法原地排序,那我们创建临时空间,对两个有序数组排序

【排序算法】归并排序(C语言)

  1. 从前往后遍历,选出最小值放在temp数组前面部分

【排序算法】归并排序(C语言)

  1. 直到排序完成,将temp数组中的数据拷贝回原数组,arr1arr2就合并成为有序数组arr

【排序算法】归并排序(C语言)

二、递归实现

我们使用递归来实现数组的分割和合并,它的逻辑非常像二叉树的后序遍历,由于我们要使用递归,又要申请临时空间,所以我们先申请好临时空间,再将归并排序过程作为子函数调用,这样不用在每次递归过程申请释放空间

归并排序调用递归

void MergeSort(int* arr, int size)
{
	int* temp = (int*)malloc(size * sizeof(int));
	if (temp == NULL)
	{
		perror("malloc fail\n");
		return;
	}

	_MergeSort(arr, 0, size - 1, temp);	//归并排序的过程

	free(temp);
	temp = NULL;
}

归并排序

由于我们递归过程中要用区间来分割函数,所以参数为待排数组的闭区间,使代码书写更加方便,这也是将递归过程单独调用的好处

void _MergeSort(int* arr, int left, int right, int* temp)
{
    //分解:
    //分割数组只有一个元素时停止递归
	if (left >= right)
	{
		return;
	}

	int mid = (left + right) / 2;

	_MergeSort(arr, left, mid, temp);		//分割并排序数组左半边
	_MergeSort(arr, mid + 1, right, temp);	//分割并排序数组右半边

    //合并:
	int begin1 = left, end1 = mid;			//数组1的左右区间
	int begin2 = mid + 1, end2 = right;		//数组2的左右区间
	int i = begin1;

    //排序两个有序数组
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			temp[i] = arr[begin1];
			begin1++;
		}
		else
		{
			temp[i] = arr[begin2];
			begin2++;
		}
		i++;
	}

	while (begin1 <= end1)
	{
		temp[i] = arr[begin1];
		begin1++;
		i++;
	}

	while (begin2 <= end2)
	{
		temp[i] = arr[begin2];
		begin2++;
		i++;
	}

	//拷贝临时数组的内容到原数组(可以调用memcpy函数)
	//memcpy(arr+left, temp+left, (right-left+1)*sizeof(int));
	for (i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

三、非递归实现

归并排序的非递归实现是非常复杂的一个算法,在快速排序中我们使用栈来存储待排数组的左右区间,模拟递归的过程。但是在归并排序中我们不这么实现。

1. 实现思路

由于数组总是以一半的方式进行分割,分割的终点是每个数组只有一个元素,所以我们可以定义一个变量gap作为分割后数组的长度,遍历时一次跳过gap * 2个元素,刚好是两个数组的长度,gap从1开始对两个有序数组进行排序,直到gap作为数组长度的一半时结束

  1. gap = 1,此时将长度为1的数组排序并合并,将两个长度为1的数组合并(黄色和蓝色分别是需要合并的两个数组)

【排序算法】归并排序(C语言)

  1. 排序合并后,将i指针向后移动gap * 2个元素,刚好两个数组,继续排序合并

【排序算法】归并排序(C语言)

  1. 持续上述操作,直到数组排序完成,则第一躺排序完成,所有长度为1的有序数组都合并成长度为2的有序数组

【排序算法】归并排序(C语言)

  1. gap *= 2,一个数组长度为2,然后遍历数组,一次跳过2个有序数组(4个元素),并将两个有序数组排序合并

【排序算法】归并排序(C语言)

  1. gap *= 2,一个数组长度为4,然后遍历数组,一次跳过2个有序数组(8个元素),并将两个有序数组排序合并

【排序算法】归并排序(C语言)

  1. gap *= 2,此时gap为8,等于数组长度,意味着没有第二个数组与长度为8的数组合并了,排序结束,数组有序

【排序算法】归并排序(C语言)

2. 数组边界问题

在归并排序的非递归实现中,我们要遍历数组,将两个长度为gap的数组排序合并,但是gap总是2的幂次方,这就导致数组长度不一定是gap * 2的倍数,这就导致两个数组在遍历到数组边界时会导致越界问题。所以我们要对数组的边界问题进行处理

对于归并排序合并的两个数组,有3种越界情况:

  1. 第一个数组越界

黄色和蓝色数组是需要合并的两个数组,第一个数组指的是黄色数组,第二个数组指的是蓝色数组

此时遍历到数组末尾时,第一个数组只有一个元素,但是需要合并的数组长度是2,所以第一个数组访问时会造成越界(第二个数组自然也越界)

【排序算法】归并排序(C语言)

  1. 第二个数组全部越界

此时遍历到数组末尾时,第一个数组的长度刚好到原数组的末尾,第二个数组不存在,访问第二个数组是回越界

【排序算法】归并排序(C语言)

  1. 第二个数组部分越界

此时第一个数组在数组内,第二个数组只有一部分在数组内,第二个数组存在但是长度没有gap,访问第二个数组时会越界

【排序算法】归并排序(C语言)

解决方法:

我们来解决这些数组越界问题的方法是调整数组区间范围

  1. 第一个数组越界时,第二个数组不存在,所以不用合并,第一个数组本身就是有序数组
  2. 第二个数组完全越界时,第二个数组依然不存在,所以不用合并
  3. 第三个数部分组越界时,第二个数组存在但是不完整,此时我们将第二个数组的结束位置调整为原数组末尾位置即可,让第一个数组和第二个数组合并。

3. 代码实现

先申请临时空间,然后根据gap遍历数组,依次排序合并数组。文章来源地址https://www.toymoban.com/news/detail-480357.html

void MergeSortNonR(int* arr, int size)
{
    //申请空间
    int* temp = (int*)malloc(size * sizeof(int));
    if (temp == NULL)
    {
        perror("malloc fail!\n");
        return;
    }
    
    //归并排序
    int gap = 1;
    while (gap < size)
    {
        //单趟排序
        int i = 0;
        for (i = 0; i < size; i += 2*gap)	//一次跨2*gap格,两个数组
        {
            int begin1 = i, end1 = i+gap-1;			//第一个数组下标区间
            int begin2 = i+gap, end2 = i+2*gap-1;	//第二个数组下标区间,别忘记加上i
            
            //数组边界处理
            if (end1 >= size)	//第一个数组越界
            {
                break;
            }
            if (begin2 >= size)	//第二个数组全部越界
            {
                break;
            }
            if (end2 >= size)	//第二个数组部分越界
            {
                end2 = size - 1;
            }
            
            //排序合并
            int j = i;	//合并后数组的下标
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (arr[begin1] <= arr[begin2])
                {
                    temp[j] = arr[begin1];
                    begin1++;
                }
                else
                {
                    temp[j] = arr[begin2];
                    begin2++;
                }
                j++;
            }
            
            while (begin1 <= end1)
            {
                temp[j] = arr[begin1];
                begin1++;
                j++;
            }
            
            while (begin2 <= end2)
            {
                temp[j] = arr[begin2];
                begin2++;
                j++;
            }
            
            //拷贝temp数组到原数组(排哪个区间就拷贝哪个区间,end2是闭区间哦)
            for (j=i; j<=end2; j++)
            {
                arr[j] = temp[j];
            }
        }
        gap *= 2;
    }
    
    free(temp);
    temp = NULL;
}

到了这里,关于【排序算法】归并排序(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言实现八大排序算法(详解插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序(递归和非递归)、归并排序(递归和非递归)和计数排序)

    本篇文章使用C语言实现了数据结构中常见的八大排序算法,它们分别是 插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序 。在排序算法的实现过程中,每种算法都有其独特的特点和适用场景。插入排序通过逐步构建有序序列来排序,希尔

    2024年01月24日
    浏览(54)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(70)
  • 考研算法31天:归并排序 【归并排序,分治】

    算法介绍 归并算法其过程分为三步: 1.分:递归到最下面 2.治:两个元素之间排序。 3。归:递归到最下层然后返回,从两个元素变成四个元素再排序。 如下图所示: 动态图如下: 算法题目 算法ac代码:

    2024年02月11日
    浏览(41)
  • 【排序】归并排序(C语言实现)

          归并排序(MERGE - SORT)是建立在归并操作上的一种有效的排序算法, 该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为

    2024年02月02日
    浏览(38)
  • 【算法】排序——归并排序和计数排序

     ========================================================================= 主页点击直达:个人主页 我的小仓库:代码仓库 C语言偷着笑:C语言专栏 数据结构挨打小记: 初阶数据结构专栏 Linux被操作记: Linux专栏 LeetCode刷题掉发记: LeetCode刷题 算法头疼记: 算法专栏  ========================

    2024年02月08日
    浏览(36)
  • 【排序算法】归并排序与快速排序

           🔥🔥 欢迎来到小林的博客!!       🛰️博客主页:✈️小林爱敲代码       🛰️博客专栏:✈️ 算法训练笔记       🛰️社区 :✈️ 进步学堂       🛰️欢迎关注:👍点赞🙌收藏✍️留言 今天给大家分享两种排序,一种是

    2024年01月19日
    浏览(39)
  • 【初阶算法4】——归并排序的详解,及其归并排序的扩展

    目录 前言 学习目标: 学习内容: 一、介绍归并排序 1.1 归并排序的思路 1.2 归并排序的代码 1.2.1 mergesort函数部分  1.2.2 process函数部分  1.2.3 merge函数部分  二、AC两道经典的OJ题目 题目一:逆序对问题 题目二:小和问题  三、练习一道LeetCode的题目 四、总结在什么情况下使

    2024年02月08日
    浏览(40)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(53)
  • 排序算法:归并排序(非递归)

    先赞后看,养成习惯!!!^ _ ^3 ❤️ ❤️ ❤️ 码字不易,大家的支持就是我坚持下去的动力。点赞后不要忘了 关注 我哦! 所属专栏:排序算法 步骤如下: 1.先两两归并,两个为一组 2.然后根据每组的距离gap,分配组数进行排序 3.gap每次扩大2的倍数 4.注意一些细节:首先注

    2024年03月24日
    浏览(38)
  • 深度理解排序算法——归并排序

    ………………………………………………………………………………… 给定一段无序数组,将数组拆分成 两段 ,使得 左右两段 得数组均呈现有序状态,再借助 临时数组 将两段数组归并至一块呈现有序,最后 拷贝 回原数组即得到有序数组。 从逻辑上理解,就是一颗 二叉

    2024年02月03日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包