第三章查找与排序技术精选文档.ppt

《第三章查找与排序技术精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章查找与排序技术精选文档.ppt（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第三章查找与排序技术第三章查找与排序技术1 1本讲稿第一页，共六十四页第三章第三章 查找与排序技术查找与排序技术3.1 基本查找技术基本查找技术查找：查找：在一个给定的数据结构中查找某个指定在一个给定的数据结构中查找某个指定的元素。的元素。通常，根据不同的通常，根据不同的数据结构数据结构，应该采用不同的，应该采用不同的查找方法：查找方法：顺序查找；顺序查找；有序表的对分查找；有序表的对分查找；分块查找。分块查找。2 2本讲稿第二页，共六十四页3.1.1 顺序查找顺序查找顺序查找（顺序搜索）：顺序查找（顺序搜索）：在线性表中顺序查找在线性表中顺序查找指定的元素。指定的元素。顺序查找的基本方法：顺

2、序查找的基本方法：从线性表的第一个元素从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行开始，依次将线性表中的元素与被查元素进行比较，若比较，若有相等有相等则表示找到（则表示找到（查找成功查找成功）；若）；若线性表中的所有元素都与被查元素进行了比较线性表中的所有元素都与被查元素进行了比较但但都不相等都不相等，则表示线性表中没有要找到的元，则表示线性表中没有要找到的元素（素（查找失败查找失败）。）。3 3本讲稿第三页，共六十四页举例说明举例说明举例举例：设设A是是n个元素的一维数组。对于指定的输入个元素的一维数组。对于指定的输入x，如果，如果x在数组中，则顺序找到它第一次出现处的在数组

3、中，则顺序找到它第一次出现处的下标；下标；如果如果x在数组中，则以下标作为查找结果。否则在数组中，则以下标作为查找结果。否则以以-1作为结果作为结果4 4本讲稿第四页，共六十四页#define n 5 /*n为查找表中元素个数的最大可能值为查找表中元素个数的最大可能值*/#define MAXLEN n+1int seqsearch(int A,int k)int i;i=0;AMAXLEN-1=k;while(Ai!=k)i+;if(iMAXLEN-1)return i;/*查找成功，返回被查元素在表中的相对位置查找成功，返回被查元素在表中的相对位置*/else return-1;/*查找失

4、败，返回查找失败，返回-1*/使使用用了了监监视视哨哨，在在查查找找过过程程中中，不不用用每每一一步步都都去去判判断断是是否查找结束。否查找结束。找找到到：返返回回元元素素在在线线性性表表中中的的存存储储位位置；置；未找到：返回未找到：返回-1。5 5本讲稿第五页，共六十四页#include stdio.hvoid main()int j,a=11,21,2,45,90,h=8;j=seqsearch(a,h);printf(%d,j);6 6本讲稿第六页，共六十四页顺序查找的效率顺序查找的效率如果线性表中的如果线性表中的第一个元素第一个元素就是被查找元素，就是被查找元素，只需要做一次比较就只

5、需要做一次比较就查找成功查找成功；如果被查的元素是线性表中的如果被查的元素是线性表中的最后一个元素最后一个元素，或者被查元素根本不在线性表中，则需要与线或者被查元素根本不在线性表中，则需要与线性表中的所有元素进行比较（性表中的所有元素进行比较（最坏情况最坏情况）；）；平均情况：平均情况：利用顺序查找法在线性表中查找一利用顺序查找法在线性表中查找一个元素，大约要与个元素，大约要与线性表中一半的元素线性表中一半的元素进行比进行比较。较。7 7本讲稿第七页，共六十四页结论结论对于大的线性表来说，对于大的线性表来说，顺序查找的效率是很顺序查找的效率是很低低的。但在下列两种情况下也只能采用顺序的。但在下

