┌──┐ 0│ ∧ │ ├──┤
1│ → 0.13→0.16→ ∧ ├──┤
2│ →0.20→ ∧ ├──┤ 3│ →0.39→ ∧ ├──┤
4│ →0.42→ ∧ ├──┤
5│ →0.53→ ∧ ├──┤
6│ →0.64→ ∧ ├──┤
7│ →0.71→0.79→ ∧ ├──┤
8│ →0.89→ ∧ ├──┤ 9│ ∧ │ └──┘
结果为：0.13 0.16 0.20 0.39 0.42 0.53 0.64 0.71 0.79 0.89
11.若关键字是非负整数、快速排序、归并、堆和基数排序啊一个最快?若要求辅助空间为O(1)，则应选择谁? 若要求排序是稳定的，且关键字是实数，则应选择谁? 答：
若关键字是非负整数，则基数排序最快；若要求辅助空间为O(1)，则应选堆排序；若要求排序是稳定的，且关键字是实数，则应选归并排序，因为基数排序不适用于实数，虽然它也是稳定的。
12.对于8.7节的表8.2，解释下述问题：
(1)当待排序的关键字序列的初始态分别为正序和反序时，为什么直接选择排序的时间基本相同?若采用本书8.4.1节的算法，这两种情况下的排序时间是否基本相同?
(2)为什么数组的初态为正序时，冒泡和直接插入排序的执行时间最少?
(3)若采用8.3.2节的快速排序，则数组初态为正序和反序时，能得到与表8.2类似的结果吗? 答：
(1)由于在直接选择排序中，主要的操作是比较操作和移动操作。无论文件的初始状态如何，若文件有n个记录，则都要进行n-1趟直接选择排序，第i趟直接选择排序中都要做n-i次比较才能选出最小关键字的记录。所以总的比较次数都为O(n2)。至于记录的移动次数，初始文件为正序时，移动次数为0，当文件初始时为反序，总的移动次数为3(n-1)。因此当待排序的关键字序列的初始态分别为正序和反序时，直接选择排序的时间基本相同，为O(n2)。若采用本书8.4.1节的算法，这两种情况下的排序时间基本相同。
(2)当冒泡排序是正序时，只需做一趟冒泡排序就可完成，共做n-1次比较，移动次数为0，所以执行时间最少。而直接插入排序时，若初始为正序，则做了n-1趟直接插入排序，但每趟排序只做了一次比较，共做n-1次比较。移动次数为0。所以当数组初态为正序，直接插入排序时间也最少。
(3)不能，其中辅助空间不同
13. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。 解：
重写的算法如下： void InsertSort(SeqList R)
{//对顺序表中记录R[0..n-1]按递增序进行插入排序 int i,j;
for(i=n-2;i>=0;i--) //在有序区中依次插入R[n-2]..R[0] if(R[i].key>R[i+1].key) //若不是这样则R[i]原位不动 {
R[n]=R[i];j=i+1; //R[n]是哨兵
do{ //从左向右在有序区中查找插入位置
R[j-1]=R[j]; //将关键字小于R[i].key的记录向右移 j++;
}while(R[j].key R[j-1]=R[n]; //将R[i]插入到正确位置上 }//endif }//InsertSort. 14.以单链表作为存储结构实现直接插入排序算法。 解： #define int KeyType //定义KeyType 为int型 typedef struct node{ KeyType key; //关键字域 OtherInfoType info; //其它信息域， struct node * next; //链表中指针域 }RecNode; //记录结点类型 typedef RecNode * LinkList ; //单链表用LinkList表示 void InsertSort(LinkList head) {//链式存储结构的直接插入排序算法,head是带头结点的单链表 RecNode *p,*q,*s; if ((head->next)&&(head->next->next))//当表中含有结点数大于1 { p=head->next->next;//p指向第二个节点 head->next=NULL; q=head;//指向插入位置的前驱节点 while(p)&&(q->next)&&(p->key {s=p;p=p->next;// 将要插入结点摘下 s->next=q->next;//插入合适位置：q结点后 q->next=s; } } } 15.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。请分析算法的时间复杂度。 解： 因为只需将负数关键字排在前面而无需进行精确排列顺序，因此本算法采用两端扫描的方法，就象快速排序采用的方法一样，左边扫描到正数时停止，开始扫描右边，遇到负数时与左边的当前记录交换，如此交替进行，一趟下来就可以完成排序。 void ReSort(SeqList R) {//重排数组，使负值关键字在前 int i=1,j=n; //数组存放在R[1..n]中 while (i { while(i R[0]=R[i]; //R[0]为辅助空间 while(i R[i++]=R[j];R[j--]=R[0];//交换当前两个元素并移动指针 }//endwhile }//ReSort 本算法在任何情况下的比较次数均为n(每个元素和0)相比，交换次数少于n/2，总的来说，时间复杂度为O(n).
相关推荐：
loading