数据结构及算法排序-PPT

第八章排序技术本章的基本内容是：排序的基本概念插入排序交换排序选择排序数据结构及算法排序-PPT全文共117页，当前为第1页。8.1概述

排序：将一组“无序”的记录序列,调整为按关键字“有序”的记录序列.学号姓名高数英语思想品德0002王军85880001李明64920003汤晓影8586………687278……1.排序的基本概念数据结构及算法排序-PPT全文共117页，当前为第2页。排序：给定一组记录的集合{r1,r2,……,rn}，其相应的关键码分别为{k1,k2,……,kn}，排序是将这些记录排列成顺序为{rs1,rs2,……,rsn}的一个序列，使得相应的关键码满足非递减关系ks1≤ks2≤……≤ksn（称为升序）或非递增关系ks1≥ks2≥……≥ksn（称为降序）。1.排序的基本概念学号姓名高数英语0002李明640001王军850003汤晓影85………726878…学号姓名高数英语0001王军850002李明640003汤晓影85………687278…8.1概述

数据结构及算法排序-PPT全文共117页，当前为第3页。假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri一定在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

学号姓名高数英语思想品德0001王军85880002李明64920003汤晓影8586………687278……排序算法的稳定性：8.1概述

1.排序的基本概念数据结构及算法排序-PPT全文共117页，当前为第4页。待排序序列中的记录已按关键码排好序。待排序序列中记录的排列顺序与排好序的顺序正好相反。学号姓名高数英语思想品德0001王军85880002李明64920003汤晓影8586………687278……8.1概述

1.排序的基本概念正序：逆序（反序）：数据结构及算法排序-PPT全文共117页，当前为第5页。排序的分类在排序的整个过程中，待排序的所有记录全部被放置在内存中,不需要访问外存由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。8.1概述

1.排序的基本概念1.内排序：2.外排序：数据结构及算法排序-PPT全文共117页，当前为第6页。2.内排序算法1.插入排序2.交换排序3.选择排序4.归并排序直接插入排序希尔排序冒泡排序快速排序简单选择排序堆排序8.1概述

数据结构及算法排序-PPT全文共117页，当前为第7页。排序基本过程:是一个逐步扩大记录的有序序列长度的过程3.排序的基本过程有序序列区无序序列区有序序列区无序序列区一趟排序一趟排序:将无序序列区里一个或几个记录合并到有序序列的过程为一趟排序，有序序列长度增加1个或几个8.1概述

数据结构及算法排序-PPT全文共117页，当前为第8页。大家有疑问的，可以询问和交流可以互相讨论下，但要小声点数据结构及算法排序-PPT全文共117页，当前为第9页。4.排序算法的存储结构从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。假定2：将待排序的记录序列排序为升序序列。

r[n+1]假定1：待排序记录采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。8.1概述

101524612354098012345678数据结构及算法排序-PPT全文共117页，当前为第10页。内排序算法1.插入排序2.交换排序3.选择排序4.归并排序直接插入排序希尔排序冒泡排序快速排序简单选择排序堆排序8.1概述

数据结构及算法排序-PPT全文共117页，当前为第11页。8.2插入排序插入排序的主要操作是插入，其基本思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。举例:有序序列2,待排序记录3,6,11）直接插入排序2）希尔排序数据结构及算法排序-PPT全文共117页，当前为第12页。基本思想：在插入第i（i＞1）个记录时，前面的i-1个记录已经排好序。8.2.1直接插入排序有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……有序序列无序序列8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第13页。直接插入排序过程示例

r0123456211825221025*21第一趟18221025*252522212522211025*2522211025*2522211810181025*第二趟18第四趟1825*第三趟第五趟算法稳定吗？21算法思想？i从第2个数到第n个数{将第i个数插入到有序序列中的合理位置}8.2插入排序共多少趟？数据结构及算法排序-PPT全文共117页，当前为第14页。对于r[i]，如何查找它的插入位置?如何实现插入？直接插入排序需解决的关键问题?无序序列2025211826……1)将r[i]暂存在r[0]2)j=i-1；//从第i-1记录开始查找3)当r[j]>r[0]时，循环做{r[j]后移一个位置,j--}4)r[j+1]=r[0]//将r[0]插入到位置j+12201234521ij25j22j218.2插入排序数据结构及算法排序-PPT全文共117页，当前为第15页。直接插入排序无序序列2025101825……2201234510ij25222010jr[0]的作用?暂存单元,监视哨对于r[i]，如何查找它的插入位置?如何实现插入？需解决的关键问题?1)将r[i]暂存在r[0]2)j=i-1；//从第i-1记录开始查找3)当r[j]>r[0]时，循环做{r[j]后移一个位置,j--}4)r[j+1]=r[0]//将r[0]插入到位置j+1jj8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第16页。voidinsertSort(intr[],intn){ for(i=2;i<=n;i++){r[0]=r[i];for(j=i-1;r[0]<r[j];j--)