6、列两种情况下也只能采用顺序查找：查找：1.如果线性表为如果线性表为无序表无序表（表中元素的排列是无（表中元素的排列是无序的），则不管是顺序存储结构还是链式存序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找表；储结构，都只能用顺序查找表；2.即使是即使是有序线性表有序线性表，如果采用链式存储结构如果采用链式存储结构，也只能用顺序查找。也只能用顺序查找。8 8本讲稿第八页，共六十四页3.1.2 有序表的对分查找有序表的对分查找有序表有序表：线性表中的元素按值非递减或者非递增线性表中的元素按值非递减或者非递增排列。排列。对分查找的过程：对分查找的过程：将被查找关键字与将被查找关键字与线

7、性表中间线性表中间的项目的项目进行比较，有三种可能：进行比较，有三种可能：1.若被查关键字与表中间的项目相等，则查到，过若被查关键字与表中间的项目相等，则查到，过程结束；程结束；2.若被查关键字大于表中间的项目，则取表的后半若被查关键字大于表中间的项目，则取表的后半部分作为新表再去查找；部分作为新表再去查找；3.若被查关键字小于表中间的项目，则取表的前半若被查关键字小于表中间的项目，则取表的前半部分作为新表再去查找。部分作为新表再去查找。升序升序降序降序查找成功！查找成功！在后半部分查找！在后半部分查找！在前半部分查找！在前半部分查找！减半递推！减半递推！9 9本讲稿第九页，共六十四页时间效率

8、分析时间效率分析对分查找是根据每次试探的结果将线性表的规对分查找是根据每次试探的结果将线性表的规模减半，并有规则地括出可能包含被查项目的模减半，并有规则地括出可能包含被查项目的部分。部分。最坏情况：最坏情况：对查找需要的比较次数为对查找需要的比较次数为n为线性表的长度。为线性表的长度。局限性：局限性：只适用于只适用于有序表有序表，且只限于，且只限于顺序存储顺序存储结构结构。1010本讲稿第十页，共六十四页#define n 6 /*n为查找表中元素个数的最大可能值为查找表中元素个数的最大可能值*/#define MAXLEN nint binsearch(int A,int k)int low

9、,mid,high;low=0;high=MAXLEN-1;while(lowAmid)low=mid+1;elsehigh=mid-1;return-1;/*查找失败，返回查找失败，返回-1*/1111本讲稿第十一页，共六十四页#include stdio.hvoid main()int j,a=2,11,21,45,77,90,h=90;j=binsearch(a,h);printf(%d,j);1212本讲稿第十二页，共六十四页3.1.3 分块查找分块查找分块查找又称分块查找又称索引查找索引查找，是顺序查找的一种改，是顺序查找的一种改进方法，用于在进方法，用于在“分块有序分块有序”表表中

10、进行查找。中进行查找。“分块有序分块有序”表表：将长度为将长度为n的线性表的线性表L分成分成m个子表（各子表的长度可以不等，也可以相等）个子表（各子表的长度可以不等，也可以相等），且，且后一个子表中的每一项均大于前一个子表后一个子表中的每一项均大于前一个子表中的所有项中的所有项。1313本讲稿第十三页，共六十四页分块有序表分块有序表分块有序表分块有序表的结构可以分为两部分：的结构可以分为两部分：(1)(1)线线性性表表本本身身采采用用顺顺序序存存储储结结构构也也可可以以采采用用链链式式存储结构存储结构。(2)(2)再再建建立立一一个个索索引引表表。在在索索引引表表中中，对对线线性性表表的的每每

11、个个子子表表建建立立一一个个索索引引结结点点，每每个个结结点点包包括括两两个个域域：一一是是数数据据域域，用用于于存存放放对对应应子子表表中中的的最最大大元元素素值值；二二是是指指针针域域，用用于于指指示示对对应应子子表表的的第第一一个个元素在整个线性表中的元素在整个线性表中的序号序号或者或者地址地址。1414本讲稿第十四页，共六十四页1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 181515本讲稿第十五页，共六十四页分析分析根根据据分分块块有有序序表表的的结结构构，其其查查找找过过程程可可以以分分以以下两步进行：下两步进行：(1)(1)首首先先查查找找索

