幻灯片 1

Size: px

Start display at page:

Download "幻灯片 1"

浦溆芮
7 years ago
Views:

1 1.3 查找与排序一查找查找, 也称为检索, 就是在一组同类型的数据元素中找出满足条件的元素这种操作可能成功 ( 找到 ), 也可能失败 ( 未找到 ) 通常把待查找的数据元素集合称为查找表下面介绍的查找是按关键字进行的关键字 (key) 是数据元素中能唯一标识一个数据元素 ( 或记录 ) 中某个 ( 些 ) 数据项

2 要衡量一种查找算法的优劣, 主要是看要找的值与关键字的比较次数为此, 引入平均查找长度的概念 : 对于一个含有 n 个元素的查找表, 查找成功时的平均查找长度可表示为 : ASL= 其中 : n pi c i i=1 p i 为查找第 i 个元素的概率, 且 n i=1 情形下我们认为查找每个元素的概率相等 p i =1/n p i =1 一般 n c i 为查找第 i 个元素所用的比较次数 ASL= ci /n i=1

3 1. 顺序查找顺序查找的基本思想 : 从表的一端开始, 顺序扫描线性表, 依次将扫描到的结点关键字和待找的值 K 相比较, 若相等, 则查找成功, 若整个表扫描完毕, 仍末找到关键字等于 K 的元素, 则查找失败顺序查找既适用于顺序表, 也适用于链表顺序查找的表中元素可以是无序的每个位置的查找比较次数为 C 1 =1,C 2 =2,, C n =n, 于是, 查找成功的平均查找长度为 : ASL=(1+2+ +n)/n=(n+1)/2 它的时间复杂度记为 O(n)

4 这就是说, 查找成功的平均比较次数约为表长的一半若 k 值不在表中, 则必须进行 n 次比较之后才能确定查找失败顺序查找的优点 : 算法简单, 对表结构无任何要求, 无论是用向量还是用链表来存放结点, 也无论结点之间是否按关键字有序或无序, 它都同样适用顺序查找的缺点 : 查找效率低, 当 n 较大时, 不宜采用顺序查找, 而必须寻求更好的查找方法

5 2. 二分查找二分查找, 也称折半查找二分查找有条件限制 : 要求表必须用向量作存贮结构, 且表中元素必须按关键字有序 ( 升序或降序均可 ) 排列二分查找的基本步骤 : 假设表 R[N] 中元素为升序排列待查值为 k 1)Low 1,High N 2)mid [( Low +High )/2] 3) 如果 R[mid].key =k 则查找成功, 结束否则若 R[mid].key>k, 则 High mid-1 否则 Low mid+1 4) 如果 Low High 则转 2) 否则查找失败, 结束

6 可以证明, 二分查找的平均查找长度约为 : ASL log 2 (n+1) 它的时间复杂度为 O(log 2 n) 二分查找的优点 : 查找效率高, 算法比较简单二分查找的缺点 : 要求表结构必须是用向量存放结点的, 且按查找关键字有序, 不便用于插入删除频繁的情况

7 3. 分块查找分块查找又称索引顺序查找分块查找的具体实现如下 : 将一个含有 n 个元素的主表分成 m 个子表, 并要求子表之间元素按关键字有序排列, 而各子表中元素可以无序, 然后建立索引表索引表中的每个索引项通常包含三个域 : 一是对应子表最大关键字的值 ; 二是子表的开始位置, 用来存储对应子表的第一个元素的存储位置 ; 三是子表的长度, 用来存储对应子表的元素个数在分块查找中, 首先在索引表中查找, 以确定待查的结点所在的块 ; 然后在确定出的块中进行顺序查找

8 分块查找的索引表是一个有序表, 故可以用二分查找来代替顺序查找实现索引表的快速查找例如, 给定关键字序列如下 : {18,7,26,34}, {42,36,70,60}, {83,90,78,74} 假设将该序序分成 3 个子表, 每个子表有 4 个元素, 则得到的主表和索引表为 : 12 个关键字序列的主表