r[j+1]=r[j];r[j+1]=r[0]; }}直接插入排序算法1.i从第2个到第n个记录,做以下循环：1.1将r[i]暂存在r[0]1.2j=i-1；1.3当r[j]>r[0]时，循环做：{r[j]后移一个位置,j--}1.4r[j+1]=r[0]8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第17页。直接插入排序过程示例

r0123456211825221025*212125i=218221025*25i=318221025*2225222110252221102525*2522211025*252221181018181025*i=418i=61825*i=525218.2插入排序数据结构及算法排序-PPT全文共117页，当前为第18页。直接插入排序练习

125920631248.2插入排序数据结构及算法排序-PPT全文共117页，当前为第19页。直接插入排序练习

[12]592063124初始序列[512]92063124第一趟[5912]2063124第二趟[591220]63124第三趟[5691220]3124第四趟第五趟[569122031]24第六趟[56912202431]8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第20页。1.基本操作。内排序在排序过程中的基本操作：⑴比较：关键码之间的比较；⑵移动：记录从一个位置移动到另一个位置。2.辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。3.算法本身的复杂程度。

排序算法的性能8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第21页。直接插入排序算法性能分析最好情况下：

12345时间复杂度为O(n)。比较次数：n-1移动次数：2(n-1)123452123453123454123455（正序）8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第22页。直接插入排序算法性能分析最好情况下（正序）：

比较次数：n-1移动次数：2(n-1)最坏情况下（逆序）：时间复杂度为O(n2)。54321453214345213234512123451比较次数：移动次数：2)1)(2(2-+=å=nnini2)1)(4(1-+=+ånnin2=i）（时间复杂度为O(n)。8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第23页。平均情况下（随机排列）：

直接插入排序算法性能分析时间复杂度为O(n2)。比较次数：移动次数：4)1)(4(-+=ånnn2=i4)1)(2(2-+=å=nnnii2（21+i）8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第24页。空间性能：需要一个记录的辅助空间。直接插入排序算法是一种稳定的排序算法。直接插入排序算法性能分析直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第25页。8.2.2希尔排序改进的着眼点：（1）由于直接插入排序算法简单，在待排序记录数量n较小时效率也很高。

（2）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高；213543218.2插入排序数据结构及算法排序-PPT全文共117页，当前为第26页。（1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？（2）子序列内如何进行直接插入排序？需解决的关键问题?基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。8.2.2希尔排序201819,657,1322018196571328.2插入排序数据结构及算法排序-PPT全文共117页，当前为第27页。8.2.2希尔排序子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。逐渐缩短“增量”，当缩短为1时就是对全体记录进行排序。1026159182041110261591820411d=3基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第28页。希尔插入排序过程示例

1234567894021254925*16初始序列300813d=4212525*304908401613252125*300849131640d=21325210825*16304940252125*300813164049d=10825211325*16304049082513162125*403049每隔d-1个增量记录分为一组每组内采用直接插入排序8.2插入排序算法稳定吗？数据结构及算法排序-PPT全文共117页，当前为第29页。解决方法：将相隔某个“增量”的记录组成一个子序列。增量应如何取？希尔最早提出的方法是d1=n/2，di+1=di/2。关键问题(1)应如何分割待排序记录？算法描述：for(d=n/2;d>=1;d=d/2){以d为增量，进行组内直接插入排序；}8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第30页。希尔插入排序过程示例

1234567894021254925*16初始序列300813d=4212525*304908401613252125*300849131640每隔d分为一组在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。for(i=d+1;i<=n;i++){}8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第31页。希尔插入排序过程示例

1234567894021254925*16初始序列300813d=4212525*304908401613252125*300849131640每隔d分为一组将插入数据r[i]暂存入r[0]j=i-1当r[j]>r[0]，循环做：{

r[j]后移一位

j--}r[0]插入到位置j+1将插入数据r[i]暂存入r[0]j=i-d当r[j]>r[0]且j>0，循环做：{r[i]后移d位j=j-d;}r[0]插入到位置j+d直接插入排序：希尔排序：8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第32页。解决方法：在插入记录r[i]时，自r[i-d]起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r[0]只是暂存单元，不是哨兵。当搜索位置＜0，表示插入位置已找到。在搜索过程中，记录后移也是跳跃d个位置。在整个序列中，前d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。关键问题(2)子序列内如何进行直接插入排序？8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第33页。算法描述：for(i=d+1;i<=n;i++)//将r[i]插入到所属的子序列中{

r[0]=r[i];//暂存待插入记录j=i-d;//j指向所属子序列的最后一个记录while(j>0&&r[0]<r[j]){r[j+d]=r[j];//记录后移d个位置j=j-d;//比较同一子序列的前一个记录}r[j+d]=r[0];}关键问题(2)子序列内如何进行直接插入排序？8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第34页。voidShellSort(intr[],intn){for(d=n/2;d>=1;d=d/2)//以d为增量,组内直接插入排序for(i=d+1;i<=n;i++)//将r[i]插入到所属的子序列中{r[0]=r[i];//暂存待插入记录j=i-d;//j指向所属子序列的最后一个记录while(j>0&&r[0]<r[j]){r[j+d]=r[j];//记录后移d个位置j=j-d;//比较同一子序列的前一个记录}r[j+d]=r[0];}}希尔插入排序8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第35页。希尔排序练习

12592063124初始序列第一趟结果d=3第二趟结果d=2第三趟结果d=1125920631246592012312456912202431初始化：d=3，d=2d=18.2插入排序数据结构及算法排序-PPT全文共117页，当前为第36页。希尔排序算法的时间性能希尔排序算法的时间性能是所取增量的函数，而到目前为止尚未有人求得一种最好的增量序列。研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3)

。希尔排序不稳定希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。

8.2插入排序数据结构及算法排序-PPT全文共117页，当前为第37页。第八章排序技术本章的基本内容是：排序的基本概念插入排序交换排序选择排序归并排序数据结构及算法排序-PPT全文共117页，当前为第38页。交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。

8.3交换排序反序则交换rirj1）冒泡排序2）快速排序数据结构及算法排序-PPT全文共117页，当前为第39页。8.3.1起泡排序基本思想：两两比较相邻记录的关键码，如果反序则交换，直到没有反序的记录为止。

rj

rj+1ri+1≤……

≤rn-1≤rn

无序区有序区1≤j≤i-1已经位于最终位置反序则交换8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第40页。05981269385381起泡排序过程示例

059812693853810598126938538105981269385381总共n-1趟一共做多少趟？for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++){if(r[j]>r[j+1])r[j]<->r[j+1];}第i趟的比较范围：从1到（n-i）8.3交换排序1234567数据结构及算法排序-PPT全文共117页，当前为第41页。05981269385381起泡排序过程示例