12、索引引表表，以以便便确确定定被被查查元元素素所所在在的的子子表表。由由于于索索引引表表数数据据域域中中的的数数据据是是有有序序的的且且顺顺序存储，因此可以采用序存储，因此可以采用对分查找对分查找。(2)(2)然然后后在在相相应应的的子子表表中中用用顺顺序序查查找找法法进进行行具具体体的的查找。查找。结结论论：分分块块查查找找的的效效率率介介于于对对分分查查找找和和顺顺序序查查找之间。找之间。1616本讲稿第十六页，共六十四页3.2 哈希表技术哈希表技术1717本讲稿第十七页，共六十四页传统的查找方法传统的查找方法601050302040查找：50比较思考：有没有不需要比较就可以找到的方法？思考

13、：有没有不需要比较就可以找到的方法？n理想的查找是不经过任何比较，一次存取便能得到所查记录理想的查找是不经过任何比较，一次存取便能得到所查记录1818本讲稿第十八页，共六十四页一种新的想法一种新的想法102030405060123456查找：50A【5】查找：40A【4】需要一种函数，使得F（50）5该函数为：F（x）x div 10当我们需要查找30时，先计算：f（30)3再直接从A【3中取出该记录哈希函数哈希表1919本讲稿第十九页，共六十四页哈希查找，也称为散列查找。哈希查找，也称为散列查找。它既是一种查找方法，又是一种存贮方它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的

14、内存存放法，称为散列存贮。散列存贮的内存存放形式也称为形式也称为哈希表或散列表哈希表或散列表。2020本讲稿第二十页，共六十四页哈希查找是通过构造哈希函数哈希查找是通过构造哈希函数来得到待查来得到待查关键字的地址，从理论上来说是一种不关键字的地址，从理论上来说是一种不需要用到比较的一种查找方法。需要用到比较的一种查找方法。2121本讲稿第二十一页，共六十四页3.2.1 哈希表的基本概念哈希表的基本概念1.直接查找技术直接查找技术设表的长度为设表的长度为n。如果存在一个。如果存在一个函数函数ii(k)，对，对于表中的任意一个于表中的任意一个元素元素的的关键字关键字k，满足以下，满足以下条件：条件

15、：(1)函数值函数值i的范围为：的范围为：1in；(2)对于任意的元素关键字对于任意的元素关键字k1k2，恒存在，恒存在i(k1)i(k2)。则称此表为则称此表为直接查找表直接查找表。其中函数其中函数ii(k)称为关键字称为关键字k的的映象函数映象函数。2222本讲稿第二十二页，共六十四页直接查找技术直接查找技术直接查找表中各元素的关键字直接查找表中各元素的关键字k与表项序号与表项序号i之之间存在着间存在着一一对应的关系一一对应的关系；对直接查找表的查找，只需要根据对直接查找表的查找，只需要根据映像函数映像函数i=i(k)计算出待查关键字项目在表中的计算出待查关键字项目在表中的序号序号i即即可

16、。可。2323本讲稿第二十三页，共六十四页2.Hash表表Hash表技术是直接查找技术的推广，其主要目标表技术是直接查找技术的推广，其主要目标是是提高查找效率提高查找效率。直接查找技术要求映像函数能使得表中任意两个直接查找技术要求映像函数能使得表中任意两个不同的关键字其映像函数值也不同（不同的关键字其映像函数值也不同（不允许元素不允许元素冲突的存在冲突的存在）；但在实际应用中，这一条件很难）；但在实际应用中，这一条件很难满足。满足。对于两个不同的关键字对于两个不同的关键字k1 k2有有i(k1)=i(k2)，发生，发生了了元素冲突元素冲突，即，即两个不同元素需要存在在同一个两个不同元素需要存在

17、在同一个存储单元中存储单元中。2424本讲稿第二十四页，共六十四页举例举例例例3.2 将关键字序列将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为依次填入长度为n12的表中。映象函数为的表中。映象函数为iINT(k/3)1。关键字关键字01和和02发生冲突：发生冲突：因为两个数值都想要存因为两个数值都想要存放在表的第放在表的第1项中。项中。关键字关键字09和和11发生冲突：发生冲突：因为两个数值都想要存因为两个数值都想要存放在表的第放在表的第4项中。项中。2525本讲稿第二十五页，共六十四页分析分析显然，当有元素发生冲突时，是无法进行直接查显

