算法与数据结构_严蔚敏.ppt

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 low high mid i=8 20 (6 13 30 39 42 70 85) 20 low high mid i=8 20 (6 13 30 39 42 70 85) 20 mid high low i=8 20 (6 13 20 30 39 42 70 85) 图10-2 折半插入排序过程 2 2-路插入排序 是对折半插入排序的改进，以减少排序过程中移动记录的次数。附加n个记录的辅助空间，方法是： ① 另设一个和L-R同类型的数组d，L-R[1]赋给d[1]，将d[1]看成是排好序的序列中中间位置的记录； ② 分别将L-R[ ]中的第i个记录依次插入到d[1]之前或之后的有序序列中，具体方法： ◆ L-R[i].keyd[1].key： L-R[i]插入到d[1]之前的有序表中； ◆ L-R[i].key≥d[1].key： L-R[i]插入到d[1]之后的有序表中； 关键点：实现时将向量d看成是循环向量，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个和最后一个记录。 排序示例 设有初始关键字集合{49, 38, 65, 13, 97, 27, 76} ，采用2-路插入排序的过程如右图10-3所示。 在2-路插入排序中，移动记录的次数约为n2/8 。但当L-R[1]是待排序记录中关键字最大或最小的记录时，2-路插入排序就完全失去了优越性。 27 76 d 49 first first first first final final final final 65 38 97 97 13 13 图10-3 2-路插入排序过程 3 表插入排序 前面的插入排序不可避免地要移动记录，若不移动记录就需要改变数据结构。附加n个记录的辅助空间，记录类型修改为： typedef struct RecNode { KeyType key ; infotype otherinfo ; int *next; }RecNode ; 初始化：下标值为0的分量作为表头结点，关键字取为最大值，各分量的指针值为空； ① 将静态链表中数组下标值为1的分量(结点)与表头结点构成一个循环链表； ② i=2 ，将分量R[i]按关键字递减插入到循环链表； ③ 增加i ，重复②，直到全部分量插入到循环链表。 例：设有关键字集合{49, 38, 65, 97, 76, 13, 27, 49} ，采用表插入排序的过程如下图10-4所示。 0 1 2 3 4 5 6 7 8 key域 next域 MAXINT 49 38 65 13 97 27 76 49 1 0 - - - - - - - i=2 MAXINT 49 38 65 13 97 27 76 49 2 0 1 - - - - - - i=3 MAXINT 49 38 65 13 97 27 76 49 2 3 1 0 - - - - - i=4 MAXINT 49 38 65 13 97 27 76 49