C语言常见排序算法归并排序

目录
  • 前言
  • 一、归并排序
    • 1.1 基本思想
    • 1.2 算法思想
    • 1.3 程序设计思想
    • 1.4 程序实现
    • 1.5 归并排序的特性总结

前言

本期为大家带来的是常见排序算法中的归并排序，博主在这里先分享归并排序的递归算法，包您一看就会，快来试试吧~

一、归并排序

1.1 基本思想

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

1.2 算法思想

到这里，我们可以得到一条结论，两个有序的子序列可以合成一个新的有序子序列，通过递归，我们两个新的有序序列也可以组成新的有序数列，最终实现排序的目的。有些朋友就会问了，这个我懂，关键是咋实现有序数列，其实非常的简单，分割递归至每个子序列只有一个元素时，是不是就有序啦，然后就可以合成有两个元素有序的列表嘛，再合成4个，8个……

1.3 程序设计思想

定义一个tmp数组，可以是动态开辟的(malloc)，用于临时存放合并后的有序数据，定义_MergeSort()函数，用于分解，合并数据（递归实现），参数有，待处理数组，数据区间（数组下标），tmp数组。

  • 判断区间是否存在，区间不存在以及只有一个元素的情况结束程序。
  • 分割区间：mid=(left+right)/2;递归左右区间，分割递归至每个子序列只有一个元素。
  • 每两个子序列一组，循环遍历每一个元素，if比较两个子序列各元素的大小，取大或取小，放入tmp数组，tmp[index++]=子序列++；直到有一个子序列遍历完，循环结束。
  • 循环判断是子序列是否遍历完毕，未遍历完毕的子序列剩余元素直接给到tmp数组。将tmp数组的对应的元素拷贝回原数组（已有序）。

1.4 程序实现

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<stdlib.h>//动态开辟空间的函数的头文件

void _MergeSort(int *a,int left,int right,int *tmp)
{
	//区间不存在以及只有一个元素的情况结束程序
	if (left>=right)
	{
		return;
	}

	int mid = (left + right) / 2;
	//假设[left,mid],[mid+1,right]有序，那么我们就可以归并了
	//递归使左右区间有序
	//分割递归至每个子序列只有一个元素
	_MergeSort(a,left,mid,tmp);
	_MergeSort(a, mid+1,right, tmp);

	//归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;

	while (begin1<=end1&&begin2<=end2)//有一个子序列遍历完，循环结束
	{
		if (a[begin1] < a[begin2])//升序，取小
		{
			tmp[index++] = a[begin1++];

		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}

	//判断子序列是否遍历完，未遍历完毕的子序列剩余元素直接给到tmp数组
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}

	while (begin2<=end2)
	{
		tmp[index++] = a[begin2++];
	}

	//拷贝回去
	for (int i=left;i<=right;++i)
	{
		a[i] = tmp[i];
	}
}

//归并排序
void MergeSort(int *a,int n)
{
	int* tmp=(int*)malloc(sizeof(int)*n);//动态开辟与待排序数组大小相等的一片连续的空间
	_MergeSort(a,0,n-1,tmp);//子函数实现归并

	free(tmp);//释放动态开辟的空间
}

