算法的时间复杂度 O(n)； 讨论算法中记录的最大移动次数。
void Divide(int a[ ],int n)//把数组a 中所有值为负的记录调到非负的记录之前 {
low=0;high=n-1; while(low while(low while(low }//Divide 9．8 试以单链表为存储结构实现简单选择排序的算法 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．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, a 2,..., a m)和(a m+1 , a m+2 ,..., a n ),并且其中一个序列的记录个数少于s,且s=?√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．12 设计一个用链表表示的直接选择排序算法。 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．16 已知（k1,k2,?k n）是堆，写一个算法将（k1,k2,?，k n，k n+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/