059812693853810598126938538105981269385381提问：一定需要做n-1趟？如果在一趟排序过程中没有进行过交换操作,则排序结束。8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第42页。解决方法：在每一趟起泡排序之前，令exchange的初值为0。在排序过程中，只要有记录交换，用exchange记录交换发生的位置。这样，在一趟排序结束后，只有当exchange的值不为0才需要继续做下一趟冒泡排序。关键问题1)：如何判别起泡排序的结束？intexchange=n;while(exchange){exchange=0;

for(j=1;j<=n-i;j++){if(r[j]>r[j+1]){r[j]<->r[j+1];

exchange=j;}}for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++){if(r[j]>r[j+1])r[j]<->r[j+1];}8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第43页。05981269385381起泡排序过程示例

059812693853810598126938538105981269385381提问：每趟排序只能使待排序范围减1吗？8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第44页。05981269788130起泡排序过程示例

0598123069788105981230697881如果最后一次交换是(位置j)<->(位置j+1)，位置j以后的所有记录均已经有序，即下一趟的待排序范围缩短为1到jjj+18.3交换排序j数据结构及算法排序-PPT全文共117页，当前为第45页。关键问题2）：如何确定每趟起泡排序的范围？解决方法：变量exchange记载的是这趟排序中最后一次交换的位置，而下一趟的排序范围是1到exchange。intexchange=n;while(exchange){bound=exchange;exchange=0;

for(j=1;j<bound;j++){if(r[j]>r[j+1]){r[j]<->r[j+1];

exchange=j;}}intexchange=n;while(exchange){exchange=0;

for(j=1;j<=n-i;j++){if(r[j]>r[j+1]){r[j]<->r[j+1];

exchange=j;}}8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第46页。voidBubbleSort(intr[],intn){ exchange=n;//初始的排序范围是所有记录 while(exchange){

bound=exchange;exchange=0；for(j=1;j<bound;j++)if(r[j]>r[j+1]){r[j]←→r[j+1]； exchange=j；}}}起泡排序算法8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第47页。起泡排序练习

12592063124初始序列第一趟结果第二趟结果第三趟结果第四趟结果[591262024]31[596]12202431[56912202431][56]9122024318.3交换排序数据结构及算法排序-PPT全文共117页，当前为第48页。起泡排序的时间性能分析最好情况：比较次数：n-1移动次数：012345时间复杂度为O(n)。123458.3交换排序（正序）数据结构及算法排序-PPT全文共117页，当前为第49页。最坏情况（反序）：起泡排序的时间性能分析最好情况（正序）：比较次数：n-1移动次数：054321时间复杂度为O(n)；时间复杂度为O(n2)。43215321452134512345比较次数：移动次数：2)1(1-=å=nn(n-i)n-1i2)1(1-=å=n3n3(n-i)n-1i平均情况：时间复杂度为O(n2)。稳定算法8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第50页。内排序算法1.插入排序2.交换排序3.选择排序4.归并排序直接插入排序希尔排序冒泡排序快速排序简单选择排序堆排序8.1概述

数据结构及算法排序-PPT全文共117页，当前为第51页。8.3.2快速排序首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。举例:38275550333049653027333850554965273033384950556527303338495055658.3交换排序算法思想：数据结构及算法排序-PPT全文共117页，当前为第52页。快速排序的基本思想⑴如何选择轴值？⑵如何实现分割（称一次划分）？⑶如何处理分割得到的两个待排序子序列？⑷如何判别快速排序的结束？需解决的关键问题?举例:382755503330496530273338505549658.3交换排序数据结构及算法排序-PPT全文共117页，当前为第53页。选择轴值的方法：1.使用第一个记录的关键码；2.选取序列中间记录的关键码；3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；4.随机选取轴值。关键问题⑴：如何选择轴值？选取不同轴值的后果：决定两个子序列的长度，期望子序列的长度最好相等。8.3交换排序举例:38275550333049653027333850554965数据结构及算法排序-PPT全文共117页，当前为第54页。2750384955关键问题⑵：如何实现一次划分？每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。关键在于数和轴值交换，从前、后两端开始，逐渐向中间轴值逼近的过程。8.3交换排序33275038495533数据结构及算法排序-PPT全文共117页，当前为第55页。关键问题⑵：如何实现一次划分？8.3交换排序1）当轴值在前面时，从后往前扫描，后面数逐个和轴值比较，第一个比轴值小的数和轴值换，小的数放在轴值的前面，轴值就位于待排序区域的后面2）当轴值在后面时，从前往后扫描，前面数逐个和轴值比较，第一个比轴值大的数和轴值换，大的数放在轴值的后面，轴值就位于待排序区域的前面3）当扫描到轴值，轴值就完成了一次划分275038495533275038495533每个数和轴值做比较，比轴值大的数放后面，比轴值小的数放前面。关键在于数和轴值交换，从前后两端开始，逐渐向中间轴值逼近的过程。275038495533完成一次划分O(n)数据结构及算法排序-PPT全文共117页，当前为第56页。30652750384955ji3855关键问题⑵：如何实现一次划分？jjiiijiji=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换8.3交换排序333038652750495533306527504933数据结构及算法排序-PPT全文共117页，当前为第57页。关键问题⑵：如何实现一次划分？i=0,j=n-11)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置8.3交换排序3855ij306527504933j3833306527504955iji3850302733654955ijj数据结构及算法排序-PPT全文共117页，当前为第58页。解决方法：设待划分的序列是r[s]~r[t]，设参数i，j分别指向子序列左、右两端的下标s和t，令r[s]为轴值，（1）j从后向前扫描，直到r[j]<r[i]，将r[j]移动到r[i]的位置(r[j]与r[i]交换)，使关键码小（同轴值相比）的记录移动到前面去；（2）i从前向后扫描，直到r[i]＞r[j]，将r[i]移动到r[j]的位置(r[i]与r[j]交换)

，使关键码大（同轴值比较）的记录移动到后面去；（3）重复上述过程，直到i=j。关键问题⑵：如何实现一次划分？8.3交换排序数据结构及算法排序-PPT全文共117页，当前为第59页。关键问题⑵：如何实现一次划分？算法描述：intPartition(intr[],intfirst,intend){ i=first;j=end;//初始化while(i<j) {while(i<j&&r[i]<=r[j])j--；//右侧扫描

if(i<j){r[i]←→r[j];i++;//将较小记录交换到前面}while(i<j&&r[i]<=r[j])i++；//左侧扫描if(i<j){r[j]←→r[i];j--;//将较大记录交换到后面}}returni;//i为轴值的最终位置}1)j从后往前扫描,找比轴值小的第一个数,和轴值交换2)i从前往后扫描,找比轴值大的第一个数,和轴值交换直到i=j结束，完成一次划分，即轴值的位置

3827551349