//打印
void Print(int* a, int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
int main()
{
	int a[] = {10,6,7,1,3,9,4,2};
	MergeSort(a,sizeof(a)/sizeof(a[0]));
	Print(a,sizeof(a)/sizeof(a[0]));
	return 0;
}

1.5 归并排序的特性总结

  • 1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问 题。
  • 2. 时间复杂度：O(N*logN)
  • 3. 空间复杂度：O(N)
  • 4. 稳定性：稳定

到此这篇关于C语言常见排序算法归并排序的文章就介绍到这了,更多相关C语言归并排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第

  • 举例讲解C语言对归并排序算法的基础使用

    基础概念 百度百科是这么描述归并排序的: 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作. 设有数列 {6,202,100,301,38,8,1} 初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数 i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3 i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4 i=3 [ 1 6 8 38 100 202 301 ] 4 总计: 1

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

  • C语言 实现归并排序算法

    C语言 实现归并排序算法

    C语言 实现归并排序算法 归并排序(Merge sort)是创建在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 一个归并排序的例子:对一个随机点的链表进行排序 算法描述 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾

  • C语言演示对归并排序算法的优化实现

    基础 如果有两个数组已经有序,那么可以把这两个数组归并为更大的一个有序数组.归并排序便是建立在这一基础上.要将一个数组排序,可以将它划分为两个子数组分别排序,然后将结果归并,使得整体有序.子数组的排序同样采用这样的方法排序,这个过程是递归的. 下面是示例代码: #include "timsort.h" #include <stdlib.h> #include <string.h> // 将两个长度分别为l1, l2的已排序数组p1, p2合并为一个 // 已排序

  • C语言非递归算法解决快速排序与归并排序产生的栈溢出

    C语言非递归算法解决快速排序与归并排序产生的栈溢出

    目录 1.栈溢出原因和递归的基本认识 2.快速排序(非递归实现) 3.归并排序(非递归实现) 建议还不理解快速排序和归并排序的小伙伴们可以先去看我上一篇博客​​​​​​哦!C语言超详细讲解排序算法下篇 1.栈溢出原因和递归的基本认识 我们先简单来了解下内存分布结构: 栈区:用于存放地址.临时变量等:                                                                            堆区:程序运行期间动态分配所使用的场景: 静态区

  • C语言常见排序算法归并排序

    C语言常见排序算法归并排序

    目录 前言 一.归并排序 1.1 基本思想 1.2 算法思想 1.3 程序设计思想 1.4 程序实现 1.5 归并排序的特性总结 前言 本期为大家带来的是常见排序算法中的归并排序,博主在这里先分享归并排序的递归算法,包您一看就会,快来试试吧~ 一.归并排序 1.1 基本思想 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序 列:即先使每个子序列有序,再使

  • C语言常见排序算法之插入排序(直接插入排序,希尔排序)

    C语言常见排序算法之插入排序(直接插入排序,希尔排序)

    目录 前言 一.直接插入排序 1.1 基本思想 1.2 算法思想 1.3 程序实现 1.4 直接插入排序的总结 二.希尔排序 2.1 算法思想 2.2 程序实现 2.3 希尔排序的特征总结 前言 本期为大家带来的是常见排序算法中的插入排序,主要有直接插入排序以及它的升级版——希尔排序,包您一看就会,快来试试吧~ 一.直接插入排序 1.1 基本思想 在生活当中,这种排序方式处处可见: 在玩扑克牌的时候我们就会采用插入排序的思想,当我们拿起第二张牌时,就会下意识的与第一张牌进行比较,如果比第一张牌小

  • C语言常见排序算法之交换排序(冒泡排序,快速排序)

    目录 前言 1.交换排序——冒泡排序 1.1 算法思想 1.2 动图演示 1.3 冒泡最好的情况 2. 交换排序——快速排序 2.1 快速排序——挖坑法 快排的缺点 三数取中法 2.3 快速排序——左右指针法 2.4 前后指针法 前言 本期为大家带来的是常见排序算法中的交换排序,主要有冒泡排序,快速排序,快排分享了三种算法:挖坑法,左右指针法,前后指针法,以及两种优化方式:解决快排最坏情况的“三数取中”,避免递归次数过多的"小区间优化", 基本思想:所谓交换,就是根据序列中两个记录键值

  • 必须知道的C语言八大排序算法(收藏)

    必须知道的C语言八大排序算法(收藏)

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

  • Javascript中的常见排序算法

    具体代码及比较如下所示: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

  • C语言 奇偶排序算法详解及实例代码

    C语言 奇偶排序算法详解及实例代码

    C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

  • Python八大常见排序算法定义、实现及时间消耗效率分析

    本文实例讲述了Python八大常见排序算法定义.实现及时间消耗效率分析.分享给大家供大家参考,具体如下: 昨晚上开始总结了一下常见的几种排序算法,由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的,这里的目的是为了更加完整详尽的总结一下这些排序算法,为了复习基础的东西,从冒泡排序.直接插入排序.选择排序.归并排序.希尔排序.桶排序.堆排序.快速排序入手来分析和实现,在最后也给出来了简单的时间统计,重在原理.算法基础,其他的次之,这些东西的熟练掌握不算是对之后的工作或者

  • Java实现常见排序算法的优化

    冒泡排序 冒泡排序的思想: 每次让当前的元素和它的下一个元素比较大小.如果前一个的元素大于后一个元素的话,交换两个元素. 这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素. 那么下次扫描的长度比上次少一个.因为数组的最后一个元素已经是最大的了.即最后一个元素已经有序了. 优化一: 优化的思路就是每一次扫描遍历一次数组.如果某次的扫描之后没有发生数组元素的交换的话.那么说明数组的元素已经是有序的了, 就可以直接跳出循环.没有继续扫描的必要了. 优化二:如果数组的尾部已经局部有

  • C语言 八大排序算法的过程图解及实现代码

    C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关

  • Java 常见排序算法代码分享

    Java 常见排序算法代码分享

    目录 1. 冒泡排序 2. 选择排序 3. 插入排序 4. 快速排序 5. 归并排序 6. 希尔排序 6.1 希尔-冒泡排序(慢) 6.2 希尔-插入排序(快) 7. 堆排序 8. 计数排序 9. 桶排序 10. 基数排序 11. 使用集合或 API 11.1 优先队列 11.2 Java API 汇总: 1. 冒泡排序 每轮循环确定最值: public void bubbleSort(int[] nums){     int temp;     boolean isSort = false;

随机推荐