算法内部排序插入排序.ppt
《算法内部排序插入排序.ppt》由会员分享，可在线阅读，更多相关《算法内部排序插入排序.ppt（31页珍藏版）》请在冰点文库上搜索。
-插入排序
（1）第9章内部排序9.1概述概述9.2插入排序插入排序9.3快速排序快速排序9.4选择排序选择排序9.5归并排序归并排序9.6基数排序基数排序9.7内部排序方法的比较内部排序方法的比较第9章内部排序21.直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）3.表插入排序表插入排序（基于链表存储）（基于链表存储）2.折半插入排序折半插入排序（基于折半查找）（基于折半查找）4.希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）99.2.2插入排序插入排序1.直接插入排序直接插入排序利用利用“顺序查找”“顺序查找”实现实现“在在R1.i-1R1.i-1中中查查找找RiRi的插入位置的插入位置”99.2.2插入排序插入排序插入过程分为两步插入过程分为两步:
在已排好序的表中查找插入位置；在已排好序的表中查找插入位置；插入元素。
插入元素。
不同的插入算法的区别在于第一步的不同不同的插入算法的区别在于第一步的不同从从Ri-1Ri-1起向前进行顺序查找，起向前进行顺序查找，监视哨设置在监视哨设置在R0R0；R0=Ri;/R0=Ri;/设置设置“哨兵哨兵”循环结束表明循环结束表明RiRi的插入位置为的插入位置为j+1j+1对于在查找过程中找到的那些对于在查找过程中找到的那些关键字不小于关键字不小于i.keyi.key的记录，并在查找的同时实现记录向后的记录，并在查找的同时实现记录向后移动；移动；Rj+1=RjRj+1=RjR0R0j+1j+1RiRifor（j=i-1;R0.keyRj.key;-j）;for（j=i-1;R0.keyRj.key;-j）;j=i-1j=i-1插入位置插入位置99.2.2.1.1直接插入排序直接插入排序voidInsertionSort（SqList&L）/对顺序表L作直接插入排序。
for（i=2;i=L.length;+i）if（L.ri.keyL.ri-1.key）/InsertSortL.r0=L.ri;/复制为监视哨for（j=i-1;L.r0.keyL.ri-1.keyi=3L.ri.keyL.ri-1.keyi=4L.r0=L.ri;25*46jj+125*i=5L.ri.keyL.ri-1.key114625*252011i=6L.ri.keyL.ri-1.keyL.r0=L.ri;/复制为监视哨复制为监视哨for（j=i-1;L.r0.keyL.rj.key;-j）L.rj+1=L.rj;/记录后移记录后移L.rj+1=L.r0;/插入到正确位置插入到正确位置064625*2520110606j+1完成完成8排序效率分排序效率分析析
（1）时间复杂度：
时间复杂度：
关键字的比较次数和记录移动次关键字的比较次数和记录移动次数。
数。
（2）空间复杂度：
空间复杂度：
执行算法所需的附加存储空间执行算法所需的附加存储空间。
（3）稳定算法和不稳定算法稳定算法和不稳定算法99.2.2.1.1直接插入排序直接插入排序例例11：
设有关键字序列为：
设有关键字序列为：
7,4,3,29,13,6，直，直接插入排序的过程如图所示：
接插入排序的过程如图所示：
初始记录的关键字：
初始记录的关键字：
74329136第一趟排序：
第一趟排序：
47329136第二趟排序：
第二趟排序：
34729136第三趟排序：
第三趟排序：
34729136第四趟排序：
第四趟排序：
34713296第五趟排序：
第五趟排序：
34671329图图9-1直接插入排序的过程直接插入排序的过程最好的情况（关键字在记录序列中顺序有序）：
最好的情况（关键字在记录序列中顺序有序）：
最坏的情况（关键字在记录序列中逆序有序）：
最坏的情况（关键字在记录序列中逆序有序）：
直接插入排序算法分析：
直接插入排序算法分析：
“比较比较”的次数：
的次数：
“比较比较”的次数：
的次数：
00“移动移动”的次数：
的次数：
“移动移动”的次数：
的次数：
99.2.2.1.1直接插入排序直接插入排序2）1）（4（）1（2nnini2）1）（2（）（2nnini112nni10平均的情况：
平均的情况：
若待排序对象序列中出现各种可若待排序对象序列中出现各种可能排列的概率相同，则可取上述最好情况和最能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。
在平均情况下的关键码比坏情况的平均情况。
在平均情况下的关键码比较次数和对象移动次数约为较次数和对象移动次数约为nn22/4/4。
空间效率：
空间效率：
OO（11）因为仅占用因为仅占用11个缓冲个缓冲单元单元99.2.2.1.1直接插入排序直接插入排序99.2.2.1.1直接插入排序直接插入排序直接插入排序的时间复杂度为直接插入排序的时间复杂度为O（O（nn22）。
直接插入排序是一种稳定的排序方法。
直接插入排序是一种稳定的排序方法。
1299.2.2.2.2折半插入排序折半插入排序当记录数量当记录数量nn的很大时，不宜采取直的很大时，不宜采取直接插入排序的方法。
接插入排序的方法。
因为因为R1.i-1R1.i-1是一个按关键字有是一个按关键字有序的有序序列，则可以利用折半查找序的有序序列，则可以利用折半查找实现“在实现“在R1.i-1R1.i-1中查找中查找RiRi的的插入位置”，如此实现的插入排序为插入位置”，如此实现的插入排序为折半插入排序折半插入排序。
13voidBiInsertionSort（SqList&L）/BInsertSort在L.r1.i-1中折半查找插入位置；for（i=2;i=high+1;-j）L.rj+1=L.rj;/记录后移L.rhigh+1=L.r0;/插入99.2.2.2.2折半插入排序折半插入排序low=1;high=i-1;while（low=high）m=（low+high）/2;/折半if（L.r0.keyL.rm.key）high=m-1;/插入点在低半区elselow=m+1;/插入点在高半区14364952805861239775ilowhighmmlowlowmhigh14364952586180239775ilowhighmhighmhighmlow例如:
再如:
插入插入位置位置插入插入位置位置L.rL.ri=1（30）1370853942620i=213（1330）70853942620i=76（6133039427085）20i=820（6133039427085）20lowhighmidi=820（6133039427085）20lowhighmidi=820（6133039427085）20midhighlowi=820（613203039427085）折半插入排序过程折半插入排序过程时间效率：
时间效率：
在插入第在插入第ii个对象时，需要经过个对象时，需要经过loglog22ii+1+1次关键码的比较，才能确定它应插入的位次关键码的比较，才能确定它应插入的位置。
因此，将置。
因此，将nn个对象用折半插入排序所个对象用折半插入排序所进行的关键码比较次数为：
进行的关键码比较次数为：
n*logn*log22nn但是移但是移动次数并未减少，所以排序效率仍为动次数并未减少，所以排序效率仍为O（nO（n22）。
空间效率：
空间效率：
OO（11）稳定性：
稳定性：
稳定稳定折半插入排序的算法分析折半插入排序的算法分析讨论：
讨论：
若记录是链表结构，用直接插入若记录是链表结构，用直接插入排序行否？
折半插入排序呢？
排序行否？
折半插入排序呢？
答：
答：
直接插入不仅可行，而且还无需移直接插入不仅可行，而且还无需移动元素，时间效率更高！
动元素，时间效率更高！
链表无法“折半”！
折半插入排序的算法分析折半插入排序的算法分析19小结小结直接插入排序的时间复杂性直接插入排序的时间复杂性O（n2）折半插入排序的时间复杂性折半插入排序的时间复杂性O（n2）两种排序方法都是两种排序方法都是稳定的稳定的。
209.2.22-路插入排序路插入排序2-路插入排序是在折半插入排序的基础路插入排序是在折半插入排序的基础上改进而来，其目的是减少排序过程中上改进而来，其目的是减少排序过程中移动记录的次数，但需要移动记录的次数，但需要n个记录的个记录的辅助空间。
辅助空间。
具体做法：
确定中间记录，将待插具体做法：
确定中间记录，将待插记录与中间值比较，小于中间值，则记录与中间值比较，小于中间值，则直直接插入接插入到前半部分的有序表中。
反之，到前半部分的有序表中。
反之，直接插入到后半部分的有序表中。
在算直接插入到后半部分的有序表中。
在算法实现时，可以设两个指针，法实现时，可以设两个指针，first和和final分别指示排序过程中得到的有序分别指示排序过程中得到的有序序列的第一个记录和最后一个记录。
序列的第一个记录和最后一个记录。
2199.2.2.2.22-路插入排序路插入排序排序排序49,38,65,97,76,13,27,49*49493849653849659738496576973849657697133849657697132738分治的思想分治的思想例例229.2.39.2.3希尔希尔（shell）shell）排序排序（又称缩小增量排序）（又称缩小增量排序）基本思想：
基本思想：
对待排记录序列先作对待排记录序列先作“宏观宏观”调整，再调整，再作作“微观微观”调整。
调整。
所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插入排序的插入排序。
技巧：
技巧：
子序列的构成不是简单地子序列的构成不是简单地“逐段分割逐段分割”，而，而是将相隔某个增量是将相隔某个增量dkdk的记录组成一个子序列的记录组成一个子序列,让增量让增量dkdk逐趟缩短（例如依次取逐趟缩短（例如依次取5,3,15,3,1），直到，直到dkdk11为止。
为止。
优点：
优点：
让关键字值小的元素能很快前移，且序列若让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间基本有序时，再用直接插入排序处理，时间效率会高很多。
效率会高很多。
将记录序列分成若干子序列，分别对每个子序列进行插将记录序列分成若干子序列，分别对每个子序列进行插入排序。
入排序。
其中，其中，dd称为增量，它的值在排序过程中从大到小逐称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序渐缩小，直至最后一趟排序减为减为11。
例如：
将n个记录分成d个子序列：
R1，R1+d，R1+2d，R1+kdR2，R2+d，R2+2d，R2+kdRd，R2d，R3d，Rkd，R（k+1）d9.2.39.2.3希尔希尔（shell）shell）排序排序例：
例：
关键字序列关键字序列T=（49T=（49，3838，6565，97,76,13,27,97,76,13,27,4949*，55,0455,04），），请写出希尔排序的具体实现过程。
请写出希尔排序的具体实现过程。
算法分析：
算法分析：
开始时开始时dkdk的值较大，子序列中的对象较少的值较大，子序列中的对象较少，排序速度较快；随着排序进展，排序速度较快；随着排序进展，dkdk值逐渐变值逐渐变小，子序列中对象个数逐渐变多，由于前面工作小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度的基础，大多数对象已基本有序，所以排序速度仍然很快。
仍然很快。
380123456789104938659776132749*5504初态：
第1趟（dk=5）第2趟（dk=3）第3趟（dk=1）4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697rivoidShellInsert（SqList&L,intdk）for（i=dk+1;i=n;+i）if（L.ri.key0&（L.r0.keyL.rj.key）;j-=dk）L.rj+dk=L.rj;/记录后移，查找插入位置L.rj+dk=L.r0;/插入/if/ShellInsert9.2.39.2.3希尔希尔（shell）shell）排序排序voidShellSort（SqList&L,intdlta,intt）/增量为dlta的希尔排序for（k=0;kt;+t）ShellInsert（L,dltak）;/一趟增量为dltak的插入排序/ShellSort9.2.39.2.3希尔希尔（shell）shell）排序排序时间效率：
时间效率：
空间效率：
空间效率：
OO（11）因为仅占用因为仅占用11个缓冲单元个缓冲单元O（O（nn1.251.25）OO（1.61.6nn1.251.25）经验公式经验公式算法分析：
算法分析：
开始时开始时dkdk的值较大，子序列中的对象较少的值较大，子序列中的对象较少，排序速度较快；随着排序进展，排序速度较快；随着排序进展，dkdk值逐渐变值逐渐变小，子序列中对象个数逐渐变多，由于前面工作小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度的基础，大多数对象已基本有序，所以排序速度仍然很快。
仍然很快。
算法的稳定性：
算法的稳定性：
不稳定不稳定9.2.39.2.3希尔希尔（shell）shell）排序排序对特定的待排序对象序列，可以准确地估算关键码的比较次数和对象移动次数。
但想要弄清关键码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。
Knuth利用大量的实验统计资料得出，当n很大时，关键码平均比较次数和对象平均移动次数大约在n1.25到1.6n1.25的范围内。
这是在利用直接插入排序作为子序列排序方法的情况下得到的。
9.2.39.2.3希尔希尔（shell）shell）排序排序
升级会员 