数据结构 算法评价 若待排序记录按关键字从小到大排列(正序),则 关键字比较次数: 1=n 记录移动次数: 2=2(n-1) 若待排序记录按关键字从大到小排列(逆序),则 关键字比较次数:∑=(+2X(n-1) 记录移动次数:∑(+1) (n+4)(n-1) 若待排序记录是随机的,取平均值,则 关键字比较次数约: 4 记录移动次数约: 时间复杂度:T(m)=Om2 空间复杂度:S(n)=O(1) 直接插入排序是一种稳定的排序方法
数据结构 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) 直接插入排序是一种稳定的排序方法。 算法评价
数据结构 1022其它插入排序 折半插入排序:用折半查找方法确定插入位置。 算法参见P267 例:i=1 (30)1370853942620 213(1330)70853942620 i=76(6133039427085)20 820(133034270)20 i=820 33039427085)20 i=820(613 39427085)20 S m i=820(6 39427085)20 i=820(613203039427085) 时间复杂度:T(n)=O(m2)空间复杂度:S(n)=0(1)m
数据结构 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)
数据结构 1023希尔排序 希尔排序( Shell sort)又称为“缩小增量排 序”。排序过程:先取一个正整数d1<n,把所有 相隔d1的记录放一组,组内进行直接插入排序; 然后取d2<d1,重复上述分组和排序操作;直至 d=1,即所有记录放进一个组中排序为止
数据结构 tjm 10.2.3 希尔排序 希尔排序（Shell Sort）又称为“缩小增量排 序” 。排序过程：先取一个正整数d1<n，把所有 相隔d1的记录放一组，组内进行直接插入排序； 然后取d2<d1，重复上述分组和排序操作；直至 di=1，即所有记录放进一个组中排序为止
数据结构 例:初始:4938659776132748554 取d1=5 趟分组:4938659776132748554 趟排序:1327485544938659776 取d2=3 二趟分组:1327485544938659776 二趟排序: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