★折半插入排序 必排序过程：用折半查找方法确定插入位置的 排序叫~ 例 -1 (30)1370853942620 i=213 (13 30)70853942620 i=76 (6 13 30 39 42 70 85)20 i=8 20 1330 39 427085)20 m h i=820 ( B309 4270 85)20 h i=8 20 (6 13 39 42 70 85)20 i=8 20 (6 30 39 4270 85)20 h i=820 (6 13 203039427085)
折半插入排序 ❖排序过程：用折半查找方法确定插入位置的 排序叫~ 例 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 30 39 42 70 85 ) 20 l m h i=8 20 (6 13 30 39 42 70 85 ) 20 l m h i=8 20 (6 13 30 39 42 70 85 ) 20 l mh i=8 20 (6 13 30 39 42 70 85 ) 20 h l i=8 20 (6 13 20 30 39 42 70 85 )
★希尔排序（缩小增量法） 排序过程：先取一个正整数d1<n,把所 有相隔d1的记录放一组，组内进行直接 插入排序；然后取d2<d1,重复上述分 组和排序操作；直至di=1,即所有记录 放进一个组中排序为止
希尔排序(缩小增量法) ❖排序过程：先取一个正整数d1<n，把所 有相隔d1的记录放一组，组内进行直接 插入排序；然后取d2<d1，重复上述分 组和排序操作；直至di=1，即所有记录 放进一个组中排序为止
例初始：4938659776132748554 取d1=5 一趟分组：493865977613 27 48554 一趟排序：1327485544938659776 取d2=3 二趟分组：13 27485544938659776 二趟排序：1344838274955659776 取d3=1 三趟分组：1327485544938 659776 三趟排序：4132738484955 657697
取d3=1 三趟分组：13 27 48 55 4 49 38 65 97 76 三趟排序：4 13 27 38 48 49 55 65 76 97 例 初始： 49 38 65 97 76 13 27 48 55 4 一趟排序：13 27 48 55 4 49 38 65 97 76 二趟排序：13 4 48 38 27 49 55 65 97 76 取d1=5 一趟分组：49 38 65 97 76 13 27 48 55 4 取d2=3 二趟分组：13 27 48 55 4 49 38 65 97 76
#define T 3 int d0={5,3,1}; 例 1327485544938659776 }! 一趟排序：1344838274955659776 I0f:1 二趟排序：1344838274955659776
例 49 38 65 97 76 13 27 48 55 4 #define T 3 int d[]={5,3,1}; j i 13 27 49 38 一趟排序：13 27 48 55 4 49 38 65 97 76 j j i i 4 27 j j i i 55 j i 38 j j j i i i 二趟排序：13 4 48 38 27 49 55 65 97 76 j j i i 48 65 j i 55 97 j i 4 76
必希尔排序特点 ●子序列的构成不是简单的“逐段分割”， 而是将相隔某个增量的记录组成一个子序 列 ●希尔排序可提高排序速度，因为 ◆分组后n值减小，n更小，而T(n)=0(n), 所以T()从总体上看是减小了 ◆关键字较小的记录跳跃式前移，在进行 最后一趟增量为1的插入排序时，序列已 基本有序 ●增量序列取法 ◆无除1以外的公因子 ◆最后一个增量值必须为1
❖希尔排序特点 ⚫子序列的构成不是简单的“逐段分割”， 而是将相隔某个增量的记录组成一个子序 列 ⚫希尔排序可提高排序速度，因为 ◆分组后n值减小，n²更小，而T(n)=O(n²), 所以T(n)从总体上看是减小了 ◆关键字较小的记录跳跃式前移，在进行 最后一趟增量为1的插入排序时，序列已 基本有序 ⚫增量序列取法 ◆无除1以外的公因子 ◆最后一个增量值必须为1