★折半插入排序 排序过程:用折半查找方法确定插入位置的排序叫 例 (30)1370853942620 =213(1330)70853942620 76(6133039427085)20 i=820(6133039427085)20 m 1820(433939427085)20 1820(6133939427085)20 s m 1820(6133939427085)20 i=820(613203039427085)
折半插入排序 ❖排序过程：用折半查找方法确定插入位置的排序叫~ 例 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 txt ◆算法评价 ●时间复杂度:T(n)=O(n2) ●空间复杂度:S(n)=O(1) Ch8 2.c
❖算法描述 ❖算法评价 ⚫时间复杂度：T(n)=O(n²) ⚫空间复杂度：S(n)=O(1) Ch8_2.c
★希尔排序(缩小增量法) 排序过程:先取一个正整数d1<n.把所有相隔d1的记 录放一组,组内进行直接插入排序;然后取d2<d1, 重复上述分组和排序操作;直至d=1,即所有记录放 进一个组中排序为止
希尔排序(缩小增量法) ❖排序过程：先取一个正整数d1<n，把所有相隔d1的记 录放一组，组内进行直接插入排序；然后取d2<d1， 重复上述分组和排序操作；直至di=1，即所有记录放 进一个组中排序为止
例初始:4938659776132748554 取d1=5 趟分组:4938659776132748554 趟排序:1327485544938659776 取d2=3 趟分组:1327485544938659776 趟排序:1344838274955659776 取d3=1 三趟分组:1327485544938659776 三趟排序: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 intd]={5,3,1} 1327485544938659776 趟排序:134′4838274955659776 1 11 二趟排序: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