2-路插入排序 第十章内部排序 在2-路插入排序中,记录移动的次数会减少 但是不能绝对避免移动记录。 在通常情况下,移动记录的次数约为n2/8。 极端情况下,当r1是待排序记录中关键字 一最小或最大的记录时,2-路插入排序就完全失去 它的优越性。 如希望不移动记录,只有改变存储结构,采 用表插入排序 第16页
第十章 内部排序 第16页 在 2-路插入排序中，记录移动的次数会减少 ，但是不能绝对避免移动记录。 在通常情况下，移动记录的次数约为 n 2 /8。 极端情况下，当 r[1] 是待排序记录中关键字 最小或最大的记录时，2-路插入排序就完全失去 它的优越性。 如希望不移动记录，只有改变存储结构，采 用表插入排序。 2-路插入排序
十表插入排序 第十章内部排序 算法思想:以静态链表作为存储结构(用数组描 述的链表,有整数指示域)。在插入R时,R1到R1 已用指针按关键字不减次序链接起来,这时采用顺序 比较方法找到R应该插入的位置,然后作链表的插 入,使得到从RrR的已排序的链表。如此反复, 直到把Rn插入链表,排序过程结束。 为使插入方便,在数组中多设一个下标为0的分 量作为表头结点,并令表头记录的关键字为最大整数 maxint。排序开始时,先令表头结点和第一个记录结 点组成一个循环链表,然后从2起,依次将第i个 结点插入链表。 表插入排序解决了在排序过程中不移动记录,但 比较次数不变。故其算法的时间复杂度仍是O(n2) 第17页
第十章 内部排序 第17页 表插入排序 算法思想：以静态链表作为存储结构（用数组描 述的链表，有整数指示域）。在插入 Ri 时，R1到Ri-1 已用指针按关键字不减次序链接起来，这时采用顺序 比较方法找到 Ri 应该插入的位置，然后作链表的插 入，使得到从 R1—Ri 的已排序的链表。如此反复， 直到把 Rn 插入链表，排序过程结束。 为使插入方便，在数组中多设一个下标为 0 的分 量作为表头结点，并令表头记录的关键字为最大整数 maxint。排序开始时，先令表头结点和第一个记录结 点组成一个循环链表，然后从 i=2 起，依次将第 i 个 结点插入链表。 表插入排序解决了在排序过程中不移动记录，但 比较次数不变。故其算法的时间复杂度仍是 O(n 2 )
表插入排序 第十章内部排序 用于表插入排序的静态链表数据结构 一# define s工zE100 typedef structi Ectype rc;//关键字,Info int next 1 SLNode i typedef structi SIN。dex[S工z]; int length I SLinkListrypei 示例3设待排序关键字集合同示例1,采用表插入排序算 法 第18页
第十章 内部排序 第18页 用于表插入排序的静态链表数据结构 #define SIZE 100 typedef struct{ RecType rc; //关键字，Info int next } SLNode; typedef struct{ SLNode r[SIZE]; int length; }SLinkListType; 示例3 设待排序关键字集合同示例1，采用表插入排序算 法 表插入排序
一初始main493865977613274义 maxint4938659776132749 2 201 aManin49386597 76132749 2 3-1 0 4 maxint4938659776132749 23140 maxint4938659776132749 231 50 maxint4938659776132749 i=6 6315042 i-7//maxint4938659776132749 63150472 maxint4938659776132749 8 6 81 50 23第9页
第十章 内部排序 第19页 0 1 2 3 4 5 6 7 8 maxint 49 38 65 97 76 13 27 49 1 0 - - - - - - - 初始 maxint 49 38 65 97 76 13 27 49 2 0 1 - - - - - - i=2 maxint 49 38 65 97 76 13 27 49 2 3 1 0 - - - - - i=3 maxint 49 38 65 97 76 13 27 49 2 3 1 4 0 - - - - i=4 maxint 49 38 65 97 76 13 27 49 2 3 1 5 0 4 - - - i=5 maxint 49 38 65 97 76 13 27 49 6 3 1 5 0 4 2 - - i=6 maxint 49 38 65 97 76 13 27 49 6 3 1 5 0 4 7 2 - i=7 maxint 49 38 65 97 76 13 27 49 6 8 1 5 0 4 7 2 3 i=8
表插入排序 第十章内部排序 表插入排序的结果只是求得一个有序链表,为了能应 用有序表的折半查找,尚需对记录进行重新排列。 重排记录的做法是:扫描有序链表,将链表中第 i个结点移动至第i个分量中。 若 SLinklistType rsl; 则一般情况下,若第i个最小关键字的结点是数组中 下标为p且n的分量,则互换r和r1,且令 rs1中指针域的值改为;于此时数组中所有小于i的 分量中已是“到位”的记录,则当时,应顺链绪续查 找直到ni为止。 第20页
第十章 内部排序 第20页 表插入排序的结果只是求得一个有序链表，为了能应 用有序表的折半查找，尚需对记录进行重新排列。 表插入排序 重排记录的做法是：顺序扫描有序链表，将链表中第 i 个结点移动至第i 个分量中。 若 SLinkListType rsl; 则一般情况下，若第 i 个最小关键字的结点是数组中 下标为 p 且 p>i 的分量，则互换 rs1[i] 和 rs1[p]，且令 rs1[i] 中指针域的值改为p；由于此时数组中所有小于 i 的 分量中已是“到位”的记录，则当 p<i 时，应顺链继续查 找直到 p≥i 为止