w=r [maxi r [max]=r [n-i+l]i r[n-i+1]=w; 1++; 6归并插入排序是对关键字进行比较次数最少的一种内部排序方法,它可按如下步骤 进行: (1)另开辟两个大小为n/2的数组sma11和1arge。从i=1到n-1,对每个奇数的 i,比较x[i]和x[i+1],将较小者和较大者分别依次存入数组sma11和1arge中(当 n为奇数时,sma1ln/2]=x[n]); 对数组1age[1.Ln/2小中元素进行归 并插入排序,同时相应调整sma11中的元素,使得在这一步结束时达到 1age[i]<1arge[i+1],i=1,2,,|n/2」-1 small[i]<large[i], 1=1, 2,,Ln/2J; (3)将sma11[11传送至x[1]中,将1arge[]至1 arge [Ln/2传送至x[2]至 Ln/2H+1]中 (4)定义一组整数inti=(21+1+(-1)3)/3,i=1,2,…,t-1,直至int[txn/21 利用折半插入依次将sma11[int[i+1]至sma11[int[i]+1]插入至x数组中去。例 如,若n=21,则得到一组整数int[1]=1,int[2]=3,int[3]=5,int[4]=11,由 此sma11数组中元素应如下次序:sma113],sma11[2],sma11[5],sma11[4], sma11[11],sma11[10],…,sma11[61,插入到x数组中去。 (5)试以n=5和n=11手工执行归并插入排序,并计算排序过程中所作关键字比较的次 7.请以单链表为存储结构实现简单选择排序的算法 typedef struct( Key type key; JElemType; pede struct Lnode ElemType data struct LNode *next 7Lnode * Linklist Link list sort( Link List L)M为带头结点单链表2 { w=r[max]; r[max]=r[n-i+1]; r[n-i+1]=w; } } i++; } } ⒍归并插入排序是对关键字进行比较次数最少的一种内部排序方法，它可按如下步骤 进行： ⑴另开辟两个大小为n/2的数组 small 和 large。从 i=1 到 n-1，对每个奇数的 i，比较 x[i]和 x[i+1]，将较小者和较大者分别依次存入数组 small 和 large 中（当 n 为奇数时，small[n/2]=x[n]）； ⑵ 对数组 large[1..n/2]中元素进行归 并插入排序，同时相应调整 small 中的元素，使得在这一步结束时达到： large[i]<large[i+1],i=1,2,…,n/2-1, small[i]<large[i], i=1,2,…,n/2; ⑶将 small[1]传送至 x[1]中，将 large[1]至 large[n/2]传送至 x[2]至 x[n/2+1]中； ⑷定义一组整数 int[i]=(2i+1+(-1)i)/3,i=1,2,…,t-1，直至 int[t]>n/2+1, 利用折半插入依次将 small[int[i+1]]至 small[int[i]+1]插入至 x 数组中去。例 如，若 n=21，则得到一组整数 int[1]=1，int[2]=3，int[3]=5，int[4]=11，由 此 small 数组中元素应如下次序：small[3]，small[2]，small[5],small[4]， small[11]，small[10]，…，small[6]，插入到 x 数组中去。 ⑸试以 n=5 和 n=11 手工执行归并插入排序，并计算排序过程中所作关键字比较的次 数。 ⒎请以单链表为存储结构实现简单选择排序的算法。 typedef struct{ KeyType key; … }ElemType; typedef struct Lnode{ ElemType data; struct LNode *next; }Lnode ,*LinkList; LinkList sort ( LinkList L) //L 为带头结点单链表