18、然，当有元素发生冲突时，是无法进行直接查找的。所以引入找的。所以引入Hash表表的概念：的概念：设表的长度为设表的长度为n。若存在一个映象函数。若存在一个映象函数i=i(k)，对于表中任一元素的关键字对于表中任一元素的关键字k，满足，满足1 i(k)n，则称此表为，则称此表为Hash表表。并称。并称i(k)为关键字为关键字k的的Hash码码。Hash表中允许冲突存在表中允许冲突存在。如果在。如果在Hash表中没表中没有冲突存在，则有冲突存在，则Hash表就成为直接查找表。表就成为直接查找表。2626本讲稿第二十六页，共六十四页处理表中元素的主要工作：处理表中元素的主要工作：(1)构造合适的构造

19、合适的Hash码，以便尽量减少表中元素冲突码，以便尽量减少表中元素冲突的次数。的次数。(2)当表中元素发生冲突时，要进行适当的处理。当表中元素发生冲突时，要进行适当的处理。3.Hash码的构造码的构造查找关键字为查找关键字为k的元素时，的元素时，计算计算Hash码码i(k)的工作量是的工作量是影响效率的重要因素影响效率的重要因素。在实际构造在实际构造Hash码时，要考虑如下两方面的因素：码时，要考虑如下两方面的因素：(1)使各关键字尽可能均匀地分布在使各关键字尽可能均匀地分布在Hash表中，即表中，即Hash码码的均匀性要好，以便减少冲突发生的机会。的均匀性要好，以便减少冲突发生的机会。(2)

20、Hash码的计算要尽量简单。码的计算要尽量简单。2727本讲稿第二十七页，共六十四页一些简单的一些简单的Hash码构造方法码构造方法1.截段法截段法 2.分段叠加法分段叠加法 3.除法除法 4.乘法乘法2828本讲稿第二十八页，共六十四页 截段法截段法截取法截取法：选取与关键字对应的数字串中的一段选取与关键字对应的数字串中的一段（一般选取低位数）作为关键字的（一般选取低位数）作为关键字的Hash码。码。分段叠加法分段叠加法将关键字的编码串分割成若干段，然后把它们叠将关键字的编码串分割成若干段，然后把它们叠加后再进行截段。加后再进行截段。两种叠加处理的方法：两种叠加处理的方法：1.移位叠加：移位

21、叠加：将分割后的几部分低位对齐相加；将分割后的几部分低位对齐相加；2.间界叠加：间界叠加：从一端沿分割界来回折送，然后对齐从一端沿分割界来回折送，然后对齐相加。相加。此法适于关键字的数字位数特别多的情况。此法适于关键字的数字位数特别多的情况。2929本讲稿第二十九页，共六十四页有有80个记录，关键字为个记录，关键字为8位十进制数，哈希地位十进制数，哈希地址为址为2位十进制数。位十进制数。8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3

22、78 1 4 1 9 3 5 5.分析：分析：只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位 与另两位的叠加作哈希地址与另两位的叠加作哈希地址 截段法截段法：选取与关键字对应的数字串中的一段（一般选取与关键字对应的数字串中的一段（一般选取低位数）作为关键字的选取低位数）作为关键字的Hash码。码。3030本讲稿第三十页，共六十四页举例举例:关键字为关键字为 0442205864，哈希地址位数为，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8

23、 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加 分段叠加法分段叠加法 将关键字分割成若干段，然后把它们叠加后再进行截段。将关键字分割成若干段，然后把它们叠加后再进行截段。两种叠加处理的方法：两种叠加处理的方法：1.移位叠加：移位叠加：将分割后的几部分低位对齐相加；将分割后的几部分低位对齐相加；2.间界叠加：间界叠加：从一端沿分割界来回折送，然后对齐相加。从一端沿分割界来回折送，然后对齐相加。3131本讲稿第三十一页，共六十四页 除法除法imod(k，n)其中其中k为关键字，为关键字，n为为Hash表的长度，而表的长度，而mod为为求余运算符求余运算符；当当m