9 按关键字序列递增得到的索引表 : index start length 分块查找的性能分析 : 设长度为 n 的线性表被均匀地分为 b 块, 每块有 s 个结点假设在每个位置查找的概率相等若顺序查找索引表, 则其平均查找长度为 : ASL=(n+s 2 )/(2s)+1 当 s= n 时,ASL 最小若二分查找索引表, 则其平均查找长度为 : ASL log 2 (n/s+1)+s/2

10 分块查找的优点 : 查找效率较高, 块内结点可无序, 插入删除时不必移动块内结点分块查找的缺点 : 增加了存放索引表的辅助空间及初始时对线性表分块排序的运算, 大量的插入删除可能导致各块内结点的个数很不均匀, 降低查找速度 4. 散列查找散列查找也称为哈希查找杂凑查找它既是一种查找方法, 又是一种存贮方法散列存贮的内存存放形式也称为散列表散列查找的性能 : 按理论分析, 它的时间复杂度应为 O(1), 它的平均查找长度应为 ASL=1, 但由于冲突的存在, 它的平均查找长度将会比 1 大

11 二排序排序 (Sorting) 是数据处理中一种很重要的, 同时也很常用的运算据统计, 一般数据处理工作 % 的时间都在进行排序排序就是把一组数据元素 ( 记录 ) 按照一个或多个域 ( 排序码 ) 的值的递增或递减的次序重新排列的过程待排序记录的集合称为文件若是按排序码升序排列的, 则称为升序表或正序表, 否则称为降序表或逆序表一般只讨论正序表因为排序码可以不是记录的关键字, 同一排序码值可能对应多个记录对于具有同一排序码的多个记录来说, 若采用的排序方法使排序后记录的相对次序不变, 则称此排序方法是稳定的, 否则称为不稳定的

12 按照排序过程中使用内外存的不同将排序方法分为内排序和外排序若排序过程全部在内存中进行, 则称为内排序 ; 若排序过程需要不断地进行内存和外存之间的数据交换, 则称为外排序内排序大致可分为 : 插入排序交换排序选择排序归并排序树形排序和分配排序等下面仅讨论内排序排序过程主要是对记录的排序码进行比较和记录的移动过程因此排序的时间复杂性可用算法执行中的数据比较次数及数据移动次数来衡量为简单起见, 我们直接将排序码写成一个一维整型数组的形式, 并且在没有声明的情形下, 所有排序都按排序码的值递增排列

13 1. 直接插入排序插入排序的基本思想是 : 把待排序的元素看成为一个有序表和一个无序表, 开始时有序表中只包含一个元素, 排序过程中每次从无序表中取出第一个元素, 把它插入到有序表中的适当位置上, 从而形成新的有序表, 这样, 直到把全部待排序的元素插入到有序表中为止按照在有序表中查找待排序元素的位置时所用的方法, 形成了多种插入排序算法下面仅介绍直接插入排序 : 直接插入排序是用顺序查找的方法查找待排序元素的位置的例如, 直接插入排序的执行过程如下图所示

14 R[1] R[2] R[3] R[4] R[5] R[6] 初始状态 (17 ) ( ) 3 第 1 次插入 (3 17) ( ) 第 2 次插入 (3 17 ) ( ) 14 第 3 次插入 ( ) ( 20 9)...

15 采用直接插入排序, 如果在初始状态下文件是正序的, 则每次插入就比较一次, 无需移动记录, 故 n- 1 次插入共需 n-1 次比较, 此时, 其时间复杂度为 O(n) 若在初始状态下文件是反序的, 则第 i 次插入就需比较 i 次, 移动 i 个记录, 故 n-1 次插入共需比较 n-1=(n 2 -n)/2 次, 此时, 其时间复杂度为 O(n 2 ) 该方法是稳定的 2. 交换排序交换排序的基本思想是 : 是通过对两两比较待排序元素的排序码, 若发现逆序则交换, 直到所有元素都排好序为止此处仅介绍起泡排序快速排序

16 起泡排序的过程

