数据结构 算法评价 若待排序记录按关键字从小到大排列（正序），则 关键字比较次数： 21=n-1 记录移动次数： 22=2n-0 若待排序记录按关键字从大到小排列（逆序），则 关键字比较次数： ∑i=m+2n-) 记录移动次数： 之+D = (n+4)(n-1) 2 若待排序记录是随机的，取平均值，则 关键字比较次数约： 记录移动次数约： 时间复杂度：T(n)=O() 空间复杂度：S)=0(1) 直接插入排序是一种稳定的排序方法。 m
数据结构 tjm 若待排序记录按关键字从小到大排列(正序)，则 关键字比较次数： 1 1 2 = − = n n i 记录移动次数： 2 2( 1) 2 = − = n n i 若待排序记录按关键字从大到小排列(逆序)，则 关键字比较次数： 2 ( 2)( 1) 2 + − = = n n i n i 记录移动次数： 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i 若待排序记录是随机的，取平均值，则 关键字比较次数约： 4 2 n 记录移动次数约： 4 2 n 时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1) 直接插入排序是一种稳定的排序方法。 算法评价
数据结构 10.2.2其它插入排序 折半插入排序：用折半查找方法确定插入位置。 算法参见P267 例： i-1 (30) 13 708539426 20 =213(13 30) 70 853942620 i=76 (6 13 30 39 427085)20 i=820 ( 1330 39 427085)20 m i=820 6-s 3939427085)20 j i=820 (6 13 39 427085)20 s mj =820 (6 13 3039 427085)20 i=820 (6 3 203039 427085) 时间复杂度：T(n)=0(n)空间复杂度：S(n)=0(1)
数据结构 tjm 折半插入排序：用折半查找方法确定插入位置。 例： 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 ) 10.2.2 其它插入排序 算法参见P267 时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1)
数据结构 10.2.3希尔排序 希尔排序(Shel1Sort)又称为“缩小增量排 序”。排序过程：先取一个正整数d,<n,把所有 相隔d,的记录放一组，组内进行直接插入排序； 然后取d2<d1,重复上述分组和排序操作；直至 d=1,即所有记录放进一个组中排序为止。 tjm
数据结构 tjm 10.2.3 希尔排序 希尔排序（Shell Sort）又称为“缩小增量排 序” 。排序过程：先取一个正整数d1<n，把所有 相隔d1的记录放一组，组内进行直接插入排序； 然后取d2<d1，重复上述分组和排序操作；直至 di=1，即所有记录放进一个组中排序为止
数据结构 例：初始：4938659776132748554 取d1=5 一趟分组：493865977613 27 48554 一趟排序：1327485544938659776 取d2=3 二趟分组：13 27485544938659776 二趟排序：1344838274955659776 取d3=1 三趟分组：1327485544938659776 三趟排序：4132738484955657697
数据结构 tjm 取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