二路归并排序的算法设计和复杂度分析(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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验