- 1、本文档共78页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
查找与排序查找
查找与排序 测试1 测试2 排序的分类 排序的稳定性 插入类排序 主要思想: 从数组的第2号元素开始,顺序从数组中取出元素,并将该元素插入到其左端已排好序的数组的适当位置上,使插入后的序列仍然是个有序序列 平均时间复杂度:O(n2) 当数据的初始状态已有序时,最小比较次数为n-1次,且不发生数据记录的移动,此时算法的时间复杂度为O(n)。 当n不大时,插入排序的结果也是十分令人满意的. 稳定性:稳定的排序方法 测试3(06年初赛试题) 希尔排序 希尔排序又称缩小增量排序,它是对简单插入排序的改进。 基本思想是: 首先按增量将待排序列的元素分组, 对同一分组内的元素执行插入排序, 然后逐渐缩小增量将待排序列分组, 执行上述过程,直到增量为1时,最后进行一次插入排序,此时得到的序列就是一个有序序列。 习题: 4、设有关键码序列(17,8,3,25,16,1,13,19,18,4,6,21),要按关键码值递增的次序排序,用初始增量为4的希尔排序法,一趟扫描后的结果是 。 交换类排序 交换排序的特点在于交换。 有冒泡排序和快速排序两种。冒泡排序法是一种简单的交换排序法,快速排序是在冒泡排序法基础上改进的交换排序法。 冒泡排序 快速排序 稳定性:稳定的排序方法 for i := 1 to n do for j := 1 to n-i do if a[j] a[j+ 1] then Swap(a[j] , a[j+1]); 习题 用冒泡排序算法对数据2,37,42,19,27,35,56,44,10进行从小到大排序,在将最大的数“沉”到最后时,数的顺序是 。 快速排序 快速排序又称划分交换排序,它能够通过比较不相邻的两个元素从而一次消除多个逆序。 基本思想是 (由小到大) 在待排序的线性表中任选一个元素T 以它为基准比较表中的所有元素,通过交换将线性表中比T大的元素都放在T的后面,比T小的元素都放在T的前面,从而将整个表分解成三部分: 比T小的元素组成的子表、 T、比T大的元素组成的子表。 然后再将前后两个子表重复上述过程,直到整个线性表有序。 快速排序 原理: (1)把N个数存放在数组S中,当前集合为S中所有数。 (2)把当前集合第一个数定为标准数K,把S分为两个子集,左边子集S1为小于等于K的数,右边子集S2为大于等于K的数。这一操作是这样完成的: 设定集合第一个数作为标准数K,设定指针I、J,I指向集合第一个数,J指向集合最后一个数; 把J向左移(J:=J-1),直到找到一个S[J]=K,则交换S[I]与S[J]的位置,并把I后移(I:=I+1); 把I向右移(I:=I+1),直到找到一个S[I]=K,则交换S[I]与S[J]的位置,并把J前移(J:=J-1); 重复B、C直到I=J。 (3)依次把S1、S2作为当前集合,以第一个数作为标准数K,重复第2步,直到S1、S2及其产生的子集元素个数为1。 快速排序过程: 初始序列 [35 28 46 17 15] i j [15 28 46 17 35] 比较i和j,不满足条件 i j i=i+1 [15 28 46 17 35] 比较i和j,满足条件交换 i j j=j-1 [15 28 35 17 46] 比较i和j,满足条件交换 i j i=j时结束 一趟排序后 [15 28 17 ] 35 [46] 二趟排序后 15 [28 17 ] 35 46 三趟排序后 15 [17 ] 28 35
文档评论(0)