第十章 排序(1).ppt

《第十章 排序(1).ppt》由会员分享，可在线阅读，更多相关《第十章 排序(1).ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Data StructureData Structure第十章第十章 排序排序10.1 10.1 概述概述10.2 10.2 插入排序插入排序 10.2.1 10.2.1 直接插入排序直接插入排序 10.2.2 10.2.2 其他插入排序其他插入排序10.3 10.3 快速排序快速排序10.4 10.4 选择排序选择排序 10.4.1 10.4.1 简单选择排序简单选择排序 10.4.2 10.4.2 树形选择排序树形选择排序Data StructureData Structure10.1 10.1 概述概述 将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排

2、列起来。存放在数据表中存放在数据表中按按关键字排序关键字排序定义：设有记录序列：定义：设有记录序列：R1R1、R2 R2.RnRn 其相应的关键字序列为：其相应的关键字序列为：K1K1、K2 K2.KnKn;若存在一种确定的关系：若存在一种确定的关系：KxKx=KyKy=KzKz，则将记录序列则将记录序列R1R1、R2 R2.RnRn 排成按该关键字有序的序列：排成按该关键字有序的序列：RxRx、RyRyRzRz 的的操作，称之为排序。操作，称之为排序。1.1.什么是排序？什么是排序？例如：例如：将下列关键字序列将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为调

3、整为14,23,36,49,52,58,61,75,80,97Data StructureData Structure2.排序的目的是什么？排序的目的是什么？3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？便于查找！便于查找！时间效率时间效率排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数）空间效率空间效率占内存辅助空间的大小占内存辅助空间的大小稳定性稳定性若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B B的先后的先后次序保持不变，则称这种排序算法是稳定的。次序保持不变，则称这种排序算法是稳定的。Data Str

4、uctureData Structure4.什么叫内部排序？什么叫外部排序什么叫内部排序？什么叫外部排序？大多数排序算法都有大多数排序算法都有两个基本的操作两个基本的操作：（1 1）比较两个关键字的大小）比较两个关键字的大小（2 2）将记录从一个位置移动到另一个位置）将记录从一个位置移动到另一个位置记录序列的存储方式：记录序列的存储方式：（1 1）顺序存储顺序存储 （2 2）静态链表）静态链表 （3 3）地址）地址注：注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。外存，显然外部排序要复杂

5、得多。若待排序记录都在内存中，称为内部排序；若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。若待排序记录一部分在内存，一部分在外存，则称为外部排序。Data StructureData Structure5.内部排序的算法有哪些？内部排序的算法有哪些？按排序的规则不同，可分为按排序的规则不同，可分为5类：类：插入排序插入排序交换排序（重点是快速排序）交换排序（重点是快速排序）选择排序选择排序归并排序归并排序基数排序基数排序多关键字排序多关键字排序按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法简单的排序算

6、法：时间效率低，：时间效率低，O(n2)先进的排序算法先进的排序算法:时间效率高，时间效率高，O(nlog2n)基数排序算算法基数排序算算法：时间效率高，：时间效率高，O(dn)Data StructureData Structure注：注：大多数排序算法都是针对顺序表结构的大多数排序算法都是针对顺序表结构的(便于直接移动元素便于直接移动元素)6.顺序存储（顺序表）的抽象数据类型如何表示？顺序存储（顺序表）的抽象数据类型如何表示？Typedefstruct/定义每个记录（数据元素）的结构定义每个记录（数据元素）的结构KeyTypekey;/关键字关键字InfoTypeotherinfo;/其它

7、数据项其它数据项RedType;Typedefstruct/定义顺序表的结构定义顺序表的结构RedTyperMAXSIZE+1;/存储顺序表的向量存储顺序表的向量 /r0/r0一般作哨兵或缓冲区一般作哨兵或缓冲区intlength;/顺序表的长度顺序表的长度SqList;#defineMAXSIZE20/设记录不超过设记录不超过2020个个typedefintKeyType;/设关键字为整型量（设关键字为整型量（intint型）型）Data StructureData Structure10.210.2 插入排序插入排序 插入排序有多种具体实现算法：插入排序有多种具体实现算法：1)直接插入排序

8、直接插入排序2)折半插入排序折半插入排序插入排序的基本思想是：插入排序的基本思想是：将待排序表看做是将待排序表看做是左、右两部分左、右两部分，其中左边为有序区，右边为无序区，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录整个排序过程就是将右边无序区中的记录依次按关键字大小依次按关键字大小逐个插入到逐个插入到左边有序区中，以构成新的有序区左边有序区中，以构成新的有序区直到全部记录都排好序。直到全部记录都排好序。有序序列R1.i-1Ri无序序列Ri.n有序序列R1.i无序序列Ri+1.nData StructureData Structure1)1)直接插入排序直接插入排序直

