软件技术基础11.pptx

软件技术基础软件技术基础制作主讲段景山段景山段景山检索和排序段景山段景山第五章第五章 检索检索检索的基本方法检索的基本方法段景山段景山检索检索n n5.1检索索uu检索是依据元素的关索是依据元素的关键字，在字，在结构中找构中找寻元素的方法元素的方法关关键字字：元素的：元素的标志，志，检索的依据索的依据一般情况下，关一般情况下，关键字是一个元素的唯一字是一个元素的唯一标识段景山段景山检索检索n n检索的方法与数据索的方法与数据结构的关系构的关系uu数据数据数据数据结结构决定了构决定了构决定了构决定了检检索的方法索的方法索的方法索的方法uu有有有有时为时为提高提高提高提高检检索效率，需要索效率，需要索效率，需要索效率，需要对对数据数据数据数据结结构采用特殊构采用特殊构采用特殊构采用特殊的的的的实现实现方式方式方式方式uu例，按成例，按成例，按成例，按成绩检绩检索学生，索学生，索学生，索学生，检检索一个学生成索一个学生成索一个学生成索一个学生成绩递绩递增的增的增的增的表格比表格比表格比表格比杂杂乱的表格效率高乱的表格效率高乱的表格效率高乱的表格效率高n n检索效率的一般索效率的一般评价依据：价依据：uu比比比比较较次数次数次数次数最多、最少和平均比最多、最少和平均比最多、最少和平均比最多、最少和平均比较较次数次数次数次数段景山段景山检索检索 顺序检索顺序检索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段景山段景山检索检索 二分检索二分检索n n5.2 折半（二分）折半（二分）检索索uu方法描述：方法描述：方法描述：方法描述：元素按关元素按关元素按关元素按关键键字大小排列，每次字大小排列，每次字大小排列，每次字大小排列，每次查询查查询查找范找范找范找范围围内内内内的的的的“中中中中间间位置位置位置位置”结结点。点。点。点。若若若若该结该结点不是所需，点不是所需，点不是所需，点不是所需，则缩则缩小小小小查查找范找范找范找范围为围为前半部前半部前半部前半部分或后半部分分或后半部分分或后半部分分或后半部分mm=length/2（要求元素按关键字大小排列）（要求元素按关键字大小排列）ai.key am.keyai.key am.keyaj.key am.key段景山段景山检索检索 二分检索二分检索n n算法框架算法框架uu每次将每次将每次将每次将检检索范索范索范索范围缩围缩小一半，直到范小一半，直到范小一半，直到范小一半，直到范围围中中中中结结点的个点的个点的个点的个数数数数为为0 0whilewhile（L=hL amid.key amid.key )L=m+1L=m+1；else if(amid.key datamid.key=key)if(table-datamid.key=key)break;break;else if(key table-data mid.key)else if(key table-data mid.key)elseelse 检索检索 二分检索二分检索int binary_search(key,table)int 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;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数数数数组实现组实现的的的的顺顺序表序表序表序表 用二分用二分用二分用二分检检索索索索n n单链单链表表表表 用二分用二分用二分用二分检检索索索索n n排序二叉排序二叉排序二叉排序二叉树树 用二分用二分用二分用二分查查找找找找排序排序排序排序不适合不适合不适合不适合适合适合适合适合适合适合适合适合9 97 75 51 11616 181810101 1层层层层2 2层层层层3 3层层层层段景山段景山检索检索n n顺序序检索与二分索与二分检索索uu在在在在检检索有序索有序索有序索有序线线性表性表性表性表时时，顺顺序序序序检检索效率索效率索效率索效率较较低低低低uu对对于无序于无序于无序于无序线线性表，二分性表，二分性表，二分性表，二分检检索要求必索要求必索要求必索要求必须对须对无序无序无序无序线线性性性性表先表先表先表先进进行排序行排序行排序行排序段景山段景山检索检索 分块检索分块检索n n5.3 分分块检索索uu将将将将检检索索索索对对象分象分象分象分块块，块块内无序，内无序，内无序，内无序，块间块间有序。有序。有序。有序。块块内使用内使用内使用内使用较较低效的低效的低效的低效的顺顺序序序序查查找找找找块间块间通通通通过过排序可使用排序可使用排序可使用排序可使用较较高效的高效的高效的高效的查查找方法找方法找方法找方法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;.段景山段景山检索检索 哈希检索哈希检索n n5.4.4 线性探性探查法法uu使用数使用数使用数使用数组组存存存存储储方式方式方式方式uu存放存放存放存放时时，如果，如果，如果，如果hashhash结结果冲突，将新的表果冲突，将新的表果冲突，将新的表果冲突，将新的表项项放在下放在下放在下放在下一个空一个空一个空一个空闲闲的存的存的存的存储单储单元元元元uu检检索索索索时时当当当当发现发现当前当前当前当前hashhash地址里存放的不是需要的地址里存放的不是需要的地址里存放的不是需要的地址里存放的不是需要的元素，就从元素，就从元素，就从元素，就从下一个存下一个存下一个存下一个存储单储单元元元元开始逐个探开始逐个探开始逐个探开始逐个探查查。线线性探性探性探性探查查index=hash(key);index=hash(key);while(table-data index !=empty)while(table-data index !=empty)index+index+；index=hash(key);index=hash(key);while(table-dataindex-key!=key)while(table-dataindex-key!=key)index+;index+;段景山段景山n n例例 关关键字模字模6的的hash运算运算uu以关以关以关以关键键字分字分字分字分别为别为6 6，1010，1212，1818，1111，1313的的的的顺顺序序序序存放元素。存放元素。存放元素。存放元素。uu查查找关找关找关找关键键字字字字为为1212，1818，1313的元素的元素的元素的元素检索检索 哈希检索哈希检索0 01 12 23 34 45 5index=hash(key);index=hash(key);while(table-data index !=empty)while(table-data index !=empty)index+index+；index=hash(key);index=hash(key);while(table-dataindex-key!=key)while(table-dataindex-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个冲突的元素个冲突的元素个冲突的元素个冲突的元素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将一将一将一将一组组元素按照它元素按照它元素按照它元素按照它们们的的的的排序排序排序排序码码的大小，的大小，的大小，的大小，递递增或增或增或增或递递减排列的运算减排列的运算减排列的运算减排列的运算排序排序排序排序码码：一般是元素的关：一般是元素的关：一般是元素的关：一般是元素的关键键字，但也可以不是字，但也可以不是字，但也可以不是字，但也可以不是关关关关键键字，不同元素排序字，不同元素排序字，不同元素排序字，不同元素排序码码可以相同可以相同可以相同可以相同uu排序的方法与数据排序的方法与数据排序的方法与数据排序的方法与数据结结构的关系构的关系构的关系构的关系数据数据数据数据结结构及其构及其构及其构及其实现实现方式，将影响排序方式，将影响排序方式，将影响排序方式，将影响排序过过程中元程中元程中元程中元素比素比素比素比较时较时的方便性，和元素位置的方便性，和元素位置的方便性，和元素位置的方便性，和元素位置调调整（搬移元整（搬移元整（搬移元整（搬移元素）的方便性素）的方便性素）的方便性素）的方便性vv如：如：如：如：链链表表表表对对元素位置元素位置元素位置元素位置调调整整整整带带来很大方便来很大方便来很大方便来很大方便段景山段景山排序排序n n排序算法一般的排序算法一般的评价依据价依据uu平均的比平均的比平均的比平均的比较较次数（完成一次排序所需的元素次数（完成一次排序所需的元素次数（完成一次排序所需的元素次数（完成一次排序所需的元素间间排排排排序序序序码码的比的比的比的比较较次数）次数）次数）次数）uu元素搬移的次数元素搬移的次数元素搬移的次数元素搬移的次数uu算法的算法的算法的算法的稳稳定性：定性：定性：定性：对对相同排序相同排序相同排序相同排序码码的元素之的元素之的元素之的元素之间间相相相相对对位置的位置的位置的位置的维维持持持持vv保持相保持相保持相保持相对对位置不位置不位置不位置不变变稳稳定算法定算法定算法定算法vv不一定保持相不一定保持相不一定保持相不一定保持相对对位置不位置不位置不位置不稳稳定算法定算法定算法定算法1212，1010，1111，1010，15151010，1010，1111，1212，15151010，1010，1111，1212，1515段景山段景山排序排序 简单插入简单插入n n6.2 线性插入算法性插入算法 简单插入算法插入算法uu基本思想基本思想基本思想基本思想：从表取一个元素，按照排序关系插入：从表取一个元素，按照排序关系插入：从表取一个元素，按照排序关系插入：从表取一个元素，按照排序关系插入到新的排序表中。到新的排序表中。到新的排序表中。到新的排序表中。uu若直接在原表中若直接在原表中若直接在原表中若直接在原表中进进行：行：行：行：将表分将表分将表分将表分为为已排序子表和未排序子表。已排序子表和未排序子表。已排序子表和未排序子表。已排序子表和未排序子表。每次从未排序子表中取出表每次从未排序子表中取出表每次从未排序子表中取出表每次从未排序子表中取出表头头元素按排序关系元素按排序关系元素按排序关系元素按排序关系插入到已排序子表中，当未排序子表插入到已排序子表中，当未排序子表插入到已排序子表中，当未排序子表插入到已排序子表中，当未排序子表为为空空空空时时，排序完成。排序完成。排序完成。排序完成。3 31 14 42 2已排序子表已排序子表已排序子表已排序子表未排序子表未排序子表未排序子表未排序子表教材及教案中所有的排序教材及教案中所有的排序教材及教案中所有的排序教材及教案中所有的排序算法都是按递增顺序排序算法都是按递增顺序排序算法都是按递增顺序排序算法都是按递增顺序排序注注注注意意意意段景山段景山排序排序 简单插入简单插入n n算法分析算法分析uu算法框架算法框架算法框架算法框架逐个从未排序子表中取出元素，插入排序子表逐个从未排序子表中取出元素，插入排序子表逐个从未排序子表中取出元素，插入排序子表逐个从未排序子表中取出元素，插入排序子表的算法框架。即未排序子表不断减小，已排序的算法框架。即未排序子表不断减小，已排序的算法框架。即未排序子表不断减小，已排序的算法框架。即未排序子表不断减小，已排序子表不断增加的算法框架。子表不断增加的算法框架。子表不断增加的算法框架。子表不断增加的算法框架。tailtail1 13 36 67 7171745452 2whilewhile（tail length)tail length)核心算法：将核心算法：将核心算法：将核心算法：将tailtail所指的元素按序插入到前所指的元素按序插入到前所指的元素按序插入到前所指的元素按序插入到前面已排序的子表中面已排序的子表中面已排序的子表中面已排序的子表中 tail+;tail+;tail=1;tail=1;tailtail是两个子表的是两个子表的是两个子表的是两个子表的分界线分界线分界线分界线段景山段景山排序排序 简单插入简单插入uu核心算法核心算法核心算法核心算法按序插入的算法按序插入的算法按序插入的算法按序插入的算法vv从已排序子表的后部逐个向前比从已排序子表的后部逐个向前比从已排序子表的后部逐个向前比从已排序子表的后部逐个向前比对对，vv如果插入元素大于表中元素，就将表中元素如果插入元素大于表中元素，就将表中元素如果插入元素大于表中元素，就将表中元素如果插入元素大于表中元素，就将表中元素后移一格，否后移一格，否后移一格，否后移一格，否则则在表中元素后放入在表中元素后放入在表中元素后放入在表中元素后放入while(j -1)while(j -1)if(temp.key dataj.key)if(temp.key dataj.key)table-dataj+1=table-dataj;table-dataj+1=table-dataj;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(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=temp;break;break;j-;j-;接近接近接近接近n(n+1)/4n(n+1)/4次搬移元素次搬移元素次搬移元素次搬移元素排序排序 简单插入简单插入段景山段景山排序排序 简单选择简单选择n n6.3 选择插入排序算法插入排序算法 简单选择算法算法uu基本思想：基本思想：基本思想：基本思想：从无序表中依次从无序表中依次从无序表中依次从无序表中依次选择选择出最小的元素，出最小的元素，出最小的元素，出最小的元素，插入在新的排序表尾插入在新的排序表尾插入在新的排序表尾插入在新的排序表尾uu若直接在原有的表中若直接在原有的表中若直接在原有的表中若直接在原有的表中进进行排序！行排序！行排序！行排序！将表分将表分将表分将表分为为已排序子表和未排序子表。已排序子表和未排序子表。已排序子表和未排序子表。已排序子表和未排序子表。每次从未排序子表中每次从未排序子表中每次从未排序子表中每次从未排序子表中选选出最小的元素，与未排出最小的元素，与未排出最小的元素，与未排出最小的元素，与未排序子表的表首元素交序子表的表首元素交序子表的表首元素交序子表的表首元素交换换，同，同，同，同时时未排序子表表首未排序子表表首未排序子表表首未排序子表表首成成成成为为排序子表表尾，当未排序子表排序子表表尾，当未排序子表排序子表表尾，当未排序子表排序子表表尾，当未排序子表为为空空空空时时，排，排，排，排序完成。序完成。序完成。序完成。3 31 14 42 2已排序子表已排序子表已排序子表已排序子表未排序子表未排序子表未排序子表未排序子表段景山段景山排序排序 简单选择简单选择n n算法分析算法分析uu算法框架算法框架算法框架算法框架未排序子表不断减小，已排序子表不断增大的未排序子表不断减小，已排序子表不断增大的未排序子表不断减小，已排序子表不断增大的未排序子表不断减小，已排序子表不断增大的算法框架算法框架算法框架算法框架whilewhile（head length)head length)核心算法：每次从未排序子表选出最小的元核心算法：每次从未排序子表选出最小的元核心算法：每次从未排序子表选出最小的元核心算法：每次从未排序子表选出最小的元素，与素，与素，与素，与headhead指向的元素指向的元素指向的元素指向的元素交换交换交换交换。head+;head+;head=0;head=0;headhead是两个子表是两个子表是两个子表是两个子表的分界线的分界线的分界线的分界线3 31 14 42 2headhead课堂练习：请参照前面的算法写出算法框架课堂练习：请参照前面的算法写出算法框架课堂练习：请参照前面的算法写出算法框架课堂练习：请参照前面的算法写出算法框架段景山段景山排序排序 简单选择简单选择uu核心算法核心算法核心算法核心算法从未排序子表中从未排序子表中从未排序子表中从未排序子表中选选出最小的元素（逐个比出最小的元素（逐个比出最小的元素（逐个比出最小的元素（逐个比较较）最小的元素和未排序子表首元素交最小的元素和未排序子表首元素交最小的元素和未排序子表首元素交最小的元素和未排序子表首元素交换换3 31 14 42 2headheadj=head;j=head;whilewhile（j length)j length)j+;j+;min=j;min=j;if(table-data j.key datamin.key)if(table-data j.key datamin.key)min=j;min=j;table-dataheadtable-dataheadtable-datamin;table-datamin;课堂练习：请写出选择最小元素的算法课堂练习：请写出选择最小元素的算法课堂练习：请写出选择最小元素的算法课堂练习：请写出选择最小元素的算法课堂练习：请写出元素交换的算法课堂练习：请写出元素交换的算法课堂练习：请写出元素交换的算法课堂练习：请写出元素交换的算法段景山段景山void select_sort(table)void select_sort(table)head=0;head=0;while(head length)while(head length)head=head+1;head=head+1;j=head,min=j;j=head,min=j;while(j length)while(j length)if(table-data j.keydatamin.key)if(table-data j.keydatamin.key)min=j;min=j;j+;j+;temp=table-datahead;temp=table-datahead;table-datahead=table-datamin;table-datahead=table-datamin;table-datamin=temp;table-datamin=temp;table-dataheadtable-dataheadtable-datamin;table-datamin;排序排序 简单选择简单选择n(n+1)/2n(n+1)/2次比较次比较次比较次比较n n次交换次交换次交换次交换段景山段景山排序排序n n简单插入与插入与简单选择算法的比算法的比较uu排序效率排序效率排序效率排序效率简单简单插入算法搬移元素的次数插入算法搬移元素的次数插入算法搬移元素的次数插入算法搬移元素的次数较较多多多多简单选择简单选择算法比算法比算法比算法比较较元素的次数元素的次数元素的次数元素的次数较较多，但搬移次多，但搬移次多，但搬移次多，但搬移次数少数少数少数少uu对对于一个基本有序的表，于一个基本有序的表，于一个基本有序的表，于一个基本有序的表，倾倾向使用向使用向使用向使用 算法算法算法算法uu对对于一个于一个于一个于一个顺顺序混乱的表，序混乱的表，序混乱的表，序混乱的表，倾倾向使用向使用向使用向使用 算法算法算法算法简单插入简单插入简单插入简单插入简单选择简单选择简单选择简单选择例：例：例：例：1 2 3 4 5 7 61 2 3 4 5 7 6段景山段景山排序排序n n简单插入与插入与简单选择算法的比算法的比较uu稳稳定性：定性：定性：定性：简单简单插入算法是插入算法是插入算法是插入算法是？简单选择简单选择算法是算法是算法是算法是？稳定的稳定的稳定的稳定的不稳定的不稳定的不稳定的不稳定的算法的稳定性：算法的稳定性：算法的稳定性：算法的稳定性：对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持对相同排序码的元素之间相对位置的维持保持相对位置不变稳定算法保持相对位置不变稳定算法保持相对位置不变稳定算法保持相对位置不变稳定算法不一定保持相对位置不稳定算法不一定保持相对位置不稳定算法不一定保持相对位置不稳定算法不一定保持相对位置不稳定算法1 14 42 23 33 3例：例：例：例：段景山段景山排序排序 冒泡排序冒泡排序n n6.4 冒泡排序冒泡排序uu基本思想基本思想基本思想基本思想：逐个交：逐个交：逐个交：逐个交换换次序不当的相次序不当的相次序不当的相次序不当的相邻邻表表表表项项，多趟，多趟，多趟，多趟扫扫描后得到排序表描后得到排序表描后得到排序表描后得到排序表3 319192 24 413131010交换交换交换交换19192 2交换交换交换交换19194 4交换交换交换交换1313191910101919交换交换交换交换段景山段景山排序排序 冒泡排序冒泡排序n n冒泡！冒泡！uu最大的元素在第一趟算法中排到了（冒）表尾最大的元素在第一趟算法中排到了（冒）表尾最大的元素在第一趟算法中排到了（冒）表尾最大的元素在第一趟算法中排到了（冒）表尾uu次大的元素在第二趟算法中将冒到倒数第二次大的元素在第二趟算法中将冒到倒数第二次大的元素在第二趟算法中将冒到倒数第二次大的元素在第二趟算法中将冒到倒数第二uu逐趟冒泡，我逐趟冒泡，我逐趟冒泡，我逐趟冒泡，我们们就就就就获获得排序表得排序表得排序表得排序表3 319192 24 41313101019192 219194 413131919191910101313131310102 23 3段景山段景山排序排序 冒泡排序冒泡排序n n算法分析算法分析uu（1 1）多趟）多趟）多趟）多趟扫扫描的框架描的框架描的框架描的框架每一趟每一趟每一趟每一趟扫扫描，都将一个最大的元素排到表尾。描，都将一个最大的元素排到表尾。描，都将一个最大的元素排到表尾。描，都将一个最大的元素排到表尾。每一趟每一趟每一趟每一趟扫扫描，未排序子表减少一格描，未排序子表减少一格描，未排序子表减少一格描，未排序子表减少一格for(turn=0;turn length-2;turn+)for(turn=0;turn length-2;turn+)核心算法：从前向后，每两个元素根据大小交换核心算法：从前向后，每两个元素根据大小交换核心算法：从前向后，每两个元素根据大小交换核心算法：从前向后，每两个元素根据大小交换位置。位置。位置。位置。for(turn=table-length-1;turn 1;turn-)for(turn=table-length-1;turn 1;turn-)核心算法：核心算法：核心算法：核心算法：turn:turn:未排序子表结束位置未排序子表结束位置未排序子表结束位置未排序子表结束位置法法法法一一一一法法法法二二二二段景山段景山排序排序 冒泡排序冒泡排序uu（2 2）核心算法，从前向后）核心算法，从前向后）核心算法，从前向后）核心算法，从前向后逐个逐个逐个逐个比比比比较较相相相相邻邻元素的元素的元素的元素的排序排序排序排序码码，并根据大小关系交，并根据大小关系交，并根据大小关系交，并根据大小关系交换换元素位置元素位置元素位置元素位置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 table-data i+1 段景山段景山排序排序 冒泡排序冒泡排序n n改改改改进进uu不一定要不一定要不一定要不一定要进进行行行行table-length-1table-length-1趟，当趟，当趟，当趟，当发现发现有一趟有一趟有一趟有一趟算法中没有算法中没有算法中没有算法中没有发发生交生交生交生交换换事件，事件，事件，事件，说说明表中的元素已明表中的元素已明表中的元素已明表中的元素已经经排好序了。排好序了。排好序了。排好序了。void bubble_sort(table)void bubble_sort(table)for(turn=table-length-1;turn 1;turn-)for(turn=table-length-1;turn 1;turn-)for(i=0;i trun-1;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;课堂练习：将改进加入算法中课堂练习：将改进加入算法中课堂练习：将改进加入算法中课堂练习：将改进加入算法中段景山段景山排序排序 冒泡排序冒泡排序n n改改进：uu加一个加一个加一个加一个标标志位志位志位志位void bubble_sort(table)void bubble_sort(table)for(turn=table-length-1;turn 1;turn-)for(turn=table-length-1;turn 1;turn-)flag=0;flag=0;for(i=0;i trun-1;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;flag=1flag=1;if(flag=0)if(flag=0)breakbreak;段景山段景山排序排序 冒泡排序冒泡排序n n冒泡排序法的效率冒泡排序法的效率uu同同同同时时兼兼兼兼顾顾了比了比了比了比较较和搬移元素的开和搬移元素的开和搬移元素的开和搬移元素的开销销uu对对于基本有序的序列，效率于基本有序的序列，效率于基本有序的序列，效率于基本有序的序列，效率较较高。高。高。高。uu是是是是稳稳定的算法定的算法定的算法定的算法段景山段景山排序排序 快速排序快速排序n n6.5 快速排序法快速排序法uu基本思想基本思想基本思想基本思想：从表中任意：从表中任意：从表中任意：从表中任意选选取一个元素，把它放于取一个元素，把它放于取一个元素，把它放于取一个元素，把它放于它在排序表中它在排序表中它在排序表中它在排序表中应该应该放置放置放置放置的位置的位置的位置的位置k kki kk kjk k两端的子表不一定有序两端的子表不一定有序两端的子表不一定有序两端的子表不一定有序段景山段景山排序排序 快速排序快速排序uu(1)(1)选选取表首元素取表首元素取表首元素取表首元素uu(2)(2)将将将将该该元素放在表中元素放在表中元素放在表中元素放在表中这样这样的位置：在它之前的元的位置：在它之前的元的位置：在它之前的元的位置：在它之前的元素都比它小，在它之后的元素都比它大。素都比它小，在它之后的元素都比它大。素都比它小，在它之后的元素都比它大。素都比它小，在它之后的元素都比它大。uu(3)(3)以以以以该该元素元素元素元素为为界限，两端的子表不一定有序界限，两端的子表不一定有序界限，两端的子表不一定有序界限，两端的子表不一定有序uu(4)(4)将快速算法分将快速算法分将快速算法分将快速算法分别别作用于两端的子表，不断作用于两端的子表，不断作用于两端的子表，不断作用于两端的子表，不断进进行行行行下去，直到最小的子表是一个元素的子表。下去，直到最小的子表是一个元素的子表。下去，直到最小的子表是一个元素的子表。下去，直到最小的子表是一个元素的子表。ki kk kjk k实际上，就是逐个定位的思想实际上，就是逐个定位的思想实际上，就是逐个定位的思想实际上，就是逐个定位的思想段景山段景山排序排序 快速排序快速排序n n算法分析算法分析uu递归递归的算法框架：的算法框架：的算法框架：的算法框架：将表按照（将表按照（将表按照（将表按照（1 1）（）（）（）（2 2）的步）的步）的步）的步骤骤逐步化小。逐步化小。逐步化小。逐步化小。最小的最小的最小的最小的单单元素子表是排序表元素子表是排序表元素子表是排序表元素子表是排序表由此回溯上去，形成排序表由此回溯上去，形成排序表由此回溯上去，形成排序表由此回溯上去，形成排序表if(low high)if(low high)核心算法：核心算法：核心算法：核心算法：将将将将tablelowtablelow放在排序表中，它应该在的位置放在排序表中，它应该在的位置放在排序表中，它应该在的位置放在排序表中，它应该在的位置 调用调用调用调用quick_sort quick_sort 对左半无序子表进行排序对左半无序子表进行排序对左半无序子表进行排序对左半无序子表进行排序调用调用调用调用quick_sort quick_sort 对右半无序子表进行排序对右半无序子表进行排序对右半无序子表进行排序对右半无序子表进行排序对于对于对于对于lowlow到到到到highhigh之间的子表通过以下调用，成为排序表。之间的子表通过以下调用，成为排序表。之间的子表通过以下调用，成为排序表。之间的子表通过以下调用，成为排序表。quick_sort(low,high)quick_sort(low,high)段景山段景山uu核心算法：如何在无序表里面找到一个元素排序核心算法：如何在无序表里面找到一个元素排序核心算法：如何在无序表里面找到一个元素排序核心算法：如何在无序表里面找到一个元素排序后后后后应该应该在的位置？在的位置？在的位置？在的位置？排序排序 快速排序快速排序13132 29 94 424246 62020lowlowhighhigh1)1)利用利用利用利用highhigh向左移找到比向左移找到比向左移找到比向左移找到比1111小的元素，小的元素，小的元素，小的元素，2)2)利用利用利用利用lowlow向右找到比向右找到比向右找到比向右找到比1111大的元素，大的元素，大的元素，大的元素，3)3)交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。4)4)不断循环不断循环不断循环不断循环1)2)3)1)2)3)知道知道知道知道lowlow与与与与highhigh相遇相遇相遇相遇:low=high:low=high5)5)表首元素与表首元素与表首元素与表首元素与highhigh指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置1111段景山段景山排序排序 快速排序快速排序n n核心算法核心算法whilewhile（lowhigh)lowdatalow.key data f)while(table-datalow.key data f)low+;low+;while(table-datahigh.key table-data f)while(table-datahigh.key table-data f)high-;high-;if(low high)if(low datalow table-datalowtablehigh;tablehigh;table-dataftable-dataftable-datahigh;table-datahigh;2)2)利用利用利用利用low low 向右移找到比向右移找到比向右移找到比向右移找到比1111大的元素，大的元素，大的元素，大的元素，1)1)利用利用利用利用highhigh向左找到比向左找到比向左找到比向左找到比1111小的元素，小的元素，小的元素，小的元素，3)3)交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。交换这两个元素的存放位置。4)4)不断循环不断循环不断循环不断循环1)2)3)1)2)3)知道知道知道知道lowlow与与与与highhigh相遇相遇相遇相遇:lowhigh:lowhigh5)5)表首元素与表首元素与表首元素与表首元素与highhigh指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，指向的元素交换位置，该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置该位置就是表首元素应该在的位置quick_sort(table,low,high)quick_sort(table,low,high)while(low high)while(low datahigh table-dataf while(table-datahigh table-dataf&low high&l