92插入排序 Void BInsertsort( sqlist &l); for (i=2; i<=L length; i++) How=l; high=i-1; Lr[lOri]: while ( lowshigh) im=(lowthigh)/2; if(Lr[·key<Lrm].key)∥<确保稳定,若改为≤,则不稳定 high=m-1; Ise low=m+1 for (k=i-1; k>=high+l; k--)Lr[k+1FL.r[k: Lr[high+1=Lr[0B 3//BInsertsort 移动次数未变,故仍为O(m2)
9.2 插入排序 Void BInsertSort( SqList &L)； { for ( i=2;i<=L.length;i++) {low=1；high=i-1 ； L.r[0]=L.r[i]； while (low≤high) {m=(low+high)/2； if (L.r[i]．key＜L.r[m]．key) //＜确保稳定，若改为≤，则不稳定 high＝ｍ-1; else low=m+1；} for ( k=i-1;k>= high+1;k--) L.r[k+1]=L.r[k]； L.r[high+1]=L.r[0];} }//BInsertSort 移动次数未变，故仍为O(n2 )
92插入排序 希尔排序( Shells methool)(又称为缩小增量排序) 基本思想:分割成若干个较小的子文件,对各个子文件分别进 行直接插入排序,当文件达到基本有序时,再对整个文件进行一次 直接插入排序。 2.依据:(1)若待排序文件基本有序",即文件中具有特性 r[ ikey<Max{rli}1<记录数较少, 则文件中大多数记录都不需要进行插入。 (2)基本有序时,直接插入排序效率可以提高,接近于O(m)
9.2 插入排序 三. 希尔排序（Shell`s Methool）(又称为缩小增量排序) ⒈ 基本思想：分割成若干个较小的子文件，对各个子文件分别进 行直接插入排序，当文件达到基本有序时，再对整个文件进行一次 直接插入排序。 ⒉ 依据：⑴若待排序文件"基本有序" ，即文件中具有特性： r[i].key＜ Max {r[j ]} 1≤j＜i的记录数较少， 则文件中大多数记录都不需要进行插入。 ⑵基本有序时，直接插入排序效率可以提高，接近于O(n)
92插入排序 3.例设初始关键字为:49386597761327495504 第一趟以步长为5分割为5个子文件:(R1,R6)(R2,R7)(R3R8) (R4R6)(R5R10),对每个子文件进行直接插入排序结果为: 13274955044938659776 第二趟以步长为3对第一趟排序结果分割为3个子文件: (R1,R4,R7,R10)(R2,R5,R8)(R3,R6,R9) 对每个子文件进行直接插入排序,结果为: 13044938274955659776 第三趟以步长为1对第二趟排序结果进行直接插入排序,结果为 04132738494955657697
9.2 插入排序 ⒊ 例：设初始关键字为：49 38 65 97 76 13 27 49' 55 04 第一趟以步长为5分割为5个子文件：(R1,R6) (R2,R7) (R3,R8) (R4,R6)(R5,R10)，对每个子文件进行直接插入排序结果为： 13 27 49' 55 04 49 38 65 97 76 第二趟以步长为3对第一趟排序结果分割为3个子文件： (R1,R4,R7,R10)(R2,R5,R8)(R3,R6,R9) 对每个子文件进行直接插入排序，结果为： 13 04 49' 38 27 49 55 65 97 76 第三趟以步长为1对第二趟排序结果进行直接插入排序，结果为： 04 13 27 38 49' 49 55 65 76 97