★折半插入排序 必排序过程：用折半查找方法确定插入位置的排序叫~ 例 =1 (30)1370853942620 i=213 (13 30)708539426 20 =7 6 (6 13 3039 42 70 85)20 i=820 133039 4270 85)20 m i=820 6-s 30 39 42 70 85)20 i=8 20 (6 13 39 42 70 85)20 s mj i=820 (6 13 9 39 42 70 85)20 i=820 (6 13 203039 427085)
折半插入排序 ❖排序过程：用折半查找方法确定插入位置的排序叫~ 例 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 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s mj i=8 20 (6 13 30 39 42 70 85 ) 20 j s i=8 20 (6 13 20 30 39 42 70 85 )
算法描述 Ch8 2 txt 必算法评价 ●时间复杂度：T(n)=O(n) ●空间复杂度：S)=O(1)》 Ch8 2.c
❖算法描述 ❖算法评价 ⚫时间复杂度：T(n)=O(n²) ⚫空间复杂度：S(n)=O(1) Ch8_2.c
★希尔排序（缩小增量法） 必排序过程：先取一个正整数d1<n,把所有相隔d1的记 录放一组，组内进行直接插入排序；然后取d2<d1, 重复上述分组和排序操作；直至di=1,即所有记录放 进一个组中排序为止
希尔排序(缩小增量法) ❖排序过程：先取一个正整数d1<n，把所有相隔d1的记 录放一组，组内进行直接插入排序；然后取d2<d1， 重复上述分组和排序操作；直至di=1，即所有记录放 进一个组中排序为止
例初始：4938659776132748554 取d1=5 一趟分组：493865977613 274855 4 趟排序：1327485544938659776 取d2=3 二趟分组：13 2748554493865.9776 二趟排序：1344838274955659776 取d3=1 三趟分组：1327485544938 659776 三趟排序：4132738484955657697
取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
必算法描述 Ch8_3.txt #define T 3 intd0={5,3,1; 例 1327485544938659776 一趟排序：1344838274955659776 iitt06111 二趟排序：1344838274955659776 Ch8 3.c
❖算法描述 Ch8_3.c 例 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 i j 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