9、接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），），请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】最简单的排序法！最简单的排序法！最简单的排序法！最简单

10、的排序法！在已形成的在已形成的有序表中有序表中线性查找线性查找，并在适当位置插入，把原来位置上的元，并在适当位置插入，把原来位置上的元素向后素向后顺移顺移。Data StructureData Structure例例例例2 2：关键字序列关键字序列关键字序列关键字序列T=T=（2121，2525，4949，25*25*，1616，0808），），），），请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。*表示后一个表示后一个2525i i=1=121212525494925*25*16160808012345

11、6暂暂存存2121i i=2=2i i=3=3i i=5=5i i=4=4i i=6=62525252525494949494925*25*25*494916161625*25*0808084949解：解：序列存入一维数组序列存入一维数组V7V7中，将中，将V0V0作为缓冲或暂存单元作为缓冲或暂存单元21212525494925*25*2121初态：初态：1616494925*25*2525212116160808完成!则程序执行过程为：则程序执行过程为：Data StructureData Structure算法算法 10.1 10.1 void void InsertSortInsertS

12、ort(SqList&LSqList&L)/对顺序表L作直接插入排序。L.rj+1=L.r0/L.rj+1=L.r0/插入到正确位置插入到正确位置/InsertsortInsertsortfor(ifor(i=2=2；i=L.1engthi=L.1ength；+i)+i)if if LT(L.ri.keyLT(L.ri.key，L.ri-1.key)/L.ri-1.key)/“”，需将，需将L.riL.ri 插入有序子表插入有序子表L.r0=L.r0=L.riL.ri/复制为哨兵复制为哨兵for(j=i-2;LT(L.r0.keyfor(j=i-2;LT(L.r0.key，L.rj.keyL.

13、rj.key);-i);-i)L.rj+1=L.rj+1=L.rjL.rj；/记录后移记录后移L.riL.ri=L.rj-1=L.rj-1；/记录后移记录后移Data StructureData Structure直接插入排序的算法分析直接插入排序的算法分析若设待排序的对象个数为若设待排序的对象个数为n n，则算法需要进行，则算法需要进行n n-1-1次插入。次插入。最好情况下，最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的面的有序对象序列的最后一个对象最后一个对象的关键码比较的关键码比较 1 1 次，移动

14、次，移动 2 2 次对象。次对象。因此，总的关键码比较次数为因此，总的关键码比较次数为n n-1-1，对象移动次数为，对象移动次数为 2(2(n n-1)-1)。最坏情况下，最坏情况下，第第i i趟插入时，第趟插入时，第i i个对象必须与前面个对象必须与前面i-1i-1个对象都做关键码个对象都做关键码比较，并且每做比较，并且每做 1 1 次比较就要做次比较就要做 1 1 次数据移动。则总的关键码比较次数次数据移动。则总的关键码比较次数KCNKCN和对象移动次数和对象移动次数RMNRMN分别为分别为出现各种可能排列的概率相同，出现各种可能排列的概率相同，平均比较次数和对象移动次数约为平均比较次数

15、和对象移动次数约为 n n2 2/4/4。Data StructureData Structure2）折半插入排序折半插入排序新元素插入到哪里？新元素插入到哪里？在已形成的在已形成的有序表中有序表中折半查找折半查找，并在适当位置插入，把原来，并在适当位置插入，把原来位置上的元素向后位置上的元素向后顺移顺移。从减少“比较”和“移动”操作的次数出发 void void BInsertSortBInsertSort(SqListSqList&L)/&L)/对顺序表对顺序表L L作折半插入排序。作折半插入排序。for(ifor(i=2=2；iL.1engthiL.1ength；+i)+i)L.r0=L

16、.r0=L.riL.ri/L.riL.ri 暂存到暂存到L.r0 L.r0 low=1;high=i-1;/low=1;high=i-1;/在在rlow.highrlow.high 中折半查找有序插入的位置中折半查找有序插入的位置while(lowwhile(low=high)=high+1;-j)L.rj+1=for(j=i-1;j=high+1;-j)L.rj+1=L.rjL.rj;/;/记录后移记录后移L.rhigh+1=L.r0;/L.rhigh+1=L.r0;/插入插入/for/for/BInsertSortBInsertSort算法算法10.210.2Data StructureD

