实验二分治法归并排序教学内容
更新时间:2023-05-02 12:02:01 阅读量: 实用文档 文档下载
- 实验二分法推荐度:
- 相关推荐
实验二分治法归并排
实验二分治法归并排序
一、实验目的及要求
(-)实验目的
1、熟悉归并排序算法过程;
2、验证归并排序算法复杂度。
(二)实验要求
1、合理添加计数器
2、实现归并排序算法并验证复杂性
3、掌握递归方法
二、实验内容与步骤
1、设计归并排序算法
2、在算法中添加计数器,累计比较次数(注意计数器要用全局变量)和递归调用次数
3、完成算法分析
4、用JAVA实现算法,分别运行5?10个记录的排序,分析比较次数和规模之间的尖系
5、判断运行结果是否与分析结果一致
6、和实验一的结果比较复杂性差别(用图表)
三、实验结果与分析
1、代码如下:(n=8 )
import java.util.Sea nner;
public class GuiB in gPaiXu {
static int com=0, use =0; //com 表示比较次数,use 表示递归调用次数public static void main ( Stri ng[] args) {
int [] a = new int [8];
Seanner sea n = new Seanner (System, in);
int r=0, t=a. len gth -1;
int num;
System, out .printin ( ”请输入8个整数:”);
〃将输入的每个数记入数组
for (int i=0;i
num = sea n.n ext I nt ();
a[i] = num;
}
〃递归调用归并排序
PaiXu (a,r,t);
仅供学习与交流,如有侵权请联系网站刪除谢谢
〃输出各个数据
System, out .println( ”该8个整数从小到大是:”);
for (int i=0;i
System, out .print(a[i]+ ””);
}
System, out .println( "\n 比较次数:"+com);
System, out .println( ”递归调用次数:”+use );
}
〃归并排序
public static void PaiXu( int b[], int r, int t){ use ++; 〃每递归调用一次,加一int s;
int [] temp = new int [b. Iength ];
if (r==t) return ;
else {
s=(r+t)/2;
PaiXu (b,r,s);
PaiXu (b,s+1 ,t);
GuiBing (b,temp,r,s,t);
for (int i=r;iv=t;i++) b[i]=temp[i];
}
}
〃归并
public static void GuiB ing( int b[], int temp[], int r, int
s, int t){
int i=r,j=s+1 ,k=r; while (i<=s && j<=t){
if (b[i]<=b01)
temp[k++]=b[i++];
else
temp[k++]=b[j++];
com++; 〃每比较一次,加一
}
while (i<=s)
temp[k++]=b[i++];
while (j<=t)
temp[k++]=b[j++];
}
、算法分析:设待排序记录个数为,该算法的基本语句是归并算法的循环体的比较语句
“if (b[i]<=b[j]) temp[k++]=b[i++];
else temp[k++]=b[j++]; ”‘
其执行次数为:0(n],即执行一趟归并算法的时间复杂度为0(D)则归并排序算法存在以下推式:k(D)= { 2T(n/2) + n n> 1所以,归并排序算法的时间复杂度为'I ■ 12。
另外,归并排序算法递归调用次数为II 。
3、结果如下:
:应间霆独詔OC㈣离明呈控制台乂v已蜒止a GuiBingPaiXu [J A va应凫序I D:\Pn n=5
|L闫圖@ Javadoc空,芦明胃輦制台总1
卜已蟀止》GuiB ngPaiXu [Java应用程请愉人5个藝厂
陳5个整数从小到犬是;
12 3 4 5
比较次数:7递归调用次数油fEEfiffil @ Javadoc^〉旦疑占戈台帯
GuiB A ngPaiXu [Java 应用琶克请输刃、整数:
4
5
3
怜牙个整数从小到大是:
1 2a4S
比较次数;7递归调用次
数洱
b叵題|磁Javadoc |亀.芦朋貝圜4台滋弐已馆止* GuiBingPaiXu [Jnv□应用程序| 请输入音个整数:
4
6
怪个整勘从小到大站比sass :递归调用
次数:耳
1 <
淤个整對从小到犬是,
12345673
比较次数:L7 递归调用
衣数;久5
JI
n=8
4、与选择排序的对比(时间复杂度)
从时间复杂度上看,归并排序的要小于选择排序,
并且实际上,
在问题规模相同而待排序记录顺序的整齐程度有所差异的 情况下,
选择排序是不论待排序记录顺序的整齐程度如何,其时间复杂度都是固定的;
归并排序是若待排序记录顺序越整齐,其时间复杂度越小,
匚问题刼Javads 声明□控制台疣I
GuiBingPaiXu [Java 直更程书 D:\Proj
请输入丄D 个整数:
1
2
佥问鬆切Javadoc 篦声琥旦控制台亦 R 已舞止* GuiBingPaiXu [Java 应用程序]D;\Pro 请输入丄诃整数: 10
陽丄D 个整数从小到大是:
1234567S9 比较次数:甫
递归调用次数:甫
10 该久0个整数从小到犬是: 1234S67B9 比较次数:凸 递归调用次数;19 由n = 5,6, -,10等数据的运行结果可知'
10
n=10
10
5
随着问题规模n 的增加,其时间复杂度(比较次数的执行)也增加,所以,该算法分析的判断正确。
正在阅读:
实验二分治法归并排序教学内容05-02
2014年广西公务员考试行测言语理解数量关系资料分析模拟试题及答03-08
武汉大学创业教育工作总结03-17
乡间的四季作文600字07-05
2015年湖南省岳阳市普通高中学业水平考试通用技术考查试卷及答案09-22
中国古代三部科技著作09-03
网络销售学生实习报告04-17
成长的苦辣酸甜作文450字06-17
一年级上册三字经教案精讲12-23
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 归并
- 治法
- 教学内容
- 二分
- 排序
- 实验
- 第十八章电功率知识点归纳
- 欧美的工业革命教学设计 北师大版(新教案)
- 连锁超市三年发展战略规划
- 最新扬尘防治教育培训记录资料
- 金蝶K3系统总账模块培训教材
- 【完整版】2019-2025年中国连锁超市行业企业发展方向及匹配能力建设研究报告
- 国内外营商环境评价指标体系的比较解读
- 水利专业技术工作总结中级职称
- 【完整版】2019-2025年中国大型超市行业价值竞争策略制定与实施研究报告
- 广东省珠海市2021届高三上学期期末学业质量监测数学理试题Word版含解析
- 工程项目成本核算表格.docx
- 【完整版】2019-2025年中国奶茶行业市场差异化竞争战略制定与实施研究报告
- 2016年碳纤维自行车发展现状及市场前景分析 (目录)
- 【完整版】2019-2025年中国速冻汤圆行业服务竞争策略制定与实施研究报告
- 2020年公需科目考试答案.2020年中央经济工作会议精神解读(中)
- 第一章第三节地图的阅读 (1)
- 2018-2019年高中生物河南高考精品汇编【71】含答案考点及解析
- 【完整版】2019-2025年中国移动电子商务行业发展趋势预测研究报告
- Excel_VBA_编程教程(完整版)(最新完整版)
- 2020年度社会工作者工作计划