【算法101】 ①r0=rjl; ∥r送关r0中,使rj为待插入 记录空位 i=j-1; ∥从第个记录向前测试插入位置 用r0为辅助单元,可兔去测试i1 ⑨若r0 keyer. key,转④。/插入位置确定 ③若r0key< r. key时, r[i+1l=ri;i=-i1;转②。∥调整待插入位置 ④ri+1-r0J;结束。 /放待插入记录
【算法10.1】 ① r[0]=r[j]； //r[j]送r[0]中，使r[j]为待插入 记录空位 i=j-1； //从第i个记录向前测试插入位置， 用r[0]为辅助单元， 可免去测试i<1。 ② 若r[0].key≥r[i].key，转④。 //插入位置确定 ③ 若r[0].key < r[i].key时， r[i+1]=r[i]；i=i-1；转②。 //调整待插入位置 ④ r[i+1]=r[0]；结束。 //存放待插入记录
【例101】向有序表中插入一个记录的过程如下: r{r2]r3r{4r5存储单元 21018259将r5插入四个记录的有序表 中,j r Orll; 初始化,设置待插入位置 2101825 ri+1为待插入位置 i=4,r0<rl,ri+1=rl;i-;调整待插入位置 21018口25 1-3,r0<r,ri+1=rl;r调整待插入位置 2101825 i=2,r0<ri,ri+1=r闻i;i-;调整待插入位置 2口101825 i=1,r0≥r[,ri+1r0;插入位置确定,向空位 填入插入记录 29101825向有序表中插入一个记录的过 程结束
【例10.1】向有序表中插入一个记录的过程如下： r[1] r[2] r[3] r[4] r[5] 存储单元 2 10 18 25 9 将r[5]插入四个记录的有序表 中，j=5 r[0]=r[j]；i=j-1； 初始化，设置待插入位置 2 10 18 25 □ r[i+1]为待插入位置 i=4，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置 2 10 18 □ 25 i=3，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置 2 10 □ 18 25 i=2，r[0] < r[i]，r[i+1]=r[i]；i--； 调整待插入位置 2 □ 10 18 25 i=1，r[0] ≥r[i]，r[i+1]=r[0]； 插入位置确定，向空位 填入插入记录 2 9 10 18 25 向有序表中插入一个记录的过 程结束
直接插入排序方法:仅有一个记录的表总是有 序的,因此,对n个记录的表,可从第二个记录开始 直到第n个记录,逐个向有序表中进行插入操作,从 而得到n个记录按关键码有序的表。 【算法10.2】 void InsertSort(S TBL &p) for(i=2: i<=p->length; i++) if(p->elemi]. key< p->elem i-1.key /小于时,需将eem插入有序表 p>elem0=p->elem[i;为统一算 法设置监测 for(j=i-1: p->elem[]. key p- >elemi key; j--) p>elem+1}=p-> eleme;体记录后移* p->elem+1l=p->elem|0;/插入到正确位置}
直接插入排序方法：仅有一个记录的表总是有 序的，因此，对n个记录的表，可从第二个记录开始 直到第n个记录，逐个向有序表中进行插入操作，从 而得到n个记录按关键码有序的表。 【算法10.2】 void InsertSort(S_TBL &p) { for(i=2；i<=p->length；i++) if(p->elem[i].key < p->elem[i-1].key) /*小于时，需将elem[i]插入有序表*/ { p->elem[0]=p->elem[i]； /*为统一算 法设置监测*/ for(j=i-1 ； p->elem[0].key < p- >elem[j].key；j--) p->elem[j+1]=p->elem[j]； /*记录后移*/ p->elem[j+1]=p->elem[0]；/*插入到正确位置*/}}
效率分析】 空间效率:仅用了一个辅助单元。 时间效率:向有序表中逐个插入记录的操作, 进行了n-1趟,每趟操作分为比较关键码和移动记录, 而比较的次数和移动记录的次数取决于待排序列按 关键码的初始排列。 最好情况下:即待排序列已按关键码有序,每 趟操作只需1次比较2次移动 总比较次数=n-1次 总移动次数=2(n-1)次 最坏情况下:即第j趟操作,插入记录需要同前 面的个记录进行j次关键码比较,移动记录的次数为 j+2次
【效率分析】 空间效率：仅用了一个辅助单元。 时间效率：向有序表中逐个插入记录的操作， 进行了n-1趟，每趟操作分为比较关键码和移动记录， 而比较的次数和移动记录的次数取决于待排序列按 关键码的初始排列。 最好情况下：即待排序列已按关键码有序，每 趟操作只需1次比较2次移动。 总比较次数=n-1次 总移动次数=2(n-1)次 最坏情况下：即第j趟操作，插入记录需要同前 面的j个记录进行j次关键码比较，移动记录的次数为 j+2次
总比较次数=∑j=m(n-1) 总移动次数=∑(+2)=m(n-1)+2n 平均情况下:即第趟操作,插入记录大约同前面的 个记录进行关键码比较,移动记录的次数为j/22次 总比较次数=∑ n(n ≈-n 4 4 总移动次数=∑(4+2)=1m-1)+2n=n j=1 由此,直接插入排序的时间复杂度为O(m2)。是一 个稳定的排序方法
( 1) 2 1 1 1 = = − − = j n n n j j n n n n j ( 1) 2 2 1 ( 2) 1 1 = + = − + − = 总比较次数 总移动次数 平均情况下：即第j趟操作，插入记录大约同前面的j/2 个记录进行关键码比较，移动记录的次数为j/2+2次。 总比较次数 总移动次数 2 1 1 4 1 ( 1) 4 1 2 n n n j n j = = − − = 2 1 1 4 1 ( 1) 2 4 1 2) 2 ( n n n n j n j = + = − + − = 由此，直接插入排序的时间复杂度为O(n2 )。是一 个稳定的排序方法