【最新】《算法导论》学习总结——快速排序 (2)doc_第1页
【最新】《算法导论》学习总结——快速排序 (2)doc_第2页
【最新】《算法导论》学习总结——快速排序 (2)doc_第3页
全文预览已结束

下载本文档

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

文档简介

1、算法导论学习总结快速排序 一、冒泡排序 已知一组无序数据a1、a2、an，需将其按升序排列。首先比较a1与a2的值，若a1大于a2则交换两者的值，否则不变。再比较a2与a3的值，若a2大于a3则交换两者的值，否则不变。再比较a3与a4，以此类推，最后比较an-1与an的值。这样处理一轮后，an的值一定是这组数据中最大的。再对a1an-1以相同方法处理一轮，则an-1的值一定是a1an-1中最大的。再对a1an-2以相同方法处理一轮，以此类推。共处理n-1轮后a1、a2、an就以升序排列了。 优点：稳定； 缺点。慢，每次只能移动相邻两个数据。 二、选择排序 每一趟从待排序的数据元素中选出最小（或

2、最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： 初始状态。无序区为r1.n，有序区为空。 第1趟排序 在无序区r1.n中选出关键字最小的记录rk，将它与无序区的第1个记录r1交换，使r1.1和r2.n分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 第i趟排序 第i趟排序开始时，当前有序区和无序区分别为r1.i-1和r（1in-1）。该趟排序从当前无序区中选出关键字最小的记录rk，将它与无序区的第1个记录r交换，使r1.i和r分别变为记录个数增加1

3、个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 优点：移动数据的次数已知（n-1次）； 缺点。比较次数多。 三、插入排序 已知一组升序排列数据a1、a2、an，一组无序数据b1、b2、bm，需将二者合并成一个升序数列。首先比较b1与a1的值，若b1大于a1，则跳过，比较b1与a2的值，若b1仍然大于a2，则继续跳过，直到b1小于a数组中某一数据ax，则将axan分别向后移动一位，将b1插入到原来ax的位置这就完成了b1的插入。b2bm用相同方法插入。（若无数组a，可将b1当作n=1的数组a） 优点：稳定，快； 缺点。比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。 四、缩小增量排序 由希尔在1959年提出，又称希尔排序（shell排序）。 已知一组无序数据a

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

温馨提示

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

最新文档

评论

0/150

提交评论