10.21折半插入排序 直接插入排序的基本操作是向有序表中插入 个记录,插入位置的确定通过对有序表中记录按关 键码逐个比较得到的。平均情况下总比较次数约为 n24。既然是在有序表中确定插入位置,可以不断二 分有序表来确定插入位置,即一次比较,通过待插 入记录与有序表居中的记录按关键码比较,将有序 表一分为二,下次比较在其中一个有序子表中进行, 将子表又一分为二。这样继续下去,直到要比较的 子表中只有一个记录时,比较一次便确定了插入位
10.2.1 折半插入排序 直接插入排序的基本操作是向有序表中插入一 个记录，插入位置的确定通过对有序表中记录按关 键码逐个比较得到的。平均情况下总比较次数约为 n 2 /4。既然是在有序表中确定插入位置，可以不断二 分有序表来确定插入位置，即一次比较，通过待插 入记录与有序表居中的记录按关键码比较，将有序 表一分为二，下次比较在其中一个有序子表中进行， 将子表又一分为二。这样继续下去，直到要比较的 子表中只有一个记录时，比较一次便确定了插入位 置
二分判定有序表插入位置方法: ①low=;high=j1;r10-ril;∥有序表长度为j l,第个记录为待插入记录 ∥设置有序表区间,待插入记录送辅助单元 ②若low>high,得到插入位置,转⑤ ③lw≤high,m=(ow+high)/2;∥取表的中点, 并将表一分为二,确定待插入区间 ④若r|0 key<rlm. key,high=m-1;/插入位置在 低半区 否则,low=m+1 ∥插入位置在高半区转② ⑤high+1即为待插入位置,从j-到high+1的记录, 逐个后移,rhgh+1]=r0];放置待插入记录
二分判定有序表插入位置方法： ① low=1；high=j-1；r[0]=r[j]； // 有序表长度为j- 1，第j个记录为待插入记录 //设置有序表区间，待插入记录送辅助单元 ② 若low>high，得到插入位置，转⑤ ③ low≤high，m=(low+high)/2； // 取表的中点， 并将表一分为二，确定待插入区间*/ ④ 若r[0].key<r[m].key，high=m-1； //插入位置在 低半区 否则，low=m+1； // 插入位置在高半区转② ⑤ high+1即为待插入位置，从j-1到high+1的记录， 逐个后移，r[high+1]=r[0]；放置待插入记录
【算法103】 void InsertSort(s TBL * /对顺序表作折半插入排序* for(=2; i<=s->length; i++) s->elem[0=s>elem[i;保存待插入元素* Dw=i; high=i-1;/设置初始区间 while(lo<hgh)/该循环语句完成确定插入位置 1 mid=(low+high)/2 if(s->elem[0. key>s->elem mid]. key) low=mid+1;插入位置在高半区中 else high=mid-1;/插入位置在低半区中* 3/ while x/ for(=i-1;j>=high+1;j-)/high+1为插入位置* s->elem[+1}=s> elem li;/后移元素,留出插入空位* A> elem high+1|=s>eml0;/将元素插入 3/*fo 山0 3/*Insertsort*/
【算法10.3】 void InsertSort(S_TBL *s) { /* 对顺序表s作折半插入排序*/ for(i=2；i<=s->length；i++) { s->elem[0]=s->elem[i]； /* 保存待插入元素*/ low=i；high=i-1； /* 设置初始区间*/ while(low<=high) /* 该循环语句完成确定插入位置*/ { mid=(low+high)/2； if(s->elem[0].key>s->elem[mid].key) low=mid+1； /* 插入位置在高半区中*/ else high=mid-1； /* 插入位置在低半区中*/ }/* while */ for(j=i-1；j>=high+1；j--) /* high+1为插入位置*/ s->elem[j+1]=s->elem[j]； /* 后移元素，留出插入空位*/ s->elem[high+1]=s->elem[0]； /* 将元素插入 */ }/* for */ }/* InsertSort */
【时间效率】 确定插入位置所进行的折半查找,关键码的比 较次数至多为log2(mn+1)次,移动记录的次数和 直接插入排序相同,故时间复杂度仍为0()是 个稳定的排序方法。 102.3表插入排序 直接插入排序、折半插入排序均要大量移动记 录,时间开销大。若要不移动记录完成排序,需要 改变存储结构,进行表插入排序。所谓表插入排序, 就是通过链接指针,按关键码的大小,实现从小到 大的链接过程,为此需增设一个指针项。操作方法 与直接插入排序类似,所不同的是直接插入排序要 移动记录,而表插入排序是修改链接指针。用静态 链表来说明
【时间效率】 确定插入位置所进行的折半查找，关键码的比 较次数至多为 ，次，移动记录的次数和 直接插入排序相同，故时间复杂度仍为O(n2 )。是一 个稳定的排序方法。 10.2.3表插入排序 直接插入排序、折半插入排序均要大量移动记 录，时间开销大。若要不移动记录完成排序，需要 改变存储结构，进行表插入排序。所谓表插入排序， 就是通过链接指针，按关键码的大小，实现从小到 大的链接过程，为此需增设一个指针项。操作方法 与直接插入排序类似，所不同的是直接插入排序要 移动记录，而表插入排序是修改链接指针。用静态 链表来说明。 log 2 (n +1)
#define size 200 typedef structi ElemType elem;/元素类型*/ int next;/指针项 JNodeType /表结点类型* typedef structi NodeType rsIzE};/静态链表* int length;表长度* JL TBL; /静态链表类型* 假设数据元素已存储在链表中,且0号单元作为 头结点,不移动记录而只是改变链指针域,将记录 按关键码建为一个有序链表。首先,设置空的循环 链表,即头结点指针域置0,并在头结点数据域中存 放比所有记录关键码都大的整数。接下来,逐个结 点向链表中插入即可
#define SIZE 200 typedef struct{ ElemType elem； /*元素类型*/ int next； /*指针项*/ }NodeType； /*表结点类型*/ typedef struct{ NodeType r[SIZE]； /*静态链表*/ int length； /*表长度*/ }L_TBL； /*静态链表类型*/ 假设数据元素已存储在链表中，且0号单元作为 头结点，不移动记录而只是改变链指针域，将记录 按关键码建为一个有序链表。首先，设置空的循环 链表，即头结点指针域置0，并在头结点数据域中存 放比所有记录关键码都大的整数。接下来，逐个结 点向链表中插入即可