数据结构后习题答案第八章.docVIP

第八章 排序（参考答案） 本章所用数据结构 #define N 待排序记录的个数 typedef struct { int key; ElemType other; }rectype; rectype r[n+1]; // r为结构体数组 8.2 稳定排序有：直接插入排序、起泡排序、归并排序、基数排序 不稳定排序有：希尔排序、直接选择排序、堆排序 希尔排序例：49，38， 49，90，70，25 直接选择排序例：2， 2，1 堆排序例：1，2，2 8.3 void StlinkedInsertSort(s , n); // 对静态链表s[1..n]进行表插入排序， 并调整结果，使表物理上排序 { #define MAXINT 机器最大整数 typedef struct { int key; int next; }rec; rec s[n+1]; // s为结构体数组 s[0].key=maxint; s[1].next=0; //头结点和第一个记录组成循环链表 i=2; //从第2个元素开始，依次插入有序链表中 while (i=n) {q=0; p=s[0].next; // p指向当前最小元素，q是p的前驱 while (p!=0 s[p].keys[i].key) // 查找插入位置 { q=p; p=s[p].next; } s[i].next=p; s[q].next=i; // 将第个元素链入 i++； } // while(i=n) 静态链表的插入 // 以下是重排静态链表，使之物理有序 i=1; p=s[0].next; while (i=n) {WHILE (pi) p=s[p].next; q=s[p].next; if (i!=p) { s[i]((s[p]; s[i].next=p; p=q; i++; } } }//算法结束 8.4 void TwoWayBubbleSort( rectype r[n+1]; int n) // 对r[1..n]进行双向冒泡排序。即相邻两遍向两个相反方向起泡 { int i=1, exchange=1; // 设标记 while (exchange) { exchange=0; // 假定本趟无交换 for (j=n-i+1 j=i+1;j--) // 向前起泡，一趟有一最小冒出 if (r[j]r[j-1]) {r[j](r[j-1]; exchange=1;} // 有交换 for (j= i+1;j=n-I;j++) // 向后起泡，一趟有一最大沉底 if (r[j]r[j+1]) {r[j](r[j+1]; exchange=1;} // 有交换 i++; } // end of WHILE exchange }//算法结束 8.5 （1）在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成 相等程度的序列（各3个元素），再各进行2次比较，完成全部排序。 （2）最好的初始排列：4，1，3，2，6，5，7 8.6 void QuickSort(rectype r[n+1]; int n) // 对r[1..n]进行快速排序的非递归算法 { typedef struct { int low,high; }node node s[n+1]； int top; int quickpass(rectype r[],int,int); // 函数声明 top=1; s[top].low=1; s[top].high=n; while (top0) {ss=s[top].low; tt=s[top].high; top--; if (sstt) { k=quickpass(r,ss,tt); if (k-ss1) {top++; s[top].low=ss; s[top].high=k-1;} if (tt-k1) {top++; s[top].low=k+1; s[top].high=tt;} } } // 算法结束 int quickpass(rectype r[];int s,t) {i=s; j=t; rp=r[i]; x=r[i].key; while （ij） {while (ij x=r[j].key) j--; if (ij) r[i++]=r[j]; while (ij x=r[j].key) i++;