p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next; p->next->next=t;
} //交换q和s->next两个结点 }//for
}//LinkedList_Select_Sort
9.9假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。
void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序 {
int number[w+1],pos[w+1];
for(i=0;i pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置 for(i=0;i 分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用. 9.10 已知两个有序序列(a1, a2 ,..., am)和(am+1 , am+2 ,..., an),并且其中一个序列的记录个数少于s,且s= floor ( sqrt (n) ). 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。 void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列 { start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;i for(j=start2;j RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位 start1+=k+1; start2=j; //修改两序列尚未归并部分的起始位置 } }//SL_Merge void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18 { len=end-start+1; for(i=1;i<=k;i++) if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p for(i=0;i j=start+i;l=start+(i+k)%len;temp=a[j]; while(l!=start+i) { a[j]=temp; temp=a[l]; a[l]=a[j]; j=l;l=start+(j-start+k)%len; //依次向右移 } a[start+i]=temp; }//for }//RSh 9.11 偶交换排序如下所述：第一趟对所有奇数i,将a[i]和a[i+1]进行比较；第二趟对所有偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1],则将两者交换；第一趟对所有奇数i, 第二趟对所有偶数i，…,依次类推直至整个序列有序为止。 （1） 这种排序方法的结束条件是什么？ （2） 分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。 （3） 写出奇偶交换排序的算法。 void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 { for(p=L;p->next->next;p=p->next) { q=p->next;x=q->data; for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点 if(r->next->data x=r->next->data; s=r; } if(s!=q) //找到了值比q->data更小的最小结点s->next { p->next=s->next;s->next=q; t=q->next;q->next=p->next->next; p->next->next=t; } //交换q和s->next两个结点 }//for }//LinkedList_Select_Sort 9.12 设计一个用链表表示的直接选择排序算法。（与9.8重） 9.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。 （与9.5重复） 9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。 （与9.7类似） 9.15 为什么通常使用一维数组作为堆的存放形式？ 9.16 已知（k1,k2,…，kn）是堆，写一个算法将（k1,k2,…，kn，kn+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。 void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法 { for(i=2;i { //此时从H.r[1]到H.r[i-1]已经是大顶堆 j=i; while(j!=1) //把H.r[i]插入 { k=j/2; if(H.r[j].key>H.r[k].key) H.r[j]<->H.r[k]; j=k; } }//for }//Build_Heap 9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。 9.18 在供选择的答案中填入正确答案： 1）、排序（分类）的方法有许多种：__A_③_法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B①__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C_④__和__D②__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E_⑦_。 供选择答案 ① 选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序 ⑤ 归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序 2）、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79 3）、下列排序算法中， C 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序 9.19 判断正误： （ ）在一个大堆中，最小元素不一定在最后。 （ X ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n）。 （ X ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现象，则称该算法是不稳定的。