24、od(k，n)=0时，取时，取i=n（本节规定）。（本节规定）。乘法乘法imod(k*，n)一般取一般取0.618033988747，或，或0.6125423371，或，或0.6161616161。3232本讲稿第三十二页，共六十四页3.2.2 几种常用的几种常用的Hash表表1.线性线性Hash表表线性表是一种线性表是一种最简单的最简单的Hash表表。设线性设线性Hash表的长度为表的长度为m，则对线性，则对线性Hash表的查找过程如下：表的查找过程如下：3333本讲稿第三十三页，共六十四页线性线性Hash表的填入表的填入将关键字将关键字k及有关信息填入线性及有关信息填入线性Hash表的步骤

25、如表的步骤如下：下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)检查表中第检查表中第i项的内容：项的内容：若第若第i项为空，则将关键字项为空，则将关键字k及有关信息填入该及有关信息填入该项；项；若第若第i项不空，则令项不空，则令imod(i1，n)，转，转2)继继续检查。续检查。只要只要Hash表尚未填满，最终总可以找到一个空项，表尚未填满，最终总可以找到一个空项，将关键字将关键字k及有关信息填入到及有关信息填入到Hash表中。表中。线性线性Hash表的表的冲突处理。冲突处理。3434本讲稿第三十四页，共六十四页 线性线性Hash表的取出表的取出要在线性要在线性Hash表中取出关

26、键字表中取出关键字k的元素，其步骤的元素，其步骤如下：如下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)检查表中第检查表中第i项的内容：项的内容：若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；，则取出该项元素即可；若第若第i项为空，则表示在项为空，则表示在Hash表中没有该关键表中没有该关键字的信息；字的信息；若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则令，则令imod(i1，n)转转2)继续检查。继续检查。3535本讲稿第三十五页，共六十四页例例3.3 将关键字序列将关键字序列(09，31，26，19，01，13，02，11，27，16，

27、05，21)依次填入长度为依次填入长度为n12的线的线性性Hash表中。表中。设设Hash码码为为iINT(k/3)1。表表3.2 线性线性Hash表表3636本讲稿第三十六页，共六十四页分析分析线性表的线性表的优点优点：简单。简单。线性线性Hash表的表的缺点缺点：在线性在线性Hash表填入的过程中，当发生冲突时，首表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当先考虑的是下一项，因此，当Hash码的冲突较多码的冲突较多时，在线性时，在线性Hash表中会存在表中会存在“堆聚堆聚”现象现象，即许，即许多关键字被连续登记在一起，从而会降低查找效率。多关键字被连续登记在一起，从而会降低查

28、找效率。在线性在线性Hash表的填入过程中，处理冲突时会带来表的填入过程中，处理冲突时会带来新的冲突。线性新的冲突。线性Hash表的填入方法是表的填入方法是不顾后效不顾后效的。的。3737本讲稿第三十七页，共六十四页在在Hash表填入过程中表填入过程中不顾后效不顾后效，从而在填入过，从而在填入过程中其冲突的机会在不断增多；程中其冲突的机会在不断增多；当当Hash表表填满填满时，不能正常地进行查找。时，不能正常地进行查找。解决方法解决方法：将冲突的元素安排在另外的空间内，将冲突的元素安排在另外的空间内，而不占用而不占用Hash表本身的空间，则就不会产生新表本身的空间，则就不会产生新的冲突。的冲突

29、。3838本讲稿第三十八页，共六十四页3.溢出溢出Hash表表溢出溢出Hash表包括表包括Hash表表和和溢出表溢出表两部分。两部分。在在Hash表的填入过程中，将冲突的元素表的填入过程中，将冲突的元素顺序填顺序填入入溢出表，而当查找过程中发现冲突时，就在溢出表，而当查找过程中发现冲突时，就在溢出表中进行顺序查找。溢出表中进行顺序查找。溢出表是一个溢出表是一个顺序查找表顺序查找表。3939本讲稿第三十九页，共六十四页溢出溢出Hash表的填入表的填入将将关关键键字字k及及有有关关信信息息填填入入溢溢出出Hash表表的的步步骤骤如下：如下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)

