二路归并排序的算法设计和复杂度分析(C语言)

2024-04-16 16:28

本文主要是介绍二路归并排序的算法设计和复杂度分析(C语言),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

实验内容:

实验过程:

1.算法设计

2.程序清单

3.运行结果

4.算法复杂度分析


实验内容

二路归并排序的算法设计和复杂度分析。

实验过程

1.算法设计

二路归并排序算法,分为两个阶段,首先对待排序列进行拆分,然后进行合并排序。

第一阶段:将待排序列分长度成大致相等的两个子序列,按照同样的拆分方法,对每个子序列进行拆分,直到子序列中只有一个元素。

第二阶段:对拆分的结果,自底向上将相邻的两个有序序列合并排序。

2.程序清单

#include<stdio.h>
#include<malloc.h>
void disp(int a[],int n)
{int i;for(i=0;i<n;i++)printf("%d ",a[i]);printf("\n");
}
//将两个相邻的有序子序列归并为一个有序子序列
void Merge(int a[],int low,int mid,int high)
{int *tmpa;//创建临时数组tmpa储存合并结果int i=low,j=mid+1,k=0;//k是tmpa的下标,i,j分别为两个子表的下标tmpa=(int *)malloc((high-low+1)*sizeof(int));while(i<=mid&&j<=high)if(a[i]<=a[j])//将第一个子表中的元素放入tmpa中{tmpa[k]=a[i];i++;k++;}else//将第二个子表中的元素放入tmpa中{tmpa[k]=a[j];j++;k++;}while(i<=mid)//将第一个子表余下的部分复制到tmpa中{tmpa[k]=a[i];i++;k++;}while(j<=high)//将第二个子表余下的部分复制到tmpa中国{tmpa[k]=a[j];j++;k++;}for(k=0,i=low;i<=high;k++,i++)//将tmpa复制到a中a[i]=tmpa[k];free(tmpa);
}//二路归并算法
void MergeSort(int a[],int low,int high)
{int mid;if(low<high){mid=(low+high)/2;MergeSort(a,low,mid);//对a[low,mid]子序列排序MergeSort(a,mid+1,high);//对a[mid+1,high]子序列排序Merge(a,low,mid,high);//将两个子序列合并}
}
void main()
{int n=10;int a[]={1,5,2,4,10,6,3,8,9,10};printf("排序前");disp(a,n);MergeSort(a,0,n-1);printf("排序后");disp(a,n);
}

3.运行结果

4.算法复杂度分析

设MergeSort(a,0,n-1)算法的执行时间为T(n),显然Merge(a,0,n/2,n-1)合并操作的执行时间为O(n),所有得到以下递推式:

当n=1时,T(n)=1

当n>1时,T(n)=2T(n/2)+O(n)

故二路归并排序的算法时间复杂度为O(nlogn)

在算法中需要一个一维数组辅存储排序结果,所以空间复杂度为O(n)

这篇关于二路归并排序的算法设计和复杂度分析(C语言)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/909302

相关文章

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的