- 1、本文档共11页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
深圳大学算法设计与杨煊实验一讲述
深 圳 大 学 实 验 报 告
课程名称: 算法设计与分析
实验项目名称: 排序算法性能分析
学院:
专业、班级:
指导教师: 杨 烜
报 告 人: 学号:
实验报告提交时间: 2015.4.3
教务处制
一、实验目的与实验环境
实验目的:
1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理
2. 掌握不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
实验环境:VC++ 6.0
二、实验原理与算法描述
算法(1)选择排序 SelectSort(A[0...n-1],n)
//利用选择排序对给定的数组排序
//输入:一个可排序数组A[0...n-1]
//输出:非降序排列的数组A[0...n-1]
for i-0 to n-2 do
min-i
for j-i+1 to n-1 do
if A[j]A[min]
min-j
swap A[i] and A[min]
理论效率:C(n) ∈θ(n^2),不稳定算法
算法(2)快速排序 QuickSort(A[0...n-1],n)
//利用快速排序对给定的数组排序
//输入:一个可排序数组A[0...n-1]
//输出:非降序排列的数组A[0...n-1]
if lr
s-Partition(A[l...r]) //s是分裂位置
Quicksort(A[l...s-1])
Quicksort(A[s+1...r])
Partition(A[l...r])
//以第一个数为中轴,对子数组进行分区
//输入:数组A[0...n-1]中的子数组A[l...r],由左右下标l和r定义
//输出:数组A[l...r]的一个分区,分裂点的未知作为函数的返回值
p-A[l]
i-l;j-r+1
repeat
repeat i-i+1 until A[i]=P
repeat j-j-1 until A[j]=P
swap(A[i],A[j])
until i=j
swap (A[i],A[j]) //当i=j撤销最后一次交换
swap (A[l],A[j])
return j
理论效率:C(n) ∈θ(nlnn),不稳定算法
算法(3)合并排序 MergeSort(A[0...n-1])
//利用合并排序对给定的数组排序
//输入:一个可排序数组A[0...n-1]
//输出:非降序排列的数组A[0...n-1]
if n1
copy A[0...?n/2?-1] to B[0...?n/2?-1]
copy A[?n/2?...n-1] to C[0...?n/2?-1]
Mergesort(B[0...?n/2?-1])
Mergesort(C[0...?n/2?-1])
Merge(B,C,A)
Merge(B[0...p-1],C[0...q-1],A[0...p+q-1])
//将两个有序数组合并为一个有序数组
//输入:两个有序数组B[0...p-1],C[0...q-1]
//输出:A[0...p+q-1]中已经有序存放了B和C中的元素
i-0;j-0;k-0
while ip and jq do
if B[i]=C[j]
A[k]-B[i];i-i+1
else
A[k]-C[j];j-j+1
k-k+1
if i=p
copy C[j...q-1] to A[k...p+q-1]
else
copy B[i...p-1] to A[k...p+q-1]
理论效率:C(n)∈θ(nlogn),稳定算法
算法(4)冒泡排序 BubbleSort(A[0...n
您可能关注的文档
- 函数的表示法(一)解读.ppt
- 函数的图像解读.ppt
- 几种新型农药中毒的诊治金平(修改)解读.ppt
- 出口退税申报系统培训解读.pptx
- 函数表示与定义域值域解读.ppt
- 函数表示法解读.ppt
- 深受孩子喜爱的3款超萌面包讲述.docx
- 深化党建制度改革3讲述.ppt
- 深圳四年级心理健康教案讲述.doc
- 函数的表示法解读.ppt
- [专精特新]金华永和氟化工有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]重庆升光电力印务有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]无锡巨力重工股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]江西凯安新材料集团股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]浙江永昌电气股份有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]苏州中创铝业有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]杭州汽轮铸锻有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]浙江美声智能系统有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]汕头市虹桥包装实业有限公司行业竞争力评级分析报告(2023版).pdf
- [专精特新]江西亚中电子科技股份有限公司行业竞争力评级分析报告(2023版).pdf
最近下载
- 2023河南郑州航空港经济综合实验区管委会招聘14人高频笔试、历年难易点考题(共500题含答案解析)模拟试卷.docx
- 2024-2030年中国双皮奶市场专题研究及市场前景预测评估报告.docx
- abaqus中英菜单对照.docx VIP
- AI技术在提高课堂效率中的应用教学研究课题报告.docx
- 10S505柔性接口给水管道支墩图集.docx
- 2023-2024年中医肛肠学(副高)考试高频题库(历年考点版)带答案解析篇.docx VIP
- 2023年中医肛肠学(副高)历年考试高频考点试题带答案解析.docx VIP
- 2023-2024年中医肛肠学(副高)考试高频题库(历年考点版)带答案解析版.docx VIP
- 2023-2024年中医肛肠学(副高)考试参考题库(历年高频考点版)带答案解析篇.docx VIP
- 七年语文《世说新语》二则课内外文言文比较阅读(原卷版+解析版).docx VIP
文档评论(0)