30、检查表中第检查表中第i项的内容：项的内容：若第若第i项为空，则将关键字项为空，则将关键字k及有关信息填入该及有关信息填入该项；项；若第若第i项不空，则将关键字项不空，则将关键字k及有关信息依次填及有关信息依次填入溢出表中的入溢出表中的自由项自由项。4040本讲稿第四十页，共六十四页溢出溢出Hash表的取出表的取出要要在在溢溢出出Hash表表中中取取出出关关键键字字k的的元元素素，其其步步骤骤如下：如下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)检查表中第检查表中第i项的内容：项的内容：若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；，则取出该项元素即可；若第若第i

31、项为空，则表示在项为空，则表示在Hash表中没有该关键字表中没有该关键字信息；信息；若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则转入在，则转入在溢出表中进行溢出表中进行顺序查找顺序查找。4141本讲稿第四十一页，共六十四页例例3.5 将关键字序列将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为依次填入长度为n12的溢出的溢出Hash表中。表中。设设Hash码为码为iINT(k/3)1。表表3.4 Hash表和其溢出表表和其溢出表冲突的元素被填入冲突的元素被填入溢出表的自由项溢出表的自由项4242本讲稿第四十二页，共六十

32、四页3.3 基本排序技术基本排序技术排序：排序：将一个数据元素（或记录）的将一个数据元素（或记录）的任意序列，重新排列成一个按关键字任意序列，重新排列成一个按关键字有序的序列。有序的序列。4343本讲稿第四十三页，共六十四页3.3.1 冒泡排序与快速排序（互换排序）冒泡排序与快速排序（互换排序）定义：定义：所谓互换排序是指借助数据元素之间的所谓互换排序是指借助数据元素之间的互换进行排序的一种方法。互换进行排序的一种方法。冒泡排序（冒泡排序（Bubble Sort）是一种最简单的互换是一种最简单的互换排序，它是通过相邻两项目的比较，按一定次排序，它是通过相邻两项目的比较，按一定次序互换，使表格逐

33、步达到有序化。序互换，使表格逐步达到有序化。快速排序（快速排序（Quick Sort）是对冒泡排序的一种改是对冒泡排序的一种改进。进。4444本讲稿第四十四页，共六十四页1.冒泡排序冒泡排序基本思想：基本思想：首先对具有首先对具有n个项目的无序表进行扫描，比较相个项目的无序表进行扫描，比较相邻两个元素的大小，若发现邻两个元素的大小，若发现逆序逆序则进行互换，则进行互换，由此可以使由此可以使n个项目中的最大者沉到表的最后；个项目中的最大者沉到表的最后；然后对剩下的未排序好的项目再进行扫描，使然后对剩下的未排序好的项目再进行扫描，使它们之中的最大者又沉到表的最后；它们之中的最大者又沉到表的最后；以

34、此类推，直到将表全部排序好为止。以此类推，直到将表全部排序好为止。大数在前，小大数在前，小数在后！数在后！4545本讲稿第四十五页，共六十四页将第一个记录的关键字与第二个记录的关键字进将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序行比较，若为逆序r1.keyr2.key，则交换；然，则交换；然后比较第二个记录与第三个记录；依次类推，直后比较第二个记录与第三个记录；依次类推，直至第至第n-1个记录和第个记录和第n个记录比较为止个记录比较为止第一趟第一趟冒泡排序冒泡排序，结果关键字最大的记录被安置在最后，结果关键字最大的记录被安置在最后一个记录上一个记录上冒泡排序冒泡排序4646本讲稿

35、第四十六页，共六十四页对前对前n-1个记录进行第二趟冒泡排序，结果使关个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第键字次大的记录被安置在第n-1个记录位置个记录位置重复上述过程，直到重复上述过程，直到“在一趟排序过程中没有进在一趟排序过程中没有进行过交换记录的操作行过交换记录的操作”为止为止冒泡排序冒泡排序4747本讲稿第四十七页，共六十四页#include”stdio.h”void main()int a10,i,j,temp;printf(”Input l0 integer numbers:”);for(i=0;i10;i+)scanf(”%d”,&ai);for(i=0;i

