本章习题解答只给岀算法描述,1~6题略。 1.以关键字序列(tim,kay,eva,roy,dot,jon,kim,ann,tom,jim,quy, any)为例,手工执行以下排序算法(按字典序比较关键字的大小),写出每一趟排序结束 时的关键字状态 (1)直接插入排序;(2)冒泡排序:(3)直接选择排序 (4)快速排序 (5)归并排序:(6)基数排序 2已知序列{503,87,512,61,908,170,897,275,653,462},请给出采 用堆排序对该序列做升序排序时的每一趟结果。 3有n个不同的英文单词,它们的长度相等,均为m,若n>>50,m<5,试问采用什 么排序方法时间复杂度最佳?为什么? 4如果只想得到一个序列中第k小元素前的部分排序序列,最好采用什么排序方法? 为什么?如有这样一个序列:(57,40,38,11,13,34,48,75,25,6,19,9, 7}得到其第4个最小元素之前的部分序列[6,7,9,11},使用所选择的算法实现时, 要执行多少次比较 5阅读下列排序算法,并与已学的算法比较,讨论算法中基本操作的执行次数 Void sort(S-TBI &r, int n)( for (j=i+l;3<=n-i I if (r[j]. key<a [min]. key) if (r[j]. key>r[max ]. key) I w=r[minI [min]=r [il r[il=v r min=r
1 本章习题解答只给出算法描述，1~6 题略。 ⒈以关键字序列（tim，kay，eva，roy，dot，jon，kim，ann，tom，jim，guy， amy）为例，手工执行以下排序算法（按字典序比较关键字的大小），写出每一趟排序结束 时的关键字状态： ⑴直接插入排序； ⑵冒泡排序； ⑶直接选择排序； ⑷快速排序； ⑸归并排序； ⑹基数排序。 ⒉已知序列{503，87，512，61，908，170，897，275，653，462}，请给出采 用堆排序对该序列做升序排序时的每一趟结果。 ⒊有 n 个不同的英文单词，它们的长度相等，均为 m，若 n>>50,m<5，试问采用什 么排序方法时间复杂度最佳？为什么？ ⒋如果只想得到一个序列中第 k 小元素前的部分排序序列，最好采用什么排序方法？ 为什么？如有这样一个序列：{57，40，38，11，13，34，48，75，25，6，19，9， 7}得到其第 4 个最小元素之前的部分序列{6，7，9，11}，使用所选择的算法实现时， 要执行多少次比较？ ⒌阅读下列排序算法，并与已学的算法比较，讨论算法中基本操作的执行次数。 Void sort(S-TBL &r,int n){ i=1; while(i<n-i+1) { min=max=1; for(j=i+1;j<=n-i+1;++j) { if (r[j].key<a[min].key) min=j; else if (r[j].key>r[max].key) max=j; } if (min!=i) { w=r[min]; r[min]=r[i]; r[i]=w; } if (max!=n-i+1) { if (max=i) { w=r[min]; r[min]=r[n-i+1]; r[n-i+1]=w; } else
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 为带头结点单链表
p=L->next, while(p->next) q p->next; while(q) if(q->data. key<data. key) q q=q->next, x=p->data; date=s->da S->data=x p=p->next, return L) 8.请以单链表为存储结构实现直接插入排序的算法。 LinkList sort ListList L) /L为带头结点的单链表 >next-next L>next->next=NULL while(p) sp->next; pI
3 { p=L->next ; while (p->next) { s=p; q=p->next; while (q) { if (q->data.key<data.key) s=q ; q=q->next; } if (s!=p) { x=p->data; p->date=s->data; s->data=x; } p=p->next; } return(L); } ⒏请以单链表为存储结构实现直接插入排序的算法。 LinkList sort (ListList L) //L 为带头结点的单链表 { p=L->next->next; L->next->next=NULL; while (p) { s=p->next; pre=L ;
q=L->next while(q & p->data.key >q->data. key) preq q q->next >next-( pre->nextp return(l) 9.编写一个双向冒泡的算法,即相邻两遍向相反方向冒泡 typedef struct( Key type key J ElemType; typedef struct( ElemTy elem int length is table void sort(s table " L) while(flag) flag =0 for (i=j; K<= if (L->elem[i]. key>L->elem[i+l]. key
4 q=L->next; while (q && p->data.key > q->data.key) { pre=q; q=q->next; } p->next=q; pre->next=p; p=s; } return(L); } ⒐编写一个双向冒泡的算法，即相邻两遍向相反方向冒泡。 typedef struct{ KeyType key; … }ElemType; typedef struct{ ElemType *elem; int length; }S_table; void sort(S_table *L) { flag = 1; j = 1; while (flag) { flag = 0; for ( i=j ; i<=L->length-j; i++) if (L->elem[i].key>L->elem[i+1].key ) {
X L->elem[]FL->elem[i+1l L->elem i+1=x; flag=1 for(i=L->length-]; i>=j+l; i--) if (L->elemi].keyL->elemi-l key) x=L->elem [] L->elemi=L->elem[ i-1] L->elem i-1=x; flag=1 return 10.已知记录序列a[1.n]中的关键字各不相同,可按如下所述实现计数排序:另设 数组c[1..n],对每个记录a[i],统计序列中关键字比它小的记录个数存于c[i],则 c[i]=0的记录必为关键字最小的记录,然后依c[i]值的大小对a中记录进行重新排列, 试编写实现上述排序的算法 typedef struct( KevT y ElemType void sort(ElemType *A, ElemType "B, int n) int C[n+1 for(i-1; K<=n; 1++) C[]=0; for(i=1; K<=n; 1++)
5 x=L->elem [i]; L->elem[i]=L->elem[i+1] ; L->elem[i+1]=x; flag=1; } for (i=L->length-j; i>=j+1; i--) if (L->elem[i].key<L->elem[i-1].key) { x=L->elem [i]; L->elem[i]=L->elem[i-1] ; L->elem[i-1]=x; flag=1; } j++; } return; } ⒑已知记录序列 a[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设 数组 c[1..n]，对每个记录 a[i]，统计序列中关键字比它小的记录个数存于 c[i]，则 c[i]=0 的记录必为关键字最小的记录，然后依 c[i]值的大小对 a 中记录进行重新排列， 试编写实现上述排序的算法。 typedef struct{ KeyType key; … }ElemType; void sort (ElemType *A, ElemType *B, int n) { int C[n+1] ; for (i=1 ;i<=n; i++) C[i] = 0; for (i=1; i<=n ; i++)