17 快速排序 (Quick Sort) 基本思想是任取待排序对象序列中的某个对象 ( 例如取第一个对象 ) 作为基准, 按照该对象的排序码大小, 将整个对象序列划分为左右两个子序列 : 左侧子序列中所有对象的排序码都小于或等于基准对象的排序码右侧子序列中所有对象的排序码都大于基准对象的排序码

18 基准对象则排在这两个子序列中间 ( 这也是该对象最终应安放的位置 ) 然后分别对这两个子序列重复施行上述方法, 直到所有的对象都排在相应位置上为止基准对象也称为枢轴 ( 或支点 ) 记录

19 快速排序的过程初始关键字 prikey 一次交换 21 二次交换三次交换四次交换完成一趟排序 * i j * 16 i j * 16 i j * i j * 49 i j * 49 i j

20 完成一趟排序 * 49 分别进行快速排序 * 49 有序序列 * 49

21 选择排序基本思想每一趟 ( 例如第 i 趟, i = 0, 1,, n-2) 在后面 n-i 个待排序记录中选出排序码最小的记录, 作为有序序列中的第 i 个记录待到第 n-2 趟作完, 待排序记录只剩下 1 个, 就不用再选了

22 直接选择排序 (Select Sort) 直接选择排序是一种简单的排序方法, 它的基本步骤是 : 1 在一组对象 V[i]~V[n-1] 中选择具有最小排序码的对象 ; 2 若它不是这组对象中的第一个对象, 则将它与这组对象中的第一个对象对调 ; 3 在这组对象中剔除这个具有最小排序码的对象在剩下的对象 V[i+1]~V[n-1] 中重复执行第 1 2 步, 直到剩余对象只有一个为止

直接选择排序的过程初始 i = 0 21 49 * 16 08 0 1 2 3 4 5 21 49 * 16 08 最小者 08 交换

23 直接选择排序的过程初始 i = * * 最小者 08 交换 21,08 i = * 最小者 16 交换,16 i = * 21 最小者 21 交换 49,21

24 i = 3 i = 4 * * 最小者 * 无交换最小者无交换结果 * 49 各趟排序后的结果

25 4. 归并排序归并排序是把多个有序子文件合并成一个有序文件下面仅介绍二路归并排序二路归并排序的基本思想 : 将两个有序子文件合并成一个有序子文件, 一次合并完成后, 有序子文件的数目减少一半, 而文件的长度增加一倍, 当文件长度从 1 增加到 n( 元素个数 ) 时, 整个文件变为一个, 则该区间中的有序序列即为我们所需的排序结果下面用例子来说明 :

26 二路归并排序过程示意图 [41] [55] [13] [42] [94] [05] [70] [ ] [13 42] [05 94] [70] [ ] [ ] [ ]

27 5. 树形选择排序树形排序的基本思想 : 把 n 个排序码两两比较, 取出较小者然后在 [n/2] 个较小者中, 再用同样的方法比较选出每对中的较小者, 如此反复, 直到选出最小的排序码为止这个序列排序的过程可以用一棵树来表示 : 例如, 191,1,23,27,55,192,84,14, 这一排序中第一趟取最小的过程, 如图所示

28 第一趟取最小排序码的过程下一步在选择次小排序码时, 只需将原叶结点中的最小排序码改为无穷大, 如图所示

29 在树型选择排序的过程中, 被选中的排序码都是走了一条由叶子到根的比较过程因此, 其时间复杂度为 O(nlog 2 n) 但需增加额外的存储空间存放中间比较结果和排序结果, 具体实现有困难因此, 树形选择排序一般不是用来排序而是用来证明某些问题

19

孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 12 月 21 日 1 选择排序交换排序 2 基本思想 : 维护最小的 i 个记录的已排序序列列 ; 每次从剩余未排序的记录中选取关键码最小的记录, 排在已排序序列列之后, 作为序列列的第 i +1 个记录 ; 直接选择排序堆排序 3 以空排序序列列开始 ; 每次从未排序记录中选排序码最小的记录,