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

下载本文档

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

文档简介

1、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 = right ; +i ) if( a 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

提交评论