36、9;i+)for(j=0;jaj+1)temp=aj;aj=aj+1;aj+1=temp;for(i=0;i10;i+)printf(”%d”,ai);4848本讲稿第四十八页，共六十四页2.快速排序快速排序在冒泡排序中，每经过一次数据元素的互换只能在冒泡排序中，每经过一次数据元素的互换只能移掉一个逆序。移掉一个逆序。如果在排序过程中，每经过一次比较，使如果在排序过程中，每经过一次比较，使元素移元素移动不止一个位置动不止一个位置，这就有可能同时移掉多个逆序，这就有可能同时移掉多个逆序，达到加速排序的目的。达到加速排序的目的。基本思想：基本思想：通过一趟分割将线性表分成两部分，通过一趟分割将线性

37、表分成两部分，其中前一部分的所有元素值其中前一部分的所有元素值均不大于均不大于后一部分中后一部分中的每一个元素值；然后对每一部分再进行分割，的每一个元素值；然后对每一部分再进行分割，直到整个线性表有序为止。直到整个线性表有序为止。4949本讲稿第四十九页，共六十四页具体做法具体做法从线性表中选取一个元素，设为从线性表中选取一个元素，设为T。然后将线性。然后将线性表表后面小于后面小于T的元素移到前面的元素移到前面，而，而前面大于前面大于T的元的元素移动到后面素移动到后面，结果就将线性表分成了两部分，结果就将线性表分成了两部分（两个子表），而（两个子表），而T插入到其分界线的位置处。插入到其分界线

38、的位置处。该过程被称为该过程被称为线性表的分割线性表的分割。对分割后的各子表再按上述原则进行分割，直到对分割后的各子表再按上述原则进行分割，直到所有子表为空为止，则此时的线性表就变成了所有子表为空为止，则此时的线性表就变成了有有序表序表。5050本讲稿第五十页，共六十四页首首先先，在在表表的的第第一一个个、中中间间一一个个与与最最后后一一个个元元素素中中选选取取中中项项，设设为为L(k)，并并将将L(k)赋赋给给T，再再将将表表中中的第一个元素与的第一个元素与L(k)交换。交换。然然后后设设置置两两个个指指针针i和和j分分别别指指向向表表的的起起始始与与最最后后的的位置。反复作以下两步：位置。

39、反复作以下两步：(1)将将j逐逐渐渐减减小小，并并逐逐次次比比较较L(j)与与T，直直到到发发现现一一个个L(j)T为止，为止，将将L(j)移到移到L(i)的位置上的位置上。(2)将将i逐逐渐渐增增大大，并并逐逐次次比比较较L(i)与与T，直直到到发发现现一一个个L(i)T为止，为止，将将L(i)移到移到L(j)的位置上的位置上。上上述述两两个个操操作作交交替替进进行行，直直到到指指针针i与与j指指向向同同一一个个位置（即位置（即ij）为止。）为止。5151本讲稿第五十一页，共六十四页快速排序的过程快速排序的过程212108082525494925*25*1616初始关键字初始关键字Tij08

40、082525494925*25*16162121一次交换一次交换ij08082525494925*25*16162121二次交换二次交换ij08082525494925*25*16162121三次交换三次交换ij08082525494925*25*16162121四次交换四次交换ij08082525494925*25*16162121完成一趟排序完成一趟排序ij5252本讲稿第五十二页，共六十四页例例初始关键字：初始关键字：49 38 65 97 76 13 27 50 ijTji 完成一趟排序：完成一趟排序：(27 38 13)49 (76 97 65 50)分别进行快速排序：分别进行快速排

41、序：(13)27 （38)49 (50 65)76 (97)快速排序结束：快速排序结束：13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij5353本讲稿第五十三页，共六十四页3.3.2 简单插入排序与希尔排序简单插入排序与希尔排序基本思想：基本思想：依次将线性表中的每一个元素插入到一依次将线性表中的每一个元素插入到一个已经有序的子表中。个已经有序的子表中。方法：方法：将线性表中，将线性表中，只包含第只包含第1个元素的子表个元素的子表显然可以看显然可以看成是有序表；成是有序表；从线性表的从线性表的第第2个元素开始直到最后一个元素个元素开始直到最