17、ata Structure讨论：讨论：若记录是链表结构，用直接插入排序行否？折半插入排序呢？若记录是链表结构，用直接插入排序行否？折半插入排序呢？但链表无法但链表无法“折半折半”！时间效率：时间效率：虽然比较次数大大减少，可惜移动次数并未减少，所以排序虽然比较次数大大减少，可惜移动次数并未减少，所以排序 效率仍为效率仍为O(nO(n2 2)。答：答：直接插入不仅可行，而且还无需移动元素，时间效率更高！直接插入不仅可行，而且还无需移动元素，时间效率更高！在插入第在插入第 i i 个对象时，需要经过个对象时，需要经过 loglog2 2i i +1 +1 次关键码比较次关键码比较，才能确定，才能确

18、定它应插入的位置。它应插入的位置。将将 n n 个对象用折半插入排序所进行的关键码比较次数为：个对象用折半插入排序所进行的关键码比较次数为：n*logn*log2 2 n nData StructureData Structure10.3 10.3 交换排序交换排序两两比较待排序记录的关键码，如果发生逆序（即排两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。所有记录都排好序为止。交换排序的主要算法有：交换排序的主要算法有：1)冒泡排序冒泡排序2)快速排序快速排序交换排序的基本思想交换

19、排序的基本思想Data StructureData Structure 1)1)冒泡排序冒泡排序基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。前提：前提：顺序存储结构顺序存储结构例：例：关键字序列关键字序列T=(21，25，49，25*，16，08），写出冒），写出冒泡排序的具体实现过程。泡排序的具体实现过程。21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，

20、16，21，25，25*，49初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟优点：优点：每趟排序，不仅能挤每趟排序，不仅能挤出一个最大值到最后面位置，出一个最大值到最后面位置，还能同时部分理顺其他元素还能同时部分理顺其他元素.Data StructureData Structure冒泡排序的算法分析冒泡排序的算法分析时间效率：时间效率：时间效率：时间效率：O O O O（n n n n2 2 2 2)详细分析：详细分析：最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n n-1-1 次关键码比较，不移动对象。次关键码比较，不移动对象

