1、直接插入排序 般情况下,第j趟直接插入排序的操作为: 在含有i-1个记录的有序子序列r1.-1中插入一个记录r[ 后,变成含有个记录的有序子序序列r1. ●并且,和顺序查找类似,为了在查找插入位置的过程中避 免数组下标出界,在r[0处设置监视哨。 在自-1起往前搜索的过程中,可以同时后移记录。 整个排序过程为进行n-1趟插入,即:先将序列中的第一个记 录看成是一个有序序列的子序,然后从第2个记录起逐个进行 插入直至整个序列变成按关键字非递减有序序列为止。 北京邮电大学自动化学院
北京邮电大学自动化学院 6 ⚫ 一般情况下，第i趟直接插入排序的操作为： ⚫ 在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i] 后，变成含有i个记录的有序子序序列r[1…i]； ⚫ 并且，和顺序查找类似，为了在查找插入位置的过程中避 免数组下标出界，在r[0]处设置监视哨。 ⚫ 整个排序过程为进行n-1趟插入，即：先将序列中的第一个记 录看成是一个有序序列的子序，然后从第2个记录起逐个进行 插入直至整个序列变成按关键字非递减有序序列为止。 ⚫ 在自i-1起往前搜索的过程中，可以同时后移记录。 1、直接插入排序
1、直接插入排序 例 (49386597761327 Chi Txt i=238(3849)6597761327 i365(384965)97761327 i=497(38496597)761327 i=576(3849657697)1327 613(133849657697)27 i727(13273849657697 排序结果:(3273849657697) 北京邮电大学自动化学院
北京邮电大学自动化学院 7 例 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 i=1 ( ) i=7 (13 38 49 65 76 97) 27 27 j j j j j j 27 38 49 65 76 97 排序结果：(13 27 38 49 65 76 97) 1、直接插入排序
1、直接插入排序 Ch8 txt 当待排序列中记录按关键字非递减有序排列(正序)所需进行 关键字间比较的次数达最小值义1=n-1 记录不需要移动 当待排序列中记录按关键字非递增有序排列(逆序)所需 进行关键字间比较的次数达最大值∑=(+2n= 记录移动的次数也达到最大值之(+1)=(n+X 2 我们可取上述最小值和最大值的平均值,作为直接插入排序时 所需进行关键字间的比较次数和移动记录的次数,约为n24 由此,直接插入排序的时间复杂度为o(n2)。 ch8 1.c 北京邮电大学自动化学院
北京邮电大学自动化学院 8 Ch8_1.c ⚫ 当待排序列中记录按关键字非递减有序排列(正序）所需进行 关键字间比较的次数达最小值 1 1 2 = − = n n i 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i 2 ( 2)( 1) 2 + − = = n n i n i ⚫ 记录移动的次数也达到最大值 ⚫ 当待排序列中记录按关键字非递增有序排列（逆序）所需 进行关键字间比较的次数达最大值 ⚫ 我们可取上述最小值和最大值的平均值，作为直接插入排序时 所需进行关键字间的比较次数和移动记录的次数，约为n 2 /4。 由此，直接插入排序的时间复杂度为O（ n 2）。 ⚫ 记录不需要移动。 1、直接插入排序
2、其它插入排序 ●(1)折半插入排序 ●由于插入排序的基本操作是在一个有序表中进行查找和插 入,则从上章的讨论可知,这个“查找”操作可利用“折半 查找”来实现,由此进行的插入排序称之为折半插入排序。 ●直接插入排序的基本操作是向有序表中插入一个记录,平均情况 下总比较次数约为n214。既然是在有序表中确定插入位置,可以 不断二分有序表来确定插入位置,通过待插入记录与有序表居中 的记录按关键码比较,将有序表一分为二,下次比较在其中一个 有序子表中进行,这样继续下去,直到要比较的子表中只有一个 记录时,比较一次便确定了插入位置。 北京邮电大学自动化学院
北京邮电大学自动化学院 9 2、其它插入排序 ⚫ （1）折半插入排序 ⚫ 由于插入排序的基本操作是在一个有序表中进行查找和插 入，则从上章的讨论可知，这个“查找”操作可利用“折半 查找”来实现，由此进行的插入排序称之为折半插入排序。 ⚫ 直接插入排序的基本操作是向有序表中插入一个记录，平均情况 下总比较次数约为n 2 /4。既然是在有序表中确定插入位置，可以 不断二分有序表来确定插入位置，通过待插入记录与有序表居中 的记录按关键码比较，将有序表一分为二，下次比较在其中一个 有序子表中进行，这样继续下去，直到要比较的子表中只有一个 记录时，比较一次便确定了插入位置
●折半插入排序 (30)1370853942 20 i=213(1330)70853942620 6(6133039427085)20 i=820 133039427085)20 m i-820(9133039427085)20 i=820(613.3039427085)20 F=820(6 3039427085)20 i=820613203039427085 北京邮电大学自动化学院 10
北京邮电大学自动化学院 10 i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85 ) 20 …. i=8 20 (6 13 20 30 39 42 70 85 ) ⚫折半插入排序 i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 j s