首页 > 其他分享 >归并排序笔记

归并排序笔记

时间:2024-10-06 10:22:14浏览次数:8  
标签:sort 归并 merge int mid 笔记 ++ 排序

int tmp[];//temp数组存储数据

void merge_sort(int a[],int l,int r) {
	if (l >= r) return;//递归到最后只有一个数返回
	int mid = (l + r)/2 ;//确定分界点   l~mid mid+1~r;
	merge_sort(a, l, mid);
	merge_sort(a, mid + 1, r);//递归左右两边
	int k = 0, i = l, j = mid + 1;//i,j为指针,分别从左右区的左边界开始移动
	while (i<=mid&&j<=r)/移动到右边界停止
	{
		if (a[i] < a[j]) tmp[k++] = a[i++];
		else tmp[k++] = a[j++];//每次选取左右区的较小值填入tmp中
	}
	while (i <= mid)tmp[k++] = a[i++];//填入左区余留元素
	while (j <= r)tmp[k++] = a[j++];//填入右区余留元素
	for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j]; 
}

//归并排序

ps:a[i++]=b[j++];先做赋值再做i++,b++;

标签:sort,归并,merge,int,mid,笔记,++,排序
From: https://www.cnblogs.com/dianman/p/18448888

相关文章

  • 各种排序算法相关性质整理
    排序算法稳定性最优时间复杂度平均时间复杂度最坏时间复杂度空间复杂度选择排序不稳定\(O(N^2)\)\(O(N^2)\)\(O(N^2)\)\(O(1)\)冒泡排序稳定\(O(N)\)\(O(N^2)\)\(O(N^2)\)\(O(1)\)插入排序稳定\(O(N)\)\(O(N^2)\)\(O(N^2)\)\(O(1)\)计数排序......
  • Living-Dream 系列笔记 第80期(国庆集训合集)
    IDDFS使用场景:搜索树非常大而答案的深度较浅,一般在\(20\)以内,且dfs会TLE,bfs会MLE。算法原理:以dfs的形式搜索;设定搜索的深度限制\(dep\);dfs深度不能超过\(dep\),且要恰好遍历所有\(dep\)的状态;若在\(dep\)层没有找到答案,\(dep+1\todep\),重新DFS......
  • 「分数规划」学习笔记及做题记录
    「分数规划」学习笔记及做题记录做题时发现不会分数规划,赶紧来学一下。分数规划用于求解下面一类问题:有\(n\)个物品,第\(i\)个物品的价值为\(a_i\),费用为\(b_i\)。从中选择若干个物品,使得价值与费用的比值\(\dfrac{\suma}{\sumb}\)最大/最小。另一种更严谨的表示方......
  • 《代码大全》阅读笔记1(2024.10.4)
    第一章:引言软件构建的艺术:介绍了软件开发的复杂性,以及编写高质量代码的重要性。强调了良好的编码习惯不仅能提高代码的可读性和可维护性,也能降低后期的开发成本。第二章:软件构建的哲学质量的重要性:讨论了软件质量的定义,强调高质量软件不仅包括功能的正确性,还包括可维护性、......
  • 2024.10.5 笔记
    贪心的证明方法(5个):咕咕咕贪心、DP。贪心优化DP。有简单策略:贪心。无:DP。手玩样例。手玩。兜底。重复:copy。一行多个最小值。不管。得到答案后转成0/1。反悔贪心的一般策略:先把所有都选上,再反悔。IOI那道题和这道题。感觉反悔贪心常用堆。手写堆,支持插入、......
  • 红日靶机(三)笔记
    VulnStack-红日靶机三概述相交于前边两个靶场环境,靶场三的难度还是稍难一点,有很多兔子洞,这就考验我们对已有信息的取舍和试错,以及对渗透测试优先级的判断。涉及到对数据库操作的试错,对joomla框架cve的快速学习,php中用到disabled_function的bypass,对linux内核提权的取舍......
  • 数据容器之集合(笔记)
    集合的特点不支持重复元素(去重)而且顺序不能保证(乱序,无下标索引)允许被修改小总结列表[]元祖()字符串""集合{}语法#语法{"sasa","kaka","papa","enen"}#字面量set_1={"sasa","kaka","papa","enen"}#用......
  • 【刷题笔记】2024.10.4 test
    2024.10.4test虹色的北斗七星思路题目要求\[maxn-minn-len\]的最大值,其中\(maxn\)为区间的最大值,\(minn\)为区间的最小值,\(len\)为区间的长度注意性质,最优的状态一定是区间的左右端点为最大值和最小值时。因为,如果区间左右端点不为最大值或最小值,那么区间长度就可以继续......
  • 归并排序
    inttmp[];//temp数组存储数据voidmerge_sort(inta[],intl,intr){if(l>=r)return;//递归到最后只有一个数返回intmid=(l+r)/2;//确定分界点l~midmid+1~r;merge_sort(a,l,mid);merge_sort(a,mid+1,r);//递归左右两边intk=0,i=l,j=mid+1;......
  • 学习笔记 - log
    目录1.定义2.性质3.计算公式本人实力不济,如有错误或建议及补充,请指出(评论或私信都行)1.定义如果\(x^n=a\),那么\(n\)叫作以\(x\)为底\(a\)的对数。记作\(n=\log_xa(x>0\text{且}x\neq1)\)。2.性质\(\log_aa^x=x\)(定义)\(\log_a1=0(a^0=1)\)\(\log_aa=1(a^1=a)\)负数......