42、后一个元素，逐，逐次将其中的每一个元素插入到前面已经有序的子次将其中的每一个元素插入到前面已经有序的子表中；表中；一般来说，假设线性表中前一般来说，假设线性表中前j-1个元素已经有序，个元素已经有序，现在要现在要将线性表中第将线性表中第j个元素插入到前面的有序子个元素插入到前面的有序子表表中。中。5454本讲稿第五十四页，共六十四页有序1.简单插入排序简单插入排序5555本讲稿第五十五页，共六十四页演示演示有序5656本讲稿第五十六页，共六十四页例例49 38 65 97 76 13 27i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13

43、 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=1 ()i=7 (13 38 49 65 76 97)2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：排序结果：5757本讲稿第五十七页，共六十四页void insort(int p,int n)int j,k;T t;for(j=1;j=0)&(pkt)pk+1=pk;k=k 1;pk+1=t;return;数组数组p，存放着待排序列，存放着待排序列数组数组p的长度

44、，即待排的长度，即待排序序列中元素的个数序序列中元素的个数简单插入排序简单插入排序当前待排序列（从当前待排序列（从pj到到pn-1）中第）中第一个元素的值赋给一个元素的值赋给t将待排序列中第一个元素将待排序列中第一个元素t插入到已排序序列中的合插入到已排序序列中的合适位置，同时保证已排序适位置，同时保证已排序序列仍旧为升序序列序列仍旧为升序序列5858本讲稿第五十八页，共六十四页2.希尔排序希尔排序直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(n2)，但是若待，但是若待排记录序列为排记录序列为“正序正序”时，其时间复杂度可以时，其时间复杂度可以提高至提高至O(n)。由此可以设想：由此

45、可以设想：若待排记录序列按关键字若待排记录序列按关键字“基本有序基本有序”，直，直接插入排序的效率就可大大提高；接插入排序的效率就可大大提高；一方面，由于直接插入排序算法简单，则在一方面，由于直接插入排序算法简单，则在n值很小时效率也比较高。值很小时效率也比较高。5959本讲稿第五十九页，共六十四页希尔排序的希尔排序的基本思想基本思想：先将整个待排记录序列分割先将整个待排记录序列分割成为成为若干个子序列分别进行直接插入排序若干个子序列分别进行直接插入排序，待整个，待整个序列中的记录序列中的记录“基本有序基本有序”时，再对全体记录进行时，再对全体记录进行一次直接插入排序。一次直接插入排序。子序列

46、的分割方法如下：子序列的分割方法如下：将将物理位置上物理位置上相隔某个增量相隔某个增量h的元素构成一个子序列。的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当在排序过程中，逐次减小这个增量，最后当h减到减到1时，时，进行一次插入排序，排序就完成。进行一次插入排序，排序就完成。增量序列一般取增量序列一般取 htn/2k(k1，2，log2n)，其，其中中n为待排序序列的长度。为待排序序列的长度。6060本讲稿第六十页，共六十四页图图3.6 希尔排序示意图希尔排序示意图6161本讲稿第六十一页，共六十四页3.3.3 简单选择排序简单选择排序基本思想：基本思想：首先通过首先通过n-1次关

47、键字比较，从次关键字比较，从n个记个记录中找出关键字最小的记录，将它与第一个记录录中找出关键字最小的记录，将它与第一个记录交换交换再通过再通过n-2次比较，从剩余的次比较，从剩余的n-1个记录中找出个记录中找出关键字次小的记录，将它与第二个记录交换关键字次小的记录，将它与第二个记录交换重复上述操作，共进行重复上述操作，共进行n-1趟排序后，排序结趟排序后，排序结束束6262本讲稿第六十二页，共六十四页图3-7 简单选择排序示例6363本讲稿第六十三页，共六十四页算法算法 简单选择排序。简单选择排序。void selectsort(int R,int n)int i,j,k;int temp;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(RjRk)k=j;if(i!=k)temp=Rk;Rk=Ri;Ri=temp;6464本讲稿第六十四页，共六十四页