《软件技术基础课件11》由会员分享，可在线阅读，更多相关《软件技术基础课件11（52页珍藏版）》请在金锄头文库上搜索。
1、软件技术基础软件技术基础制作主讲段景山段景山段景山检索和排序段景山段景山第五章第五章 检索检索检索的基本方法检索的基本方法段景山段景山检索检索n n5.1检索检索uu检索是依据元素的关键字，在结构中找寻检索是依据元素的关键字，在结构中找寻元素的方法元素的方法关键字关键字：元素的标志，检索的依据：元素的标志，检索的依据一般情况下，关键字是一个元素的唯一一般情况下，关键字是一个元素的唯一标识标识段景山段景山检索检索n n检索的方法与数据结构的关系检索的方法与数据结构的关系uu数据结构决定了检索的方法数据结构决定了检索的方法数据结构决定了检索的方法数据结构决定了检索的方法uu有时为提高检索效率，需要
2、对数据结构采用特殊有时为提高检索效率，需要对数据结构采用特殊有时为提高检索效率，需要对数据结构采用特殊有时为提高检索效率，需要对数据结构采用特殊的实现方式的实现方式的实现方式的实现方式uu例，按成绩检索学生，检索一个学生成绩递增的例，按成绩检索学生，检索一个学生成绩递增的例，按成绩检索学生，检索一个学生成绩递增的例，按成绩检索学生，检索一个学生成绩递增的表格比杂乱的表格效率高表格比杂乱的表格效率高表格比杂乱的表格效率高表格比杂乱的表格效率高n n检索效率的一般评价依据：检索效率的一般评价依据：uu比较次数比较次数比较次数比较次数最多、最少和平均比较次数最多、最少和平均比较次数最多、最少和平均比
3、较次数最多、最少和平均比较次数段景山段景山检索检索 顺序检索顺序检索n n5.1 顺序检索顺序检索 顺序查找顺序查找uu从头开始逐个检索直到找到需要的结点从头开始逐个检索直到找到需要的结点从头开始逐个检索直到找到需要的结点从头开始逐个检索直到找到需要的结点i = 0;while( i length) if( table-ai.key = our_key) break; i = i+1; 找到所需的结点找到所需的结点if (i length )return i;elseerror(“ no such item ”);平均查找次数平均查找次数= PiCii = 1n= n+12段景山段景山检索检索
4、 二分检索二分检索n n5.2 折半（二分）检索折半（二分）检索uu方法描述：方法描述：方法描述：方法描述：元素按关键字大小排列，每次查询查找范围内元素按关键字大小排列，每次查询查找范围内元素按关键字大小排列，每次查询查找范围内元素按关键字大小排列，每次查询查找范围内的的的的“ “中间位置中间位置中间位置中间位置” ”结点。结点。结点。结点。若该结点不是所需，则缩小查找范围为前半部若该结点不是所需，则缩小查找范围为前半部若该结点不是所需，则缩小查找范围为前半部若该结点不是所需，则缩小查找范围为前半部分或后半部分分或后半部分分或后半部分分或后半部分mm = length / 2（要求元素按关键字
5、大小排列）（要求元素按关键字大小排列）ai.keyai.key am.keyam.key段景山段景山检索检索 二分检索二分检索n n算法框架算法框架uu每次将检索范围缩小一半，直到范围中结点的个每次将检索范围缩小一半，直到范围中结点的个每次将检索范围缩小一半，直到范围中结点的个每次将检索范围缩小一半，直到范围中结点的个数为数为数为数为0 0whilewhile（L = hL amid.keyamid.key ) )L = m + 1L = m + 1；else if ( amid.key if( table-datamid.keydatamid.key = key) = key)break;b
6、reak;else if( key table-data else if( key table-data mid.keymid.key ) )elseelse 检索检索 二分检索二分检索intint binary_search( key , table ) binary_search( key , table )L = 0;L = 0;h = table-length 1;h = table-length 1;while ( )while ( ) return mid;return mid; L = hL = hh = mid 1;h = mid 1;L = mid +1;L = mid +1
7、;if ( L = h )if ( L = h )elseelse return 1;return 1;L Lh h段景山段景山n n平均查找次数平均查找次数平均查找次数平均查找次数检索检索 二分检索二分检索n1( 1 + 2 2 + 4 3 + . + 2k (log 2n +1)log2 (n + 1) - 19 97 75 51 11616 181810101 1层层层层2 2层层层层3 3层层层层段景山段景山检索检索 二分检索二分检索n n无序的线性表必须无序的线性表必须无序的线性表必须无序的线性表必须 才能使用二分检索才能使用二分检索才能使用二分检索才能使用二分检索 n n数组实现的
8、顺序表数组实现的顺序表数组实现的顺序表数组实现的顺序表 用二分检索用二分检索用二分检索用二分检索n n单链表单链表单链表单链表 用二分检索用二分检索用二分检索用二分检索n n排序二叉树排序二叉树排序二叉树排序二叉树 用二分查找用二分查找用二分查找用二分查找排序排序排序排序不适合不适合不适合不适合适合适合适合适合适合适合适合适合9 97 75 51 11616 181810101 1层层层层2 2层层层层3 3层层层层段景山段景山检索检索n n顺序检索与二分检索顺序检索与二分检索uu在检索有序线性表时，顺序检索效率较低在检索有序线性表时，顺序检索效率较低在检索有序线性表时，顺序检索效率较低在检索
9、有序线性表时，顺序检索效率较低uu对于无序线性表，二分检索要求必须对无序线性对于无序线性表，二分检索要求必须对无序线性对于无序线性表，二分检索要求必须对无序线性对于无序线性表，二分检索要求必须对无序线性表先进行排序表先进行排序表先进行排序表先进行排序段景山段景山检索检索 分块检索分块检索n n5.3 分块检索分块检索uu将检索对象分块，块内无序，块间有序。将检索对象分块，块内无序，块间有序。将检索对象分块，块内无序，块间有序。将检索对象分块，块内无序，块间有序。块内使用较低效的顺序查找块内使用较低效的顺序查找块内使用较低效的顺序查找块内使用较低效的顺序查找块间通过排序可使用较高效的查找方法块间
10、通过排序可使用较高效的查找方法块间通过排序可使用较高效的查找方法块间通过排序可使用较高效的查找方法uu可做出块的索引表，进一步针对块索引表进行折可做出块的索引表，进一步针对块索引表进行折可做出块的索引表，进一步针对块索引表进行折可做出块的索引表，进一步针对块索引表进行折半检索半检索半检索半检索306586x = 3030 x = 6565 x dataindex);p = &(table-dataindex);while( p != NULL & p-key != key )while( p != NULL & p-key != key )p = p-next ;p = p-next ;.段景
11、山段景山检索检索 哈希检索哈希检索n n5.4.4 线性探查法线性探查法uu使用数组存储方式使用数组存储方式使用数组存储方式使用数组存储方式uu存放时，如果存放时，如果存放时，如果存放时，如果hashhash结果冲突，将新的表项放在下结果冲突，将新的表项放在下结果冲突，将新的表项放在下结果冲突，将新的表项放在下一个空闲的存储单元一个空闲的存储单元一个空闲的存储单元一个空闲的存储单元uu检索时当发现当前检索时当发现当前检索时当发现当前检索时当发现当前hashhash地址里存放的不是需要的地址里存放的不是需要的地址里存放的不是需要的地址里存放的不是需要的元素，就从元素，就从元素，就从元素，就从下一
12、个存储单元下一个存储单元下一个存储单元下一个存储单元开始逐个探查。开始逐个探查。开始逐个探查。开始逐个探查。线性探查线性探查线性探查线性探查index = index = hash(keyhash(key); );while ( table-data index != empty )while ( table-data index != empty )index +index +；index = index = hash(keyhash(key); );while( table-while( table-dataindexdataindex-key != key)-key != key)ind
13、ex +;index +;段景山段景山n n例例 关键字模关键字模6的的hash运算运算uu以关键字分别为以关键字分别为以关键字分别为以关键字分别为6 6，1010，1212，1818，1111，1313的顺序的顺序的顺序的顺序存放元素。存放元素。存放元素。存放元素。uu查找关键字为查找关键字为查找关键字为查找关键字为1212，1818，1313的元素的元素的元素的元素检索检索 哈希检索哈希检索0 01 12 23 34 45 5index = index = hash(keyhash(key); );while ( table-data index != empty )while ( tab
14、le-data index != empty )index +index +；index = index = hash(keyhash(key); );while( table-while( table-dataindexdataindex-key != key)-key != key)index +;index +;6 612121818131310101111段景山段景山检索检索 哈希检索哈希检索n n5.4.5 开放地址法开放地址法uuH Hi i（k k） （H H（K K） d di i）mod mmod mi i：第：第：第：第i i个冲突的元素个冲突的元素个冲突的元素个冲突的元素
15、i i 1 to n1 to nuu（1 1）di di 1, 2, 3, 1, 2, 3, uu（2 2）di di 1 12 2, , 1 12 2, 2, 22 2 ，2 22 2uu（3 3）di di 伪随机序列伪随机序列伪随机序列伪随机序列uu目的：使冲突分散目的：使冲突分散目的：使冲突分散目的：使冲突分散线性探测线性探测线性探测线性探测二次探测二次探测二次探测二次探测随机再散列随机再散列随机再散列随机再散列段景山段景山排序的基本方法排序的基本方法第六章第六章 排序排序段景山段景山排序排序n n6.1 排序排序uu将一组元素按照它们的将一组元素按照它们的将一组元素按照它们的将一组元
16、素按照它们的排序码排序码排序码排序码的大小，递增或递的大小，递增或递的大小，递增或递的大小，递增或递减排列的运算减排列的运算减排列的运算减排列的运算排序码：一般是元素的关键字，但也可以不是排序码：一般是元素的关键字，但也可以不是排序码：一般是元素的关键字，但也可以不是排序码：一般是元素的关键字，但也可以不是关键字，不同元素排序码可以相同关键字，不同元素排序码可以相同关键字，不同元素排序码可以相同关键字，不同元素排序码可以相同uu排序的方法与数据结构的关系排序的方法与数据结构的关系排序的方法与数据结构的关系排序的方法与数据结构的关系数据结构及其实现方式，将影响排序过程中元数据结构及其实现方式，将
17、影响排序过程中元数据结构及其实现方式，将影响排序过程中元数据结构及其实现方式，将影响排序过程中元素比较时的方便性，和元素位置调整（搬移元素比较时的方便性，和元素位置调整（搬移元素比较时的方便性，和元素位置调整（搬移元素比较时的方便性，和元素位置调整（搬移元素）的方便性素）的方便性素）的方便性素）的方便性vv如：链表对元素位置调整带来很大方便如：链表对元素位置调整带来很大方便如：链表对元素位置调整带来很大方便如：链表对元素位置调整带来很大方便段景山段景山排序排序n n排序算法一般的评价依据排序算法一般的评价依据uu平均的比较次数（完成一次排序所需的元素间排平均的比较次数（完成一次排序所需的元素间
18、排平均的比较次数（完成一次排序所需的元素间排平均的比较次数（完成一次排序所需的元素间排序码的比较次数）序码的比较次数）序码的比较次数）序码的比较次数）uu元素搬移的次数元素搬移的次数元素搬移的次数元素搬移的次数uu算法的稳定性：算法的稳定性：算法的稳定性：算法的稳定性：对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持vv保持相对位置不变稳定算法保持相对位置不变稳定算法保持相对位置不变稳定算法保持相对位置不变稳定算法vv不一定保持相对位置不稳定算法不一定保持相对位置不稳定算法不一定保持相对位置不稳定算
19、法不一定保持相对位置不稳定算法1212，1010，1111，1010，15151010，1010， 1111，1212，15151010，1010， 1111，1212，1515段景山段景山排序排序 简单插入简单插入n n6.2 线性插入算法线性插入算法 简单插入算法简单插入算法uu基本思想基本思想基本思想基本思想：从表取一个元素，按照排序关系插入：从表取一个元素，按照排序关系插入：从表取一个元素，按照排序关系插入：从表取一个元素，按照排序关系插入到新的排序表中。到新的排序表中。到新的排序表中。到新的排序表中。uu若直接在原表中进行：若直接在原表中进行：若直接在原表中进行：若直接在原表中进行：
20、将表分为已排序子表和未排序子表。将表分为已排序子表和未排序子表。将表分为已排序子表和未排序子表。将表分为已排序子表和未排序子表。每次从未排序子表中取出表头元素按排序关系每次从未排序子表中取出表头元素按排序关系每次从未排序子表中取出表头元素按排序关系每次从未排序子表中取出表头元素按排序关系插入到已排序子表中，当未排序子表为空时，插入到已排序子表中，当未排序子表为空时，插入到已排序子表中，当未排序子表为空时，插入到已排序子表中，当未排序子表为空时，排序完成。排序完成。排序完成。排序完成。3 31 14 42 2已排序子表已排序子表已排序子表已排序子表未排序子表未排序子表未排序子表未排序子表教材及教
21、案中所有的排序教材及教案中所有的排序教材及教案中所有的排序教材及教案中所有的排序算法都是按递增顺序排序算法都是按递增顺序排序算法都是按递增顺序排序算法都是按递增顺序排序注注注注意意意意段景山段景山排序排序 简单插入简单插入n n算法分析算法分析uu算法框架算法框架算法框架算法框架逐个从未排序子表中取出元素，插入排序子表逐个从未排序子表中取出元素，插入排序子表逐个从未排序子表中取出元素，插入排序子表逐个从未排序子表中取出元素，插入排序子表的算法框架。即未排序子表不断减小，已排序的算法框架。即未排序子表不断减小，已排序的算法框架。即未排序子表不断减小，已排序的算法框架。即未排序子表不断减小，已排序
22、子表不断增加的算法框架。子表不断增加的算法框架。子表不断增加的算法框架。子表不断增加的算法框架。tailtail1 13 36 67 7171745452 2whilewhile（tail length)tail length) 核心算法：将核心算法：将核心算法：将核心算法：将tailtail所指的元素按序插入到前所指的元素按序插入到前所指的元素按序插入到前所指的元素按序插入到前面已排序的子表中面已排序的子表中面已排序的子表中面已排序的子表中 tail +;tail +; tail = 1;tail = 1;tailtail是两个子表的是两个子表的是两个子表的是两个子表的分界线分界线分界线分界
23、线段景山段景山排序排序 简单插入简单插入uu核心算法核心算法核心算法核心算法按序插入的算法按序插入的算法按序插入的算法按序插入的算法vv从已排序子表的后部逐个向前比对，从已排序子表的后部逐个向前比对，从已排序子表的后部逐个向前比对，从已排序子表的后部逐个向前比对，vv如果插入元素大于表中元素，就将表中元素如果插入元素大于表中元素，就将表中元素如果插入元素大于表中元素，就将表中元素如果插入元素大于表中元素，就将表中元素后移一格，否则在表中元素后放入后移一格，否则在表中元素后放入后移一格，否则在表中元素后放入后移一格，否则在表中元素后放入while ( j -1 )while ( j -1 )if
24、( if( temp.keytemp.key dataj.key) dataj.key)table-dataj+1 = table-table-dataj+1 = table-datajdataj; ; elseelsetable-dataj+1 = temp;table-dataj+1 = temp;break;break; j-; j-; 1 12 26 67 710106 61717temptemp段景山段景山void insert_sort(table)void insert_sort(table) tail = 1;tail = 1;while ( tail length)while
25、 ( tail length) tail = tail +1; tail = tail +1; temp = table-datatail;temp = table-datatail;j = tail - 1;j = tail - 1;while( j -1)while( j -1)if(temp.key table-dataj.key)if(temp.key table-dataj.key)table-dataj+1 = table-dataj;table-dataj+1 = table-dataj;elseelsetable-dataj+1 = temp;table-dataj+1 = t
26、emp;break;break; j-; j-; 接近接近接近接近n(n+1)/4n(n+1)/4次搬移元素次搬移元素次搬移元素次搬移元素排序排序 简单插入简单插入段景山段景山排序排序 简单选择简单选择n n6.3 选择插入排序算法选择插入排序算法 简单选择算法简单选择算法uu基本思想：基本思想：基本思想：基本思想：从无序表中依次选择出最小的元素，从无序表中依次选择出最小的元素，从无序表中依次选择出最小的元素，从无序表中依次选择出最小的元素，插入在新的排序表尾插入在新的排序表尾插入在新的排序表尾插入在新的排序表尾uu若直接在原有的表中进行排序！若直接在原有的表中进行排序！若直接在原有的表中进行
27、排序！若直接在原有的表中进行排序！将表分为已排序子表和未排序子表。将表分为已排序子表和未排序子表。将表分为已排序子表和未排序子表。将表分为已排序子表和未排序子表。每次从未排序子表中选出最小的元素，与未排每次从未排序子表中选出最小的元素，与未排每次从未排序子表中选出最小的元素，与未排每次从未排序子表中选出最小的元素，与未排序子表的表首元素交换，同时未排序子表表首序子表的表首元素交换，同时未排序子表表首序子表的表首元素交换，同时未排序子表表首序子表的表首元素交换，同时未排序子表表首成为排序子表表尾，当未排序子表为空时，排成为排序子表表尾，当未排序子表为空时，排成为排序子表表尾，当未排序子表为空时，
28、排成为排序子表表尾，当未排序子表为空时，排序完成。序完成。序完成。序完成。3 31 14 42 2已排序子表已排序子表已排序子表已排序子表未排序子表未排序子表未排序子表未排序子表段景山段景山排序排序 简单选择简单选择n n算法分析算法分析uu算法框架算法框架算法框架算法框架未排序子表不断减小，已排序子表不断增大的未排序子表不断减小，已排序子表不断增大的未排序子表不断减小，已排序子表不断增大的未排序子表不断减小，已排序子表不断增大的算法框架算法框架算法框架算法框架whilewhile（head length)head length) 核心算法：每次从未排序子表选出最小的元核心算法：每次从未排序子
29、表选出最小的元核心算法：每次从未排序子表选出最小的元核心算法：每次从未排序子表选出最小的元素，与素，与素，与素，与headhead指向的元素指向的元素指向的元素指向的元素交换交换交换交换。 head +;head +; head = 0;head = 0;headhead是两个子表是两个子表是两个子表是两个子表的分界线的分界线的分界线的分界线3 31 14 42 2headhead课堂练习：请参照前面的算法写出算法框架课堂练习：请参照前面的算法写出算法框架课堂练习：请参照前面的算法写出算法框架课堂练习：请参照前面的算法写出算法框架段景山段景山排序排序 简单选择简单选择uu核心算法核心算法核心算
30、法核心算法从未排序子表中选出最小的元素（逐个比较）从未排序子表中选出最小的元素（逐个比较）从未排序子表中选出最小的元素（逐个比较）从未排序子表中选出最小的元素（逐个比较）最小的元素和未排序子表首元素交换最小的元素和未排序子表首元素交换最小的元素和未排序子表首元素交换最小的元素和未排序子表首元素交换3 31 14 42 2headheadj = head;j = head;whilewhile（j length)j length) j+; j+; min = j;min = j;if( table-data j .key if( table-data j .key datamin.keydata
31、min.key) ) min = j; min = j;table-table-dataheaddatahead table-table-datamindatamin; ;课堂练习：请写出选择最小元素的算法课堂练习：请写出选择最小元素的算法课堂练习：请写出选择最小元素的算法课堂练习：请写出选择最小元素的算法课堂练习：请写出元素交换的算法课堂练习：请写出元素交换的算法课堂练习：请写出元素交换的算法课堂练习：请写出元素交换的算法段景山段景山void select_sort(table)void select_sort(table) head = 0; head = 0; while ( head
32、length)while ( head length) head = head = headhead +1; +1; j = head, min=j;j = head, min=j;while( j length)while( j length) if(tableif(table-data j .key-data j .keydatamin.keydatamin.key) ) min = j; min = j; j+; j+; temp = table-temp = table-dataheaddatahead; ;table-table-dataheaddatahead = table-da
33、tamin; = table-datamin;table-datamin = temp;table-datamin = temp;table-table-dataheaddatahead table-table-datamindatamin; ;排序排序 简单选择简单选择n(n+1)/2n(n+1)/2次比较次比较次比较次比较n n次交换次交换次交换次交换段景山段景山排序排序n n简单插入与简单选择算法的比较简单插入与简单选择算法的比较uu排序效率排序效率排序效率排序效率简单插入算法搬移元素的次数较多简单插入算法搬移元素的次数较多简单插入算法搬移元素的次数较多简单插入算法搬移元素的次数较多简单
34、选择算法比较元素的次数较多，但搬移次简单选择算法比较元素的次数较多，但搬移次简单选择算法比较元素的次数较多，但搬移次简单选择算法比较元素的次数较多，但搬移次数少数少数少数少uu对于一个基本有序的表，倾向使用对于一个基本有序的表，倾向使用对于一个基本有序的表，倾向使用对于一个基本有序的表，倾向使用 算法算法算法算法uu对于一个顺序混乱的表，倾向使用对于一个顺序混乱的表，倾向使用对于一个顺序混乱的表，倾向使用对于一个顺序混乱的表，倾向使用 算法算法算法算法简单插入简单插入简单插入简单插入简单选择简单选择简单选择简单选择例：例：例：例：1 2 3 4 5 7 61 2 3 4 5 7 6段景山段景山
35、排序排序n n简单插入与简单选择算法的比较简单插入与简单选择算法的比较uu稳定性：稳定性：稳定性：稳定性：简单插入算法是简单插入算法是简单插入算法是简单插入算法是 ？简单选择算法是简单选择算法是简单选择算法是简单选择算法是 ？稳定的稳定的稳定的稳定的不稳定的不稳定的不稳定的不稳定的算法的稳定性：算法的稳定性：算法的稳定性：算法的稳定性：对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持保持相对位置不变稳定算法保持相对位置不变稳定算法保持相对位置不变稳定算法保持相对位置不变稳定算法不一定保持相对位置不稳
36、定算法不一定保持相对位置不稳定算法不一定保持相对位置不稳定算法不一定保持相对位置不稳定算法1 14 42 23 33 3例：例：例：例：段景山段景山排序排序 冒泡排序冒泡排序n n6.4 冒泡排序冒泡排序uu基本思想基本思想基本思想基本思想：逐个交换次序不当的相邻表项，多趟：逐个交换次序不当的相邻表项，多趟：逐个交换次序不当的相邻表项，多趟：逐个交换次序不当的相邻表项，多趟扫描后得到排序表扫描后得到排序表扫描后得到排序表扫描后得到排序表3 319192 24 413131010交换交换交换交换19192 2交换交换交换交换19194 4交换交换交换交换1313191910101919交换交换交
37、换交换段景山段景山排序排序 冒泡排序冒泡排序n n冒泡！冒泡！uu最大的元素在第一趟算法中排到了（冒）表尾最大的元素在第一趟算法中排到了（冒）表尾最大的元素在第一趟算法中排到了（冒）表尾最大的元素在第一趟算法中排到了（冒）表尾uu次大的元素在第二趟算法中将冒到倒数第二次大的元素在第二趟算法中将冒到倒数第二次大的元素在第二趟算法中将冒到倒数第二次大的元素在第二趟算法中将冒到倒数第二uu逐趟冒泡，我们就获得排序表逐趟冒泡，我们就获得排序表逐趟冒泡，我们就获得排序表逐趟冒泡，我们就获得排序表3 319192 24 41313101019192 219194 413131919191910101313
38、131310102 23 3段景山段景山排序排序 冒泡排序冒泡排序n n算法分析算法分析uu（1 1）多趟扫描的框架）多趟扫描的框架）多趟扫描的框架）多趟扫描的框架每一趟扫描，都将一个最大的元素排到表尾。每一趟扫描，都将一个最大的元素排到表尾。每一趟扫描，都将一个最大的元素排到表尾。每一趟扫描，都将一个最大的元素排到表尾。每一趟扫描，未排序子表减少一格每一趟扫描，未排序子表减少一格每一趟扫描，未排序子表减少一格每一趟扫描，未排序子表减少一格for( turn = 0 ; turn length -2 ; turn + )for( turn = 0 ; turn length -2 ; turn
39、 + ) 核心算法：从前向后，每两个元素根据大小交换核心算法：从前向后，每两个元素根据大小交换核心算法：从前向后，每两个元素根据大小交换核心算法：从前向后，每两个元素根据大小交换位置。位置。位置。位置。 for(turnfor(turn = table-length-1;turn 1;turn - -) = table-length-1;turn 1;turn - -) 核心算法：核心算法：核心算法：核心算法： turn:turn:未排序子表结束位置未排序子表结束位置未排序子表结束位置未排序子表结束位置法法法法一一一一法法法法二二二二段景山段景山排序排序 冒泡排序冒泡排序uu（2 2）核心算法
40、，从前向后）核心算法，从前向后）核心算法，从前向后）核心算法，从前向后逐个逐个逐个逐个比较相邻元素的排比较相邻元素的排比较相邻元素的排比较相邻元素的排序码，并根据大小关系交换元素位置序码，并根据大小关系交换元素位置序码，并根据大小关系交换元素位置序码，并根据大小关系交换元素位置for( i = 0 ; i data i .key table-data i+1 .key)temp = table-data i ;table-data i = table-data i+1 ;table-data i+1 = temp;table-data i table-data i table-data i+1
41、 table-data i+1 段景山段景山排序排序 冒泡排序冒泡排序n n改进改进改进改进uu不一定要进行不一定要进行不一定要进行不一定要进行table-length-1table-length-1趟，当发现有一趟趟，当发现有一趟趟，当发现有一趟趟，当发现有一趟算法中没有发生交换事件，说明表中的元素已经算法中没有发生交换事件，说明表中的元素已经算法中没有发生交换事件，说明表中的元素已经算法中没有发生交换事件，说明表中的元素已经排好序了。排好序了。排好序了。排好序了。void bubble_sort( table)void bubble_sort( table) for(turnfor(tur
42、n = table-length-1 ; turn 1 ; turn-) = table-length-1 ; turn 1 ; turn-) for( i = 0 ; i for( i = 0 ; i data i .key table-datai+1.key) if( table-data i .key table-datai+1.key) table-data i table-datai+1; table-data i table-datai+1; 课堂练习：将改进加入算法中课堂练习：将改进加入算法中课堂练习：将改进加入算法中课堂练习：将改进加入算法中段景山段景山排序排序 冒泡排序冒泡排
43、序n n改进：改进：uu加一个标志位加一个标志位加一个标志位加一个标志位void bubble_sort( table)void bubble_sort( table) for(turnfor(turn = table-length-1 ; turn 1 ; turn-) = table-length-1 ; turn 1 ; turn-) flag = 0;flag = 0; for( i = 0 ; i for( i = 0 ; i data i .key table-datai+1.key) if( table-data i .key table-datai+1.key) table-d
44、ata i table-datai+1; table-data i table-datai+1; flag = 1flag = 1; ; if(flagif(flag = 0) = 0) breakbreak; ; 段景山段景山排序排序 冒泡排序冒泡排序n n冒泡排序法的效率冒泡排序法的效率uu同时兼顾了比较和搬移元素的开销同时兼顾了比较和搬移元素的开销同时兼顾了比较和搬移元素的开销同时兼顾了比较和搬移元素的开销uu对于基本有序的序列，效率较高。对于基本有序的序列，效率较高。对于基本有序的序列，效率较高。对于基本有序的序列，效率较高。uu是稳定的算法是稳定的算法是稳定的算法是稳定的算法段景山段
45、景山排序排序 快速排序快速排序n n6.5 快速排序法快速排序法uu基本思想基本思想基本思想基本思想：从表中任意选取一个元素，把它放于：从表中任意选取一个元素，把它放于：从表中任意选取一个元素，把它放于：从表中任意选取一个元素，把它放于它在排序表中它在排序表中它在排序表中它在排序表中应该放置应该放置应该放置应该放置的位置的位置的位置的位置k kki kk kjk k两端的子表不一定有序两端的子表不一定有序两端的子表不一定有序两端的子表不一定有序段景山段景山排序排序 快速排序快速排序uu(1)(1)选取表首元素选取表首元素选取表首元素选取表首元素uu(2)(2)将该元素放在表中这样的位置：在它之
46、前的元将该元素放在表中这样的位置：在它之前的元将该元素放在表中这样的位置：在它之前的元将该元素放在表中这样的位置：在它之前的元素都比它小，在它之后的元素都比它大。素都比它小，在它之后的元素都比它大。素都比它小，在它之后的元素都比它大。素都比它小，在它之后的元素都比它大。uu(3)(3)以该元素为界限，两端的子表不一定有序以该元素为界限，两端的子表不一定有序以该元素为界限，两端的子表不一定有序以该元素为界限，两端的子表不一定有序uu(4)(4)将快速算法分别作用于两端的子表，不断进行将快速算法分别作用于两端的子表，不断进行将快速算法分别作用于两端的子表，不断进行将快速算法分别作用于两端的子表，不
47、断进行下去，直到最小的子表是一个元素的子表。下去，直到最小的子表是一个元素的子表。下去，直到最小的子表是一个元素的子表。下去，直到最小的子表是一个元素的子表。ki kk kjk k实际上，就是逐个定位的思想实际上，就是逐个定位的思想实际上，就是逐个定位的思想实际上，就是逐个定位的思想段景山段景山排序排序 快速排序快速排序n n算法分析算法分析uu递归的算法框架：递归的算法框架：递归的算法框架：递归的算法框架：将表按照（将表按照（将表按照（将表按照（1 1）（）（）（）（2 2）的步骤逐步化小。）的步骤逐步化小。）的步骤逐步化小。）的步骤逐步化小。最小的单元素子表是排序表最小的单元素子表是排序表
48、最小的单元素子表是排序表最小的单元素子表是排序表由此回溯上去，形成排序表由此回溯上去，形成排序表由此回溯上去，形成排序表由此回溯上去，形成排序表if ( low high )if ( low high ) 核心算法：核心算法：核心算法：核心算法：将将将将tablelowtablelow放在排序表中，它应该在的位置放在排序表中，它应该在的位置放在排序表中，它应该在的位置放在排序表中，它应该在的位置 调用调用调用调用quick_sort quick_sort 对左半无序子表进行排序对左半无序子表进行排序对左半无序子表进行排序对左半无序子表进行排序调用调用调用调用quick_sort quick_s
49、ort 对右半无序子表进行排序对右半无序子表进行排序对右半无序子表进行排序对右半无序子表进行排序对于对于对于对于lowlow到到到到highhigh之间的子表通过以下调用，成为排序表。之间的子表通过以下调用，成为排序表。之间的子表通过以下调用，成为排序表。之间的子表通过以下调用，成为排序表。quick_sort(low,highquick_sort(low,high) ) 段景山段景山uu核心算法：如何在无序表里面找到一个元素排序核心算法：如何在无序表里面找到一个元素排序核心算法：如何在无序表里面找到一个元素排序核心算法：如何在无序表里面找到一个元素排序后应该在的位置？后应该在的位置？后应该在
50、的位置？后应该在的位置？排序排序 快速排序快速排序13132 29 94 424246 62020lowlowhighhigh1)1)利用利用利用利用highhigh向左移找到比向左移找到比向左移找到比向左移找到比1111小的元素，小的元素，小的元素，小的元素，2)2)利用利用利用利用lowlow向右找到比向右找到比向右找到比向右找到比1111大的元素，大的元素，大的元素，大的元素，3)3)交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。4)4)不断循环不断循环不断循环不断循环1) 2) 3)1) 2) 3)知道知道知道知道lowlow与
51、与与与highhigh相遇相遇相遇相遇:low=high:low=high5)5)表首元素与表首元素与表首元素与表首元素与highhigh指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置1111段景山段景山排序排序 快速排序快速排序n n核心算法核心算法whilewhile（lowhigh)low-datalow.keydatalow.key data f ) data f ) low+; low+; while(tablewhile(tabl
52、e-datahigh.keydatahigh.key table-data f ) table-data f ) high-; high-; if(lowif(low high) table-datalowdatalowtablehightablehigh; ;table-table-datafdataftabletable-datahighdatahigh; ;2)2)利用利用利用利用low low 向右移找到比向右移找到比向右移找到比向右移找到比1111大的元素，大的元素，大的元素，大的元素，1)1)利用利用利用利用highhigh向左找到比向左找到比向左找到比向左找到比1111小的元素，
53、小的元素，小的元素，小的元素，3)3)交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。4)4)不断循环不断循环不断循环不断循环1) 2) 3)1) 2) 3)知道知道知道知道lowlow与与与与highhigh相遇相遇相遇相遇:lowhigh:lowhigh5)5)表首元素与表首元素与表首元素与表首元素与highhigh指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置quick_sort(
54、table, low , high )quick_sort(table, low , high )while(lowwhile(low high) -datahighdatahigh table- table-datafdataf &low high&low while (table-datalowdatalow datafdataf & low high& low high ) )low +; low +; if(lowif(low high) table-datalowdatalowtabletable-datahigh ;-datahigh ; table-data f table-da
55、ta f table-datahigh; table-datahigh; f = lowf = low，lowlowlowlow1 1，last = high;last = high;quick_sort(firstquick_sort(first, high 1);, high 1);quick_sort(highquick_sort(high +1,last); +1,last);防止死循环防止死循环防止死循环防止死循环防止死循环防止死循环防止死循环防止死循环段景山段景山排序排序 快速排序快速排序uu教材中的核心算法教材中的核心算法教材中的核心算法教材中的核心算法11112 29 94 4
56、24242020lowlowhighhighx x：13136 61111段景山段景山排序排序 快速排序快速排序11112 29 94 424242020lowlowhighhighx x：13136 61111x = table-x = table-datalowdatalow; ; while(lowwhile(low high) data low = x;table-data low = x;while(tablewhile(table-datahigh.keydatahigh.key x& low x& lowhigh) high-; high-;if(lowif(low datalo
57、wdatalow+=table-+=table-datahighdatahigh; ;while(tablewhile(table-datalow.keydatalow.key x& lowhigh) x& lowhigh) low+; low+; if(lowif(low datahighdatahigh-=table-=table-datalowdatalow; ;段景山段景山排序排序 快速排序快速排序n n快速排序算法效率快速排序算法效率uu（1 1）算法趟数少）算法趟数少）算法趟数少）算法趟数少快速快速快速快速具有具有具有具有“ “二分二分二分二分” ”处理的特色处理的特色处理的特色处
58、理的特色uu（2 2）每一趟算法中交换的结点少，比较的次数为）每一趟算法中交换的结点少，比较的次数为）每一趟算法中交换的结点少，比较的次数为）每一趟算法中交换的结点少，比较的次数为n n次次次次uu( 3 )( 3 )排序算法的稳定性排序算法的稳定性排序算法的稳定性排序算法的稳定性 ？4 43 35 54 41 16 6课堂练习：试举例说明快速排序算法是否稳定课堂练习：试举例说明快速排序算法是否稳定课堂练习：试举例说明快速排序算法是否稳定课堂练习：试举例说明快速排序算法是否稳定段景山段景山排序排序 快速排序快速排序n n注意：注意：uu教案中介绍的快速排序算法与教材介绍的算法在教案中介绍的快速
59、排序算法与教材介绍的算法在教案中介绍的快速排序算法与教材介绍的算法在教案中介绍的快速排序算法与教材介绍的算法在交换元素问题上有所不同交换元素问题上有所不同交换元素问题上有所不同交换元素问题上有所不同uu快速排序算法不稳定快速排序算法不稳定快速排序算法不稳定快速排序算法不稳定uu算法是否稳定应视具体语句而定。算法是否稳定应视具体语句而定。算法是否稳定应视具体语句而定。算法是否稳定应视具体语句而定。如在选择插入算法中，如果将寻找最小元素的如在选择插入算法中，如果将寻找最小元素的如在选择插入算法中，如果将寻找最小元素的如在选择插入算法中，如果将寻找最小元素的语句改为语句改为语句改为语句改为if(ta
60、bleif(table i = i = tablemintablemin) ) min = i; min = i;算法就不稳定了。算法就不稳定了。算法就不稳定了。算法就不稳定了。段景山段景山排序排序 归并排序归并排序n n6.6 归并排序归并排序uu“ “归并归并归并归并” ”：将两个或以上的有序序列合并为一个将两个或以上的有序序列合并为一个将两个或以上的有序序列合并为一个将两个或以上的有序序列合并为一个有序序列。有序序列。有序序列。有序序列。uu归并排序：假设归并排序：假设归并排序：假设归并排序：假设n n个元素的序列，将它视为个元素的序列，将它视为个元素的序列，将它视为个元素的序列，将它视
61、为n n个子个子个子个子序列，然后不断两两归并子序列直到全部归并为序列，然后不断两两归并子序列直到全部归并为序列，然后不断两两归并子序列直到全部归并为序列，然后不断两两归并子序列直到全部归并为一个有序序列。一个有序序列。一个有序序列。一个有序序列。uu例：例：例：例：教材教材教材教材P69P69uu归并算法的基本思想与快速排序正好相反，一个归并算法的基本思想与快速排序正好相反，一个归并算法的基本思想与快速排序正好相反，一个归并算法的基本思想与快速排序正好相反，一个是不断将子表化小，一个是不断合并子表是不断将子表化小，一个是不断合并子表是不断将子表化小，一个是不断合并子表是不断将子表化小，一个是不断合并子表段景山段景山作业作业n n教材教材73页第页第26、27、28题题
