请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

斯坦福算法分析和设计_排序算法MergeSort

[复制链接]
查看: 76|回复: 0

2万

主题

2万

帖子

7万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
70839
发表于 2020-1-14 12:55 | 显示全部楼层 |阅读模式
MotivateMergeSort是个相对陈腐的算法了,为什么现在我们还要会商这么陈腐的工具呢?有几个原因原由:

  • 它固然年事很大了,可是在理论中不停被沿袭,仍然是很多步伐库中的标准算法之一。
  • 实现它的本质是分治脑筋,是一个明白分治算法脑筋的好例子,好动身点。
  • 本文会利用“递归树”来对它举交运转时候分析,后背会聚集这类思绪天生“主方式”。
题目
我的关键词 斯坦福算法分析和设想_排序算法MergeSort  热门消息 v2-9bbb15d3963812b6992fed3d49d2ade4
输入一个数组,数组里面的每个数字是不反复的,输出是已经排序好的数组。比如输入的是:
我的关键词 斯坦福算法分析和设想_排序算法MergeSort  热门消息 v2-7baabcf2272de5cbef80f78973127b88
盼望输出的是:
我的关键词 斯坦福算法分析和设想_排序算法MergeSort  热门消息 v2-c2e4ec05927961915f2259d3c67f757b
大要之前我们有所晓得一些排序算法,比如SelectionSort,扫描全数组找到最小元素,把它放到输出数组的第一位,接着扫描复制次小的元素,以此类推;比如BubbleSort,对相邻无序的元素举行比力,实行频频的交换,直到末端数组完成排序。等等。但这些算法的题目就是运转时候是平方级的。那我们来看看本日这个排序算法用更少的运转时候是怎样实现的。例子 想要明白MergeSort算法是怎样运转的,一个最简单的方式就是看看具体的例子。
我的关键词 斯坦福算法分析和设想_排序算法MergeSort  热门消息 v2-b6f8aa1a8bc7e7b6c102fffcf931f59c
团体进程就是:它把数组 [5, ,4, 1, 8, 7, 2, 6, 3] 别离为更小的数组(子题目)[5, 4, 1, 8] 和 [7, 2, 6, 3]排序,经过奇异的递归操纵,获得每个排序后的子数组,再将子数组合并起来。伪代码 将上面的图换成伪代码就是这样的进程
我的关键词 斯坦福算法分析和设想_排序算法MergeSort  热门消息 v2-bf442baaf9e7bfe00238da35671c749f
而这个Merge步伐怎样实现呢?由上面的图我们可以晓得,Merge的时候,实在输入两个已经排序好的数组C, D,再把它们排序输出到B。
我的关键词 斯坦福算法分析和设想_排序算法MergeSort  热门消息 v2-445ae6b83ff6d93d1d19b889de64315f
索引 k 操控的是输出数组,索引 i,j 操控的是已排序好的C和D子数组,都是从左向右扫描。每一次的for循环,实在就是找C和D中最小的数字,由于C和D是已排序好的数组,所以最小的数字就是i或j对应的元素。比力后把它放入输出数组B中,并将对应的索引+1,这样下次循环就跳过已复制的元素了。所以末端的数组B输出是顺次方式天生的。 算法分析我们先来对Merge步伐算算它的实行操纵数目。 第1,2行有一次赋值操纵。 第3行是一个for循环,每一个for循环里,有比力操纵(C和D(i)比力),赋值操纵(B[k]的赋值),递增操纵(i或j加1),循环变量k还要加1,所以每一次循环一共有4次操纵。一共就是4n+2次操纵,为了后背的盘算方便,当n>=1时,4n+2
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 淄博新闻网-淄博日报 淄博晚报 淄博财经新报 掌中淄博 淄博专业新闻资讯发布网站 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表