Algorithms and DataStructures:Sorting 2、插入排序 2、折半插入排序 方法：在已排序的序列中查找下一 36 24 10 6 12 元素的插入位置，将该元素插入进 去，形成更长的排序序列。如：12 low high 的插入位置为下标3。 ↓ 减少了比较次数，未降低时 12 6 10 24 36 12 间复杂性。 low high 12 6 10 24 36 12 high low li 12 6 10 24 36 12 26 SORT
26 物料管理 SORT Algorithms and DataStructures:Sorting 26 2、插入排序 2、折半插入排序 36 24 10 6 12 24 36 12 high 6 10 12 12 方法：在已排序的序列中查找下一 元素的插入位置，将该元素插入进 去，形成更长的排序序列。如：12 的插入位置为下标3。 减少了比较次数，未降低时 间复杂性。 i low 12 24 36 12 high 6 10 12 i low 12 24 36 12 high 6 10 12 i low
Algorithms and DataStructures:Sorting 2、插入排序 2、折半插入排序 方法：在已排序的序列中查找下一 36 24 10 6 25 元素的插入位置，将该元素插入进 去，形成更长的排序序列。如：12 low high 的插入位置为下标3。 ↓ 减少了比较次数，未降低时 25 6 10 24 36 25 间复杂性。 low high 25 6 10 24 36 25 high low 25 6 10 24 36 25 27 SORT
27 物料管理 SORT Algorithms and DataStructures:Sorting 27 2、插入排序 2、折半插入排序 36 24 10 6 25 24 36 12 high 6 10 25 25 方法：在已排序的序列中查找下一 元素的插入位置，将该元素插入进 去，形成更长的排序序列。如：12 的插入位置为下标3。 减少了比较次数，未降低时 间复杂性。 i low 25 24 36 12 high 6 10 25 i low 25 6 10 24 36 1225 i high low
Algorithms and DataStructures:Sorting 2、插入排序 3.2-路插入排序 [初始关键字]： 4938 659776132749 排序过程中d的状态如下： 只能减少移动记录次数，不 i=1: (49) 能绝对避免移动记录。移动 fist↑final 记录的次数约为n28。当中 i=2: (49) (38) 间位置选择为最小或最大值 ↑final 个first 时，退化为直接插入排序。 i=3: (4965) (38) ↑final 个first i=4: (496597) (38) ↑final ↑first i=5: (49657697) (38) ↑final ↑first i=6 (49657697) (1338) final ↑first (49657697) i=7: (132738) ◆final ↑first =8: (49496576971327 38) final first SORT
28 物料管理 SORT Algorithms and DataStructures:Sorting 2、插入排序 3. 2-路插入排序 只能减少移动记录次数，不 能绝对避免移动记录。移动 记录的次数约为n2 /8。当中 间位置选择为最小或最大值 时，退化为直接插入排序
0 1 2 3 45 6 7 8 2、插入排序 MAXINT 49 38 65 13 49 初始状态 key域 1 next域 4.表插入排序 MAXINT 49 38 65 97 3 49 元=2 2 基本操作仍是将一个记录插 MAXINT 49 49 入到已派好序的有序表中， i=3 唯一不同之处在于是以修改 2 2n次指针值代替移动记录。 MAXINT 493 9 复杂度为0(n2) i=4 2 MAXINT 4938 49 i=5 2 3 MAXINT 49386597 7613 2749 i=6 6 3 MAXINT 49 38 65 97 7613 2749 i=7 6 31 MAXINT 49386597 76 132749 t=8 6 81504 723 SORT
29 物料管理 SORT Algorithms and DataStructures:Sorting 2、插入排序 4. 表插入排序 基本操作仍是将一个记录插 入到已派好序的有序表中， 唯一不同之处在于是以修改 2n次指针值代替移动记录。 复杂度为O（n2）
Algorithms and DataStructures:Sorting 2、插入排序 2、 shell排序 ■又称“缩小增量排序”(Diminishing Increment Sort)) ■从直接插入排序的分析可知，当待排记录序列为“正序” 时，其时间复杂度可提高到O(),由此可设想，若待排记 录序列按关键字“基本有序”时，直接插入排序的效率也 比较高；另外，由于直接插入排序算法简单，在值很小时 效率也较高。因此从这两点出发设计一种算法就可以提高 排序的效率。 ■先将整个待排记录序列分割成若干个子序列分别进行直接 插入排序，待整个序列中的记录“基本有序“时，再对全 体记录进行一次直接插入排序，就可以完成整个的排序工 作。 ■希尔排序的一个特点是：子序列的构成不是简单地“逐段 分割”，而是将相隔某个增量的记录组成一个子序列。 SORT
30 物料管理 SORT Algorithms and DataStructures:Sorting 2、插入排序 ◼ 又称“缩小增量排序”(Diminishing Increment Sort) ◼ 从直接插入排序的分析可知，当待排记录序列为“正序” 时，其时间复杂度可提高到O(n)，由此可设想，若待排记 录序列按关键字“基本有序”时，直接插入排序的效率也 比较高；另外，由于直接插入排序算法简单，在n值很小时 效率也较高。因此从这两点出发设计一种算法就可以提高 排序的效率。 ◼ 先将整个待排记录序列分割成若干个子序列分别进行直接 插入排序，待整个序列中的记录“基本有序“时，再对全 体记录进行一次直接插入排序，就可以完成整个的排序工 作。 ◼ 希尔排序的一个特点是：子序列的构成不是简单地“逐段 分割”，而是将相隔某个增量的记录组成一个子序列。 2、 shell 排序