《SORT解题报告》PPT课件_第1页
《SORT解题报告》PPT课件_第2页
《SORT解题报告》PPT课件_第3页
《SORT解题报告》PPT课件_第4页
《SORT解题报告》PPT课件_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、SORT 解题报告,10软(3)杨楠,题目描述,1.插入排序步骤3的总共移动次数 2.冒泡排序步骤1的总共的交换次数 3.快速排序所有执行步骤2中，比基准值小的个数总和 4.归并排序中，所有的两两归并的两个序列中，第一序列的第一个元素比第二个序列的第一个元素大的次数,题目分析,做法：写出四种排序，在题目要求的地方计数。,题目分析,因为要进行四种排序，所以要保存原数组。,题目分析,快速排序第二个要求： 2. 重新排序数列，按顺序将所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 题目要

2、求按照顺序将所有的元素进行一次分区操作，即分区后，比基准小的元素相对位置和比基准大的元素相对位置要和原来的一样。 即 5 2 8 9 1，分区后只能是 2 1 5 8 9，而不能是 1 2 5 8 9或其他的。,题目分析,partition ： for( i = left + 1; i k ; -j ) a j = a j-1 ; +k ; 这样partition时间复杂度就大于O(N)，最坏会是O(N2)，书中给出的方法是O(N)的。,题目分析,归并排序要按照题目给的例子用循环写。 比如五个数 1 2 3 4 5 循环的话第一次归并是1 2 3 4 5，第二次归并是1 2 3 4 5，第三次是1 2 3 4 5 而用递归的话，递归下去是分成1 2 3 4 5，再分成 1 2 3 4 5 ，这样第一次归并变成了1 234 5，第二次是1 2 34 5，第三次是1 2 3 4 5，这样答案会错掉。,题目分析,for( k = 1 ; k n ; k *= 2 ) for( i = 0 ; i + k n ; i += 2 * k ) Merge(a,b,i,i+k-1,Min(i+2*k-1,n-1); ,题目分析,由于冒泡排序和插入排序每次交换都是交 换相邻的两个，每交换

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论