免费预览已结束,剩余1页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
选择排序和冒泡排序算法的几种改进与分析第28卷第2期2010年4月运城学院学报JournalofYunchengUniversityVo1.28No.2Apr.2010选择排序和冒泡排序算法的几种改进与分析万小红,杨玉丽(运城学院公共计算机教学部,山西运城044OOO)摘要:结合教学介绍了传统的选择排序算法和冒泡排序算法,根据可以同时选择出最大数和最小数的特点提出了双向的选择排序;同时也将这一思想用到冒泡法中,便有了双向冒泡法;而新的冒泡排序法则是将选择法中的标记位置的思想和传统冒泡排序思想相结合的一种排序方法.最后经过算法分析得出,改进的算法的时间复杂度都比传统排序方法有所改善.关键词:选择排序;冒泡排序;时间复杂度中图分类号:O156.4文献标识码:A文章编号:10088008(2010)020042020.引言排序是数据处理中经常使用的一种重要的运算,如何进行排序,特别是高效率的排序是计算机研究的重要课题之一.排序的功能是将一个数据元素(记录)的任意序列,重新排序成一个按关键字有序排列的序列.一个好的排序算法不仅可以使信息查找的效率提高,而且还直接影响着计算机的工作效率.而选择排序和冒泡排序就是众多排序算法中比较常用的两种,也是教学过程中必选的教学项目.在以下的算法中选择的数据序列的长度n均为10.1.选择法排序1.1传统的选择法排序假定序列中有n个数,传统的选择法排序是对n个数进行若干轮的处理,每一轮都从ni+1个数中选择出最小的数,并记下该数的位置,最后出了循环之后用这个位置上的数与第i个位置上的数进行交换,这样每一轮之后都能找到一个最小数,如此反复之后就实现了最终的排序.具体的算法如下Fori=1To9选择法排序m=i用n来记录要交换的位置Forj=i+1To10Ifb(m)>b(j)Thenm=jNextt=b(m):b(m)=b(i):b(i)=tNext1.2双向的选择排序算法从上面的传统的选择排序算法中可以看出,传统的排序实际是利用打擂台的方法,经过不断的比较交换,在一轮的排序结束之后只能选择出一个最小数并将其与本轮次的最前位置上的数进行交换,如果在选择出最小数的同时,也能选择出最大数并将其与本轮次的最后位置上的数进行交换,这样就使排序所需的轮次减少了一半.这样在排序的一个轮次中就确定了最大和最小值,我们可以将这种方法称为双向的选择排序算法.具体的算法实现如下:Fori=1Tb5b(i)>b(10一i+1)Thent=b(i):b(i):b(10一i+1):b(10一i+1=tEndIfForj=i+1To10一ib(j)<b(i)Thent=b(i):b(i)=b(j):b(j)=tEndIfb(j)>b(10一i+1)Thent=b(j):b(j)=b(10一i+1):b(10一i+11=tEndNextNext2.冒泡排序算法2.1传统的冒泡排序算法假定序列中n个数,要进行从小到大的排序.(1)第一轮冒泡排序首先比较第一个数与第二个收稿日期:20100227作者简介:万小红(1980一)女,宁夏平罗人,山西运城学院公共计算机教学部助教.?42?数,若为逆序,则交换,然后比较第二个数与第三个数,依次类推,直至第n一1个数和第n个数比较完为止,结果最大的数被安置在最后一个元素的位置上,也就是沉底;(2)第二轮冒泡排序与前一轮进行相同的比较,结果使次大的数沉底,被安置在第n一1个元素的位置:(3)重复上述过程,共经过n一1趟冒泡排序后,排序结束.具体的排序算法如下:Fori=1To9冒泡排序Forj=10Toi+1Step一1Ifb(j)<h(j一1)Thent=b(j):b(j)=b(j一1):b(j一1)=tNextjNexti2.2双向冒泡排序算法我们分析上述算法思想可以发现,传统的冒泡法是从一端开始比较的,经过第一轮的比较之后使得最大的数下沉到最底端,如此重复循环使得排序完成.我们可以考虑,在实现从一端开始下沉大数的同时,从另一端也进行起泡,让小数上升,即实现双向起泡.具体的算法如下:Fori=1To5双向的冒泡排序算法b(i)>b(10一i+1)Thent=b(i)lb(i)=b(10一i+1):b(10一i+1)=tEndIfForj=i+1To10一ib(j)<b(i)Thent=b(i)lb(i)=b(j):b(j)=tEndIfIfb(j)>b(10一i+1)Thent=b(j):b(j)=b(10一i+1):b(10一i+1=tEndIfNextNext2.3一种新的冒泡法排序在传统的选择排序中,在内循环中找到一个最小数,并记下它的位置,出了循环之后,然后用这个位置上的数与第一个位置上的数进行交换.再考虑冒泡排序的算法思想,发现在每一轮的比较交换中都有重复的比较交换,可以结合上面选择法的思想,在内循环中标示出交换发生的位置,这样可以避免一些重复的比较交换,具体的算法如下:Fori=1To9改进的冒泡法排序n=n+lForj=10TonStep一1m:m+1b(j)<b(j一1)Thent=b(j)b(j)=b(j一1)b(j一1)=tn=j记下交换发生的位置EndTfNextjNexti_3.算法分析比较传统的选择排序算法和双向选择排序算法,双向选择排序算法的比较次数比传统的选择排序算法的比较次数少了一半,在最坏的情况下两个的比较次数都是n(n一1)/2,故两个算法的平均时间复杂度都为O(n).传统的冒泡排序法整个的排序过程需要n一1轮,而双向冒泡排序只需要n/2轮,若记录的初始状态是正序(从小到大)的,则一轮扫描即可完成排序,所需的关键比较和记录移动的次数分别达到最小值n一1和0.即双向冒泡算法最好的时间复杂度为O(n);若初始记录是反序(从大到小)的则需要进行n/2轮排序.对于新的冒泡排序算法来说若记录的初始状态是正序(从小到大)的,则一轮扫描即可完成排序,所需的关键比较和记录移动的次数也分别达到最小值n一1和0,即算法最好的时间复杂度为O(n);如果初始记录是反序(从大到小)的,则需要进行n一1轮排序,每轮排序要进行ni次的比较,且每次比较都必须移动三次数据来达到交换数据位置,在这种情况下比较和移动次数达到最大值:分别为n(n一1)/2和3n(n一1)/2.4.结束语对于排序问题,解决的方法有很多种,而选择排序算法和冒泡排序算法作为众多排序算法中尤其在程序设计教学中是比较典型的两个算法,利用简单选择法的排序思想为前提引出冒泡排序算法的思想,能使学生较快的理解这两个简单的算法,同时通过两个排序算法的结合和比较提出新的改进算法,从而便于学生对这些排序算法思想的巩固和掌握.参考文献:1张乃孝.算法与数据结构一c语言描
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- (完整版)叉车考试试题(含答案)
- 2024年海洋知识竞赛题库及答案
- (2025年)消防安全培训试题附答案
- (2025年)输血技术规范培训考试试题附答案
- 2025 年六小证考试题目及答案
- 3-6岁儿童学习与发展指南测试题(附答案)
- (2025年)泸州市省直机关公开遴选公务员笔试题及答案解析
- 2020年全国企业安全生产知识竞赛必答题库及答案(共150题)
- 关于2026年部分产品市场推广计划洽商函(5篇)范文
- 2026年注册建筑师精炼技术题库带答案
- 2026中国邮政联合校园招聘笔试参考题库(含答案解析)
- 宁夏吴忠市盐池县2026年社区工作者招聘考试试卷-含答案解析
- (一模)嘉兴市2026-2027学年第一学期高三教学质量检测语文试卷(含答案)
- 2026中国洗衣干衣行业市场现状需求分析投资布局发展策略研究文献
- 2027年湖北交通投资集团有限公司秋季校园招聘131人笔试备考题库及答案解析
- 2026山东青岛水务集团有限公司招聘笔试历年参考题库附带答案详解
- 2026年党支部基层总结报告
- 特香型白酒的讲解
- 中国电信理工综合类笔试题库
- T∕CCEAS008-2026 建设工程造价咨询成果文件质量标准
- 2018 机械通风冷却塔 第1部分:中小型开式冷却塔
评论
0/150
提交评论