21、。最坏情形：最坏情形：初始排列逆序，算法要执行初始排列逆序，算法要执行n n-1-1趟起泡，第趟起泡，第i i趟趟(1(1 i i n n)做了做了n-i n-i 次关键码比较，执行了次关键码比较，执行了n-i n-i 次对象交次对象交换。此时的比较总次数换。此时的比较总次数KCNKCN和记录移动次数和记录移动次数RMNRMN为：为：稳稳稳稳 定定定定 性：性：性：性：稳定稳定稳定稳定 25252525和和和和25252525*在排序前后的次序未改变在排序前后的次序未改变在排序前后的次序未改变在排序前后的次序未改变Data StructureData Structure2 2）快速排序快速排序

22、 从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素 (例如取第一个例如取第一个例如取第一个例如取第一个)作为作为作为作为中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子

23、表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。此时便为有序序列了。此时便为有序序列了。此时便为有序序列了。基本思想：基本思想：基本思想：基本思想：优点：优点：优点：优点：因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！加，所以特别快！加，所以特别快！加，所以特别快！前提：前提：前提：前提：顺序存储

24、结构顺序存储结构顺序存储结构顺序存储结构 Data StructureData Structure()，设以首元素为枢轴中心设以首元素为枢轴中心例例1：关键字序列关键字序列 T=(21，25，49，25*，16，08），），请请写出快速排序的算法步骤。写出快速排序的算法步骤。21，25，49，25*，16，08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：1.1.这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？2.2.“快速排序快速排序”是否真的比任何排序算法都快？是否真的比任何排序算法都快？08，16，21，25，25*，(49)2116，08

25、，()25，25*，49(08)，16，21，25，(25*，49)以其他元素为枢轴中心以其他元素为枢轴中心Data StructureData Structureintint PartitionPartitionPartitionPartition(SqList(SqList&L,L,intint lowlow,intint high high)/一趟快排一趟快排/交换子表交换子表 rlowrlowhighhigh的记录，使支点（枢轴）记录到位，并返回其位置。的记录，使支点（枢轴）记录到位，并返回其位置。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。返回时，在支点之前的记录均

26、不大于它，支点之后的记录均不小于它。L.r0=L.r0=L.L.rlowrlow;/以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元pivotkeypivotkey=l.l.rlow.keyrlow.key;/取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(low high)while(low high)/从表的两端交替地向中间扫描从表的两端交替地向中间扫描while(while(lowhighlow=pivotkeypivotkey)-high;-high;-high;-high;L.L.rlowrlow=L.L.rhi

27、ghrhigh;/将比支点小的记录交换到低端；将比支点小的记录交换到低端；while(while(lowhighlowhigh&L.L.rlow.keyrlow.key=pivotkeypivotkey)+low;+low;+low;+low;L.L.rhighrhigh=L.L.rlowrlow;/将比支点大的记录交换到高端；将比支点大的记录交换到高端；L.L.rlowrlow=L.L.r0;r0;/支点记录到位；支点记录到位；return low;return low;/返回支点记录所在位置。返回支点记录所在位置。/PartitionPartitionPartitionPartition算

28、法算法 10.610.6Data StructureData Structure例例2：以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的）为例，写出执行快速算法的各趟各趟排序结束时，关键排序结束时，关键字序列的状态。字序列的状态。原始序列：原始序列：256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，74

29、2742，694694，076076，438438076076076076，129129，256256256256，751751751751，937937，863863，742742，694694，301301，438438256256256256076076301301129129751751256256256256076076076076，129129，256256256256，438438，301301，694694，742742，694694，863863，937937751751751751076076076076，129129129129，256256256256，43843843

30、8438，301301，694694，742742，751751751751，863863863863，937937076076076076，129129129129，256256256256，301301，301301，694694，742742，751751751751，863863863863，937937438438438438076076076076，129129129129，256256256256，301301301301，438438438438，694694694694，742742，751751751751，863863863863，937937937937时间效率：时间效

31、率：O(nlogO(nlog2 2n)n)因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加Data StructureData Structure讨论讨论2.“2.“快速排序快速排序”是否真的比任何排序算法都快？是否真的比任何排序算法都快？设每个子表的支点都在中间（比较均衡），则：设每个子表的支点都在中间（比较均衡），则：第第1 1趟比较，可以确定趟比较，可以确定1 1个元素的位置；个元素的位置；第第2 2趟比较（趟比较（2 2个子表），可以再确定个子表），可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较（趟比较（4 4个子表），可以再确定个子表），可以再确定4 4个元素的

32、位置；个元素的位置；第第4 4趟比较（趟比较（8 8个子表），可以再确定个子表），可以再确定8 8个元素的位置；个元素的位置；只需只需 loglog2 2n n 1 1趟便可排好序。趟便可排好序。基本上是！因为每趟可以确定的数据元素是呈指数增加的！基本上是！因为每趟可以确定的数据元素是呈指数增加的！基本上是！因为每趟可以确定的数据元素是呈指数增加的！基本上是！因为每趟可以确定的数据元素是呈指数增加的！每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。替逼近技巧，更进一步减少了移动次

33、数，所以速度特别快。Data StructureData Structure10.4 选择排序选择排序 基本思想：基本思想：在待排记录中依次选择关键字最小的记录作为有序序列的最在待排记录中依次选择关键字最小的记录作为有序序列的最后一条记录，逐渐缩小范围直至全部记录选择完毕。后一条记录，逐渐缩小范围直至全部记录选择完毕。10.4.1 简单选择排序简单选择排序 49 38 65 97 76 49 38 65 97 76 1313 27 27 4949 1338 65 97 76 49 1338 65 97 76 49 2727 4949 13 2765 97 76 49 13 2765 97 76

34、 49 38 38 4949 13 27 3865 97 76 13 27 3865 97 76 4949 4949 13 27 38 4965 97 76 13 27 38 4965 97 76 4949 13 27 38 49 13 27 38 49 4949 6565 97 76 97 76 13 27 38 49 13 27 38 49 4949 6597 6597 7676 13 27 38 49 13 27 38 49 4949 65 76 97 65 76 97通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1in)个记录交换 一趟简单选择排序的操

35、作为：Data StructureData Structure利用前n-1次比较所得信息，减少以后各趟选择排序中所用的比较次数。在n个关键字中选出最小值，至少进行n-1次比较，在剩余的n-1个关键字中选择次小值进行n-2次比较.10.4.2 10.4.2 树形选择排序树形选择排序 选择排序主要进行关键字间的比较，从如何减少“比较”出发考虑改进。锦标赛排序锦标赛排序首先对n个记录的关键字进行两两比较，然后在其中较小者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。一棵有n个叶子结点完全二叉树表示。08Winner 2108086325*21212549 25*160863Data StructureData Structure 排序算法小结排序算法小结 平均时间平均时间 最差最差 最佳最佳 辅助空间辅助空间 稳定性稳定性直接直接插入插入 O(O(n n2 2)O(O(n n2 2)O(n)O()O(n)O(1 1)稳定稳定冒泡冒泡排序排序 O(O(n n2 2)O()O(n n2 2)O(n)O()O(n)O(1 1)稳定稳定快速快速排序排序 O(nlogO(nlog2 2n)O(n)O(n n2 2)同平均同平均 O(logO(log2 2n)n)不稳定不稳定直接选择直接选择 O(nO(n2 2)O(n)O(n2 2)O(n)O(n2 2)O(1)O(1)不稳定不稳定