欢迎来到课桌文档! | 帮助中心 课桌文档-建筑工程资料库
课桌文档
全部分类
  • 党建之窗>
  • 感悟体会>
  • 百家争鸣>
  • 教育整顿>
  • 文笔提升>
  • 热门分类>
  • 计划总结>
  • 致辞演讲>
  • 在线阅读>
  • ImageVerifierCode 换一换
    首页 课桌文档 > 资源分类 > PPT文档下载  

    数据结构(Java版)排序.ppt

    • 资源ID:229769       资源大小:429KB        全文页数:20页
    • 资源格式: PPT        下载积分:10金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要10金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    数据结构(Java版)排序.ppt

    排序,排序,2,基本概念,排序:将n个数字按一定顺序排列(比如:升序,或者降序)班上有30个学生,按照学号进行由小到大的排序,排序,3,基本概念,内部排序:若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序 外部排序:若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序,排序,4,几种常用的排序方法,冒泡排序选择排序快速排序插入排序希尔排序归并排序,排序,5,冒泡排序,基本思想:对所有相邻记录的关键字值进行比较,如果是逆序(ajaj+1),则将其交换,最终达到有序化,排序,6,冒泡排序实例,初始关键字序列:51 33 62 96 87 17 28 51第一趟排序结果:33 51 62 87 17 28 51 96 第二趟排序结果:33 51 62 17 28 51 87 96 第三趟排序结果:33 51 17 28 51 62 87 96 第四趟排序结果:33 17 28 51 51 62 87 96 第五趟排序结果:17 28 33 51 51 62 87 96 第六趟排序结果:17 28 33 51 51 62 87 96,51,33,62,96,87,28,17,51,33,51,62,87,17,51,28,96,排序,7,课堂练习与算法设计,一组关键字(19,01,26,92,87,11,43,87,21),进行冒泡排序,试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=1 1 19 26 87 11 43 87 21 92 i=2 1 19 26 11 43 87 21 87 92 i=3 1 19 11 26 43 21 87 87 92 i=4 1 11 19 26 21 43 87 87 92 i=5 1 11 19 21 26 43 87 87 92 i=6 1 11 19 21 26 43 87 87 92i=7 1 11 19 21 26 43 87 87 92i=8 1 11 19 21 26 43 87 87 92,算法设计:for(int i=1;iaj+1)交换aj和aj+1,编程实现,排序,8,选择排序,基本思想:依次从待排序记录序列中选择出关键字值最小(或最大)的记录、关键字值次之的记录、,并分别将它们定位到序列左侧(或右侧)的第1个位置、第2个位置、,从而使待排序的记录序列成为按关键字值由小到大(或由大到小)排列的有序序列。选择排序种类:直接选择排序和堆排序,排序,9,直接选择排序实例,初始关键字序列:51 33 62 96 87 17 28 51 第一趟排序后:17 33 62 96 87 51 28 51 第二趟排序后:17 28 62 96 87 51 33 51 第三趟排序后:17 28 33 96 87 51 62 51第四趟排序后:17 28 33 51 87 96 62 51第五趟排序后:17 28 33 51 51 96 62 87 第六趟排序后:17 28 33 51 51 62 96 87 第七趟排序后:17 28 33 51 51 62 87 96,排序,10,课堂练习与算法设计,选择排序过程:34 12 45 21 87 26 3i=1 3 12 45 21 87 26 34i=2 3 12 45 21 87 26 34i=3 3 12 21 45 87 26 34i=4 3 12 21 26 87 45 34i=5 3 12 21 26 34 45 87i=6 3 12 21 26 34 45 87,算法设计:n=a.length;for(i=0,iaj)min=j;if(min!=i)交换amin和ai,排序,11,插入排序,主要思想:不断地将待排序的数值插入到有序序列中,使有序序列逐渐扩大,直至所有数值都进入有序序列中位置 插入排序种类:直接插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序,排序,12,直接插入排序,基本思想:将记录Ri插入到有序子序列R0.i-1中,使记录的有序序列从R0.i-1变为R0.i,排序,13,直接插入排序实例,初始关键字序列:51 33 62 96 87 17 28 51i=1(33)33 51 62 96 87 17 28 51i=2(62)33 51 62 96 87 17 28 51i=3(96)33 51 62 96 87 17 28 51i=4(87)33 51 62 87 96 17 28 51i=5(17)17 33 51 62 87 96 28 51i=6(28)17 28 33 51 62 87 96 51i=7(51)17 28 33 51 51 62 87 96,排序,14,一组关键字(19,1,26,92,87,11,43,87,21),进行插入 排序,试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=1 1,19,26,92,87,11,43,87,21i=2 1,19,26,92,87,11,43,87,21i=3 1,19,26,92,87,11,43,87,21i=4 1,19,26,87,92,11,43,87,21i=5 1,11,19,26,87,92,43,87,21i=6 1,11,19,26,43,87,92,87,21i=7 1,11,19,26,43,87,87,92,21i=81,11,19,21,26,43,87,87,92,算法设计:void insertSort(int a)n=a.length;for(i=1;in;i+)将ai插入到a0ai-1中,保持原来的排序 1 在a0ai-1中找到插入的位置j 2 把ajai-1逐个后移一个位置(ai-1移到ai,aj移到aj+1)3 把ai放到aj处,课堂练习与算法设计,排序,15,快速排序,基本思想:首先将待排序记录序列中的所有记录作为当前待排序区域,从中任选取一个记录(通常可选第一个记录),以它的关键字作为枢轴(或支点)(pivot),凡其关键字小于枢轴的记录均移动至该记录之前,反之,凡关键字大于枢轴的记录均移动至该记录之后,排序,16,快速排序一趟排序过程,初始关键字序列:51 33 62 96 87 17 28 51R0=51 i j第一次交换之后:28 33 62 96 87 17 28 51 i j第二次交换之后:28 33 62 96 87 17 62 51 i j第三次交换之后:28 33 17 96 87 17 62 51 i j 第四次交换之后:28 33 17 96 87 96 62 51 i j 完成一趟排序:28 33 17 51 87 96 62 51,排序,17,快速排序结果,初始关键字序列:51 33 62 96 87 17 28 51一趟排序之后:28 33 17 51 87 96 62 51分别进行快速排序:17 28 33 51 62 87 96 51 62 有序序列:17 28 33 51 51 62 87 96,排序,18,课堂练习与算法设计,给出一组关键字,快速排序的每一趟的排序结果:46,58,15,45,90,18,10,62,87,23t=46 23,58,15,45,90,18,10,62,87,23 i jt=46 23,58,15,45,90,18,10,62,87,58 i jt=46 23,10,15,45,90,18,10,62,87,58 i jt=46 23,10,15,45,90,18,90,62,87,58 i jt=46 23,10,15,45,46,18,90,62,87,58 i j,算法设计:void quickSort(int a,int s,int t)if(st)k=partion(a,s,t);quickSort(a,s,k-1)quickSort(a,k+1,t)int partion(int a,int l,int r)temp=al;j=r;i=l;while(ij)从j位置逐个比较temp和aj,把比temp小的元素调到ai处;从i位置逐个比较temp和ai,把比temp大的元素调到aj处;return j;,排序,19,排序方式比较,排序,20,综合项目实践,164页实战演练:设计一个项目可以对5000个数进行排序,计算并比较各种排序的时间。运行界面如下.,

    注意事项

    本文(数据结构(Java版)排序.ppt)为本站会员(夺命阿水)主动上传,课桌文档仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知课桌文档(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-1

    经营许可证:宁B2-20210002

    宁公网安备 64010402000986号

    课桌文档
    收起
    展开