Ch8 2.c Ch8 2 txt ●折半插入排序所需附加存储空间和直接插入排序相同,从时 间上比较,折半插入排序仅减少了关键字间的比较次数,而 记录的移动次数不变。因此,折半插入排序的时间复杂度仍 为:O(n2) 算法评价 时间复杂度:T(m)=O(n2) 空间复杂度:S(n)=O(1) (2)2-路插入排序 2路插入排序是在折半排序的基础上再改进之,其目的是减 少排序过程中移动记录的次数,但为此需要n个记录的辅助 空间。P267 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 ⚫ 算法评价 Ch8_2.c ⚫ 折半插入排序所需附加存储空间和直接插入排序相同，从时 间上比较，折半插入排序仅减少了关键字间的比较次数，而 记录的移动次数不变。因此，折半插入排序的时间复杂度仍 为： O(n2 ) ⚫ （2）2-路插入排序 ⚫ 2路插入排序是在折半排序的基础上再改进之，其目的是减 少排序过程中移动记录的次数，但为此需要n个记录的辅助 空间。 P267 ⚫ 时间复杂度：T(n)=O(n²) ⚫ 空间复杂度：S(n)=O(1)
3、希尔排序 ●希尔排序又称“缩小增量法” ●基本思想:先将整个待排记录序列分割成若干子序列分 别进行直接插入排序,待整个序列中的记录“基本有 序”时,再对全体记录进行一次直接插入排序。 排序过程:先取一个正整数d1<n,把全部记录分成d1个 组,所有距离为d1倍数的记录放一组,在各组内进行插 入排序;然后取d2<d1,重复上述分组和排序工作;直至 d=1,即所有记录放进一个组中排序为止。 北京邮电大学自动化学院
北京邮电大学自动化学院 12 3、希尔排序 ⚫ 希尔排序又称“缩小增量法” ⚫ 基本思想：先将整个待排记录序列分割成若干子序列分 别进行直接插入排序，待整个序列中的记录“基本有 序”时，再对全体记录进行一次直接插入排序。 ⚫ 排序过程：先取一个正整数d1<n，把全部记录分成d1个 组，所有距离为d1倍数的记录放一组，在各组内进行插 入排序；然后取d2<d1，重复上述分组和排序工作；直至 di=1，即所有记录放进一个组中排序为止
3、希尔排序 例初始:4938659776132748554 取d1=5 趟分组:493865976132748554 一趟排序:1327485544938659776 取d2=3 二趟分组:1327485544938659776 二趟排序:1344838274955659776 取d3=1 三趟分组:1327485544938659776 三趟排序:4132738484955657697 北京邮电大学自动化学院 13
北京邮电大学自动化学院 13 取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 3、希尔排序
算法描述 Ch8 3 txt #define t 3 intd={5,3,1}; 例 1327485544938659776 一趟排序:1344838274955659776 j i iI 二趟排序:1344838274955659776 三趟排序:4132738484955657697 Ch8 3.c 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 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 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 算法描述 三趟排序：4 13 27 38 48 49 55 65 76 97
3、希尔排序 希尔排序的分析是一个复杂的问题,因为它的时间是 所取“增量”序列的函数,这涉及一些数学上尚未解 决的难题。 ●有人在大量的实验基础上推出:当n在某个特定范围 内,希尔排序所需的比较和移动次数约为n13,当 n→>∞时,可减少到n(og2n)2 ●增量序列可以有各种取法,但要注意:应使增量序列 中的值没有除1之外的公因子,并且最后一个增量值 必须等于1。 北京邮电大学自动化学院
北京邮电大学自动化学院 15 ⚫ 希尔排序的分析是一个复杂的问题，因为它的时间是 所取“增量”序列的函数，这涉及一些数学上尚未解 决的难题。 ⚫ 增量序列可以有各种取法，但要注意：应使增量序列 中的值没有除1之外的公因子，并且最后一个增量值 必须等于1。 3、希尔排序 ⚫ 有人在大量的实验基础上推出：当n在某个特定范围 内，希尔排序所需的比较和移动次数约为n 1.3，当 n→ 时，可减少到n(log2n)2