(C++)归并排序的递归与非递归实现
递归实现
merge函数利用的是双指针技巧降低复杂度。
mergeSort函数使用了递归，当中先对左右序列各调用一次mergeSort，再对整个序列调用merge。就按照最浅层的归并的思想去理解，不要大脑走到哪就step in。
另外mergeSort进入递归有个left<right的判定容易漏写。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int maxn = 10;
const int INF = 1000000000;//INF:下确界
const LL SUP = (1LL<<63)-1;//SUP:上确界
const double eps = 1e-5;LL Map[128];void merge(int A[],int L1,int R1,int L2,int R2){int i=L1,j=L2;int temp[maxn];int index = 0;while(i<=R1&&j<=R2){//是≤不是＜ if(A[i]<=A[j]){temp[index++] = A[i++];}else{temp[index++] = A[j++];}}while(i<=R1)temp[index++] = A[i++];//这个while很容易写成if while(j<=R2)temp[index++] = A[j++];for(int i=0;i<index;i++){A[L1+i] = temp[i];}}void mergeSort(int A[],int l,int r){//递归实现的归并排序 if(l<r){int mid = (l+r)/2;mergeSort(A,l,mid);mergeSort(A,mid+1,r);merge(A,l,mid,mid+1,r); }} int main(){int A[maxn] = {66,12,33,57,64,27,39,66,78,66};mergeSort(A,0,maxn-1);for(int i=0;i<maxn;i++){printf("%d ",A[i]);}return 0;
}非递归实现
基础的归并函数merge是一样的，但感觉非递归道理容易想明白但是实现起来细节多。注意两个for和一个if的<n不能写成<=n(如果传入的n是数组的长度而非最后一个元素的下标)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;const int maxn = 10;
const int INF = 1000000000;//INF:下确界
const LL SUP = (1LL<<63)-1;//SUP:上确界
const double eps = 1e-5;LL Map[128];void merge(int A[],int L1,int R1,int L2,int R2){int i=L1,j=L2;int temp[maxn];int index = 0;while(i<=R1&&j<=R2){//是≤不是＜ if(A[i]<=A[j]){temp[index++] = A[i++];}else{temp[index++] = A[j++];}}while(i<=R1)temp[index++] = A[i++];//这个while很容易写成if while(j<=R2)temp[index++] = A[j++];for(int i=0;i<index;i++){A[L1+i] = temp[i];}}void mergeSort(int A[],int n){//非递归实现的归并排序 //step为组内元素个数(每归并一次乘二)for(int step=2;step/2<n;step*=2){//每step个元素一组，组内左一半step/2和右一半step/2的元素合并，注意有很多个这样的组for(int i=0;i<n;i+=step){int mid = i+step/2-1;//step/2为左子区间元素个数if(mid+1<n){//右子区间存在元素则合并 merge(A,i,mid,mid+1,min(i+step-1,n));}} } } int main(){int A[maxn] = {66,12,33,57,64,27,39,66,78,66};mergeSort(A,maxn);for(int i=0;i<maxn;i++){printf("%d ",A[i]);}return 0;
}如果时间限制允许，且只要求打印出每一趟归并排序的结果，可以不调用merge()而是采用sort
void mergeSort(int A[],int len){for(int step = 2;step/2<len;step*=2){for(int i=0;i<len;i+=step){sort(A+i,A+min(i+step,len));}for(int i=0;i<maxn;i++){printf("%d ",A[i]);}printf("\n");}
}但是这样就不是真正意义上的归并了
相关文章：
SnackbarUtilDemo【Snackbar的封装类】
版权声明：本文为HaiyuKing原创文章，转载请注明出处！ 前言 这个工具类参考的是《没时间解释了，快使用Snackbar!——Android Snackbar花式使用指南》，代码几乎一样，所以想要了解具体原理或者更详细信息请阅读…
java通过代理访问网络
使用代理方式连接到网络 Testpublic void t13(){String charset "utf-8" ; String proxyHost "代理地址" ; int proxyPort 1234 ; //代理端口String proxyUrsername "登陆代理服务器的用户名" ; String proxyPassword "登陆代理服务器…
poj2503 Babelfish
跟poj3349很类似的题目，这题还稍简单。用qsort快速排序和二分查找可以很轻松AC。以下是代码： Run IDUserProblemResultMemoryTimeLanguageCode LengthSubmit Time5135234zen_chou2503Accepted2356K547MSC1212B2009-05-11 20:12:26Code1 #include <std…
(C语言)一种简易记法：生成[a,b]范围内的随机整数
1. 添加头文件 #include<stdlib.h> #include<time.h> 2. 初始化随机种子 srand((unsigned)time(NULL)); 3. 确定元素个数b-a1，以及最小元素 printf("%d",rand()%(b-a1)a);//生成[a,b]之间的数 printf("%d",rand()%1001);//生成…
IE和火狐都支持的方法(输入用户名和密码后按下 enter 键)
在Firefox中老报"event is not defined”错误！原因是因为在Firefox中使用了不同的事件对象模型,不同于IE Dom，用的是W3C Dom。 document.οnkeydοwnfunction mykeyDown(e){ //compatible IE and firefox because there is not event in fir…
数据库中存储与读取文件
if exists (select * from dbo.sysobjects where id object_id(N[dbo].[p_binaryIO]) and OBJECTPROPERTY(id, NIsProcedure) 1)drop procedure [dbo].[p_binaryIO]GO /*--bcp 实现二进制文件的导入导出 支持image,text,ntext字段的导入/导出 image适合于二进制文件,包括:Wor…
洛谷P3723 [AH2017/HNOI2017]礼物（FFT）
传送门 首先，两个数同时增加自然数值相当于只有其中一个数增加（此增加量可以小于0） 我们令$x$为当前的增加量，${a},{b}$分别为旋转后的两个数列，那么$$ans\sum_{i1}^n(a_ix-b_i)^2$$ 然后把第$i$项提出来并展开&#x…
1035 插入与归并
1. 这一题，首先要会插入排序和归并排序的写法。对于归并排序，可以用非递归sort最简便。把每一趟的结果存进二维数组。 2. 单独封装一个函数，比较两个一维数组是否完全一样。 3. 由于归并比插入的复杂度低，趟数少，所以…
代码设置LinearLayout的高度
问题描述我想把这个LinearLayout宽度设置成为FILL_PARENT，源码如下LinearLayout checkboxLinearLayout (LinearLayout) getLayoutInflater().inflate(R.layout.checkboxdoitem, null);LayoutParams params (LayoutParams) checkboxLinearLayout.getLayoutParams();…
精通Spring Boot —— 第十五篇：使用@ControllerAdvice处理异常
在Spring 3.2中，新增了ControllerAdvice、RestControllerAdvice 注解，可以用于定义ExceptionHandler、InitBinder、ModelAttribute，并应用到所有RequestMapping、PostMapping， GetMapping注解中。接下来我将通过代码展示如何使用这…
架构设计之分布式文件系统
1：类图 2：数据结构 create table TBCOFILE ( FILEID INTEGER not null, FILETIME DATE, TYPE VARCHAR2(10), USERID INTEGER, IP VARCHAR2(20), APPTYPE INTEGER default 0) 3：开发步骤 1：从数据库申…
1029 Median
1. 开始测试点3和6答案错误，原因是没有考虑到，给的两个数列有可能长度相差很大，某个数列还没到中位数，就结束了。 2. 这题的底子是用two pointers按照非递减的顺序合并两个数列，无非是再确定一下中间那个数的下标&…
理解系统底层的概念是多么重要
理解系统底层的概念是多么重要 ——趋势科技邹飞评《程序员的自我修养》 关于《程序员的自我修养》这本书，最初是在和博文的周筠老师MSN上谈起，当时听周老师提及这本书是一本关于链接和装载等系统软件知识的书籍，当时就很感兴趣，因…
session删除
删除一个session值： session_unset(变量); session_destroy(变量); 删除一个cookie： 注意第二个参数中手册中的说明是： Cookie 必须用和设定时的同样的参数才能删除。如果其值一个空字符串，或者是 FALSE，并且其它的参数…
Android学习路线
Android学习路线 第一阶段：Java面向对象编程 1.Java基本数据类型与表达式，分支循环。 2.String和StringBuffer的使用、正则表达式。 3.面向对象的抽象，封装，继承，多态，类与对象，对象初始化和回…
1048 Find Coins(two pointers解法)
1. 很典型的双指针的应用，将数组按照非降排列，两个指针从一头一尾开始包抄，若等于（等于要放在第一个）则返回结果结束程序，小于则左指针右移，大于则右指针左移。 2. 起初还担心，如果…
TCP/IP 协议理解
TCP/IP 协议（Transmission Control Protocol / internet Protocol），因特网互联协议，又名网络通讯协议。通俗而言：TCP负责发现传输的问题，一有问题就发出信号，要求重新传输，直到所有数…
Webhint开源了一种代码检查工具
Webhint项目提供了一种用于检查代码的可访问性、性能和安全的开源检查（Linting）工具。在创建Web站点和应用中，有越来越多的细节问题亟待完善。为此，Webhint力图帮助开发人员标记这些细节。\\Webhint以命令行接口（CLI&a…
SHAREPOINT爬网设置
F:\2009年\MOSS档案 http://share:30088/default.aspx 进入管理中心 共享服务管理-SharedServices1-搜索设置-内容源和爬网计划-本地 Office SharePoint Server 网站-下拉- -编辑-爬网计划-完全(增量)爬网-创建计划 - 对该内容源启动完全爬网-勾选上。 一、 爬网设置ÿ…
1093 Count PAT‘s
这题出现在“活用递推”专题下面，所谓递推就是这一步的结果和上一步的结果有直接联系。对于本题来说，从左到右，记到当前位置，一共出现的P的个数，如果当前位置是P，则个数就是上一位的加1，否则等于…
拜托，面试别再问我时间复杂度了！！！
最烦面试官问，“为什么XX算法的时间复杂度是OO”，今后，不再惧怕这类问题。 快速排序分为这么几步： 第一步，先做一次partition； partition使用第一个元素tarr[low]为哨兵，把数组分成了两个半区&a…
C#和JavaScript的简单互交
转自：http://cgxcn.blog.163.com/blog/static/132312422009426112558831/ 1.asp.net呼叫js Response.Write("<script languagejavascript>"); Response.Write("alert(登峰欢迎您 );" ); …
读阮一峰对《javascript语言精粹》的笔记，我有疑问。
《javascript语言精粹》是一本很棒的书籍，其中作者在附录列出了12种他所认为的javascript语言中的糟粕。 我最近开始跟读前端前辈的博客，其中读到了阮一峰的《12种不宜使用的Javascript语法》，有一个疑问： 文如下： 9. …
1008 Elevator
思路如下：用一个整型数组存楼层，0号元素为0(开始停在0层)，每读入一个元素，和上一个比较，更大说明是上升，总时长加上楼层差*6，反之说明是下降，总时长加上楼层差*4。最后再管停留时间&…
软件安全性能測试（转载）
近来，在我负责的公司某软件产品的最后測试工作，经常被问到这样一个问题：在做測试过程中，我们的软件产品在安全性方面考虑了多少？应该怎样測评一个软件究竟有多安全？ 这个软件因为涉及客户商业上重要的…
org.springframework.data.redis 一次连接获取特定key所有k-v(pipeline）
2019独角兽企业重金招聘Python工程师标准>>> 当我们需要一次性获取在redis中以hash方式存储的所有key-value时，我们可以使用下面的方式来获取。 public void testGetMore() throws IOException {RedisCallback<List<Object>> pipelineCallba…
[网络应用]Flash中鼠标手势及Ctrl+T问题{Firefox}
想说这个问题很久了，也是对Flash的一点点小小的不满。 当你在浏览youku，56，Youtube，土豆，Kou6上的视频时，是不是会发现你的CtrlT命令不凑效了。 当你在打开一个Flash全站时，或者鼠标焦点在一个令…
(C++)一行代码递归实现辗转相除法
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 int gcd(int a,int b){return !b?a:gcd(b,a%b); } 这里递归边界是 gcd(a,0)a; 递归式是 gcd(a,b)gcd(b,a%b);
【C#】Web页面传值小结-
1. 使用QueryString变量 QueryString是一种非常简单的传值方式，他可以将传送的值显示在浏览器的地址栏中。如果是传递一个或多个安全性要求不高或是结构简单的数值时，可以使用这个方法。但是对于传递数组或对象的话，就不能用这个方法了…
分享：用promise封装ajax
用promise封装ajaxvar ajaxOptions {url: url,method: GET,async: true,data: null,dataType: text, } function ajax(protoOptions) {var options {};for(var i in ajaxOptions){options[i] protoOptions[i] || ajaxOptions[i];}return new Promise(function(resolve, reje…