直接插入排序 第十章内部排序 直接插入排序算法描述(n个记录,共进行n-1趟 插入) straisort( sqlist &l) 对时r1m进行直接插入排序,执行本算法后,r1.n 中的记录按关键字非递减有序排列 for(i=2; i<=lLength; i++) if(l.]. key < lri-1key f r0=lri for(j=i-1; lro. key <lrlil. key;j--) Lr[j+1=rail; .rlj+l=lro 第1页
第十章 内部排序 第11页 直接插入排序算法描述（n 个记录，共进行 n-1 趟 插入） straisort( SqList &l ) //对 r[1..n] 进行直接插入排序，执行本算法后，r[1..n] 中的记录按关键字非递减有序排列 { for( i = 2; i <= l.Length; i++ ) if( l.r[i].key < l.r[i-1].key ) { l.r[0] = l.r[i]; for( j = i – 1; l.r[0].key < l.r[j].key; j-- ) l.r[j+1] = l.r[j]; l.r[j+1] = l.r[0]; } } 直接插入排序
十直接插入排序算法分析 第十章内部排序 直接插入排序算法由两重循环组成,外循环表示要进行n-1 趟插入排序,内循环表明完成一趟排序所需进行的记录关键字间 的比较和记录的后移。 (1)若初始序列按关键字递增有序(简称正序),则 最小比较次数C 最小移动次数0 (2)若初始文件按关键字递减有序(简称逆序或反序),则一 最大比较次数Cm=∑ (n+2)( 2 最小移动次数Mm=(=1+2=(n+4m (3)若初始文件按关键字随机排列,则关键字的比较次数和 移动次数均为(m2)4 故直接入序算法的时厦复杂度为Om)。空间复杂度为OD 直接插入序是稳定的序方法。 第12页
第十章 内部排序 第12页 (1) 若初始序列按关键字递增有序（简称正序），则 最小比较次数 最小移动次数0 直接插入排序算法分析 直接插入排序算法由两重循环组成，外循环表示要进行 n-1 趟插入排序，内循环表明完成一趟排序所需进行的记录关键字间 的比较和记录的后移。 直接插入排序是稳定的排序方法。 (2) 若初始文件按关键字递减有序（简称逆序或反序），则 最大比较次数 最小移动次数 (3) 若初始文件按关键字随机排列，则关键字的比较次数和 移动次数均为 (n 2 )/4 故直接插入排序算法的时间复杂度为 O(n2 )。空间复杂度为O(1)
折半插入排序 第十章内部排序 在直接插入排序的一趟(第i趟)算法中,搜索操作可由在区间一 li-1]进行折半查找来实现。如此进行的插入排序称为折半插 入排序( Binary Insertion Sort BInsertsort( sqlist &l) for(i=2, isllength; itt) iIro=rli low=l; high=1-1 while( low < high im=(low t high)/2; if(lro. key <Irlm. key hight= m-1; else low= m+l 1//while for(j=i-1;j>high+1;j+)+1=rj;∥记录后移 Lr high+I=r0;/插入ri 算法10.4 折半插入排序的时间复杂度仍为O(m2)。减少了比较次数,其排 序方法是稳定的 第13页
第十章 内部排序 第13页 在直接插入排序的一趟 (第 i 趟) 算法中，搜索操作可由在区间 [1,i-1] 上进行折半查找来实现。如此进行的插入排序称为折半插 入排序 (Binary Insertion Sort)。 折半插入排序 BInsertSort( SqList &l ) { for( i = 2; i < l.length; i++ ) { l.r[0] = l.r[I]; low = 1; high = i – 1; while( low <= high ) { m = ( low + high ) / 2; if( l.r[0].key < l.r[m].key ) hight = m – 1; else low = m + 1; } //while for( j = i – 1; j >= high + 1; j++ ) r[j+1] = r[j]; //记录后移 l.r[high+1] = r[0]; //插入 r[i] } //算法 10.4 折半插入排序的时间复杂度仍为O(n 2 )。减少了比较次数，其排 序方法是稳定的
+2-路插入排序 第十章内部排序 在折半插入排序基础上的一种改进算法,其目的是 减少房过程中移动记录的次数,但为比需要n个记录 的我助空间。 算法想:另设一个和L同类型的数组d,将它看成是 个循环向量,并设两个指针frt和fnd分别指示排 序过程中得到的有序序列中的第一个记录和最后一个记 录在d中的位置。首先将r1赋值给a[l,并将d[看 一成是在排好序的序列中处于中间位置的记录,然后从r 中第2个记录起依次插入到a之前或之后的有序序列 中。 第14页
第十章 内部排序 第14页 2-路插入排序 在折半插入排序基础上的一种改进算法，其目的是 减少排序过程中移动记录的次数，但为此需要 n 个记录 的辅助空间。 算法思想：另设一个和 L 同类型的数组 d，将它看成是 一个循环向量，并设两个指针 first 和 final 分别指示排 序过程中得到的有序序列中的第一个记录和最后一个记 录在 d 中的位置。首先将 r[1] 赋值给 d[1]，并将 d[1] 看 成是在排好序的序列中处于中间位置的记录，然后从 r 中第2个记录起依次插入到 d[1] 之前或之后的有序序列 中
示例2设待排序关键字集合同示例1,采用2路插入排序算法 第十章内部排序 「初始关键字438659776132749 49) first final i=2 (49) (38 final first 3 4965) (38) final first i=4 (496597) (38) final first (49657697) 38) final first i=6(49657697) (1338) final first (49657697) 38) final first i=8 (4949657697132738) final first 图10.,22-路插入排序示例 第15页
第十章 内部排序 第15页 示例2 设待排序关键字集合同示例1，采用2-路插入排序算法 [初始关键字] 49 38 65 97 76 13 27 49 i=1 (49) ↑↑ first final i=2 (49) (38) ↑ ↑ final first i=3 (49 65) (38) ↑ ↑ final first i=4 (49 65 97) (38) ↑ ↑ final first i=5 (49 65 76 97) (38) ↑ ↑ final first i=6 (49 65 76 97) (13 38) ↑ ↑ final first i=7 (49 65 76 97) (13 27 38) ↑ ↑ final first i=8 (49 49 65 76 97 13 27 38) ↑ ↑ final first 图 10.2 2-路插入排序示例