{ 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;
ss=s[top].low; tt=s[top].high; top--; flag=true; while (flag || top>0)
{k=quickpass(r,ss,tt);
if (k-ss>tt-k) // 一趟排序后分割成左右两部分 {if (k-ss>1) // 左部子序列长度大于右部，左部进栈 {top++; s[top].low=ss; s[top].high=k-1; } if (tt-k>1) ss=k+1; // 右部短的直接处理 else flag=false; // 右部处理完，需退栈 }
else if (tt-k>1) //右部子序列长度大于左部，右部进栈 {top=top+1; s[top].low=k+1; s[top].high=tt; } if (k-ss>1) tt=k-1 // 左部短的直接处理 else flag=false // 左部处理完，需退栈 }
if (!flag && top>0)
{ss=s[top].low; tt=s[top].high; top--; flag=true;} } // end of while (flag || top>0) } // 算法结束
int quickpass(rectype r[];int s,t) // 用“三者取中法”对8.6进行改进 { int i=s, j=t, mid=(s+t)/2; rectype tmp;
if (r[i].key>r[mid].key) {tmp=r[i];r[i]=r[mid];r[mid]=tmp } if (r[mid].key>r[j].key) {tmp=r[j];r[j]=r[mid];
if (tmp>r[i]) r[mid]=tmp; else {r[mid]=r[i];r[i]=tmp } }
{tmp=r[i];r[i]=r[mid];r[mid]=tmp }
// 三者取中：最佳2次比较3次移动；最差3次比较10次移动 rp=r[i]; x=r[i].key; while （i {while (i while (i r[i]=rp; return (i); } // 一次划分算法结束 8.8 viod searchjrec（rectype r[]，int j） //在无序记录r[n]中，找到第j（0<=j { int quichpass (rectype r[],int,int) // 函数声明 i=quichpass(r,0,n-1); // 查找枢轴位置 whilehile(i!=j) if (j 8.9 viod rearrange (rectype r[],int n) //本算法重排具有n个元素的数r，使取负值的关键字放到取非负值的关键字之前。 { int i=0,j=n-1; rp=r[0]; while(i {while(i if(i while(i if(i }//while(i void arrange(rectype r[n+1]; int n) // 对r[1..n]进行整理，使关键字为负值的记录排在非负值的记录之前 [ int i=0, j=-1;rp=r[0]; while (i { while (i if (i if (i r[i]=rp;// }//算法结束 //本算法并未判断轴枢的关键字的正负，在排序中并未和轴枢 //记录比较，而是按正负区分，提高了效率 8.10 typedef struct node {ElemType data; struct node *next; }linklist; void simpleselect(linklist *head) //head是单链表的头指针，本算法对其进行直接选择排序。设p指向无序区第一个记录（开始是链表的第一个记录），用q指向一趟排序中的最小记录，为简便起见，将p和q所指结 点的数据交换。 {p=head->next; while (p->next!=null) // 剩最后一个元素时，排序结束 { q=p; // 设当前结点为最小 s=p->next; // s指向待比较结点 while (s!=null) if (s->data>q->data) s=s->next; else {q=s; s=s->next; }// 用指向新的最小 if (q!=p) {x=q->data; q->data=p->data; p->data=x; } p=p->next; // 链表指针后移，指向下一个最小值结点 } }//算法结束 8.11 按极小化堆取调整（若已是极大化堆则维持不变） （1） （2） （3） （4） 8.11 void heapadjust(K[]，n) //待排序元素在向量K中，从K1到Kn已是堆，现将第n+1个元素加入，本算法这n+1个元素调整成堆。 {rp=K[n+1]; x=K[n+1].key; // 用rp暂存第n+1个元素，x为其关键字 int c=n+1, f=c/2; // 设c表示第n+1个元素的下标，f是其双亲的下标，本算法将子女与双亲比较，若符合堆的定义，则排序结束；否则将双亲和子女交换。之后，双亲的下标为新的子女，再与新的双亲比较，直至根结点（无双亲） while (f>0) if (K[f].key<=x) break; // 已符合堆的定义，排序结束 else {K[c]=k[f]; c=f; f=c/2; } // 仅将双亲移至子女 K[c]=rp;// 将暂存记录rp（原第n+1个记录）放入合适位置 }//算法结束 // 利用上述排序思想，从空堆开始，一个一个添加元素的建堆算法如下： void heapbuilder(rectype R[]) // 向量R的第1到第n个元素为待排序元素，本算法将这n个元素建成堆。 {for (i=0;i void sort(rectype r[],int n) // 对具有n个元素的数组进排序。算法思想是先对数组扫描一遍，形成若干最大有序子 //列，再两两归并，最后完成排序。各子序列的长度（上界和下界）存储在循环队列中，//队头指针指向队头元素的前一位置，队尾指针指向队尾元素。 #define m 100 //子队列长度 { int q[m+1]; i=1; front=0; rear=0; while (i<=n-1) // 该循环求出rear个子序列 { if(r[i+1].key>= r[i].key) i++; q[++rear]=i; // 一个子序列上界 I++; //I指向下一子序列下界 } if(q[rear] //以下为两两归并，当最后只剩下一个有序子序列（即|rear-front=1|）时，合并结束。 while((front+1)%m!=rear) { newrear=rear; while((front+1)%m!=rear) //从r合并到r1中合并 { low=q[front]+1; //取两个子序列界 mid=q[++front%m]; if(front+1%m!=rear) high=q[++front%m]; else high=mid; merge(r,r1,low,mid,high); newrear=(newrear+1)%m; q[newrear]=high; //新子序列上界 } q[front]=0; rear=newrear; //下一轮归并初始化 while((front+1)%m!=rear) //从n拷入r中 { low= q[front]+1; mid=q[++front%m]; if(front+1%m!=rear) high=q[++front%m] else high=mid; merge(r1,r,low,mid,high); newrear=++rear%m; q[newrear]=high; } q[front]=0; rear=newrear; // 下一轮归并从第一个元素开始 }// 最外层的while((front+1)%m!=rear) void merge(rectype a[], a1[],int l,m,h) //设a数组中a[l…..m]和a1[m+1…..h]有序，本算法使l….h有序，并拷贝到a1中 { i=l;j=m+1;k=l-1; while(i<=m&&j<=h) if a[i].key<=a[j].key a1[++k]=a[i++] else a1[++k]=a[j++] while(i<=m) a1[++k]=a[i++]; while(j<=h) a1[++k]=a[j++]; } 8.14 void CountSort(rectype r[]; int n); // 对r[0..n-1]进行计数排序 { int c[n] = {0}; // c数组初始化，元素值指其在r中的位置。如c[i]=j,(0<=i,j for (i=0;i if (r[i]>r[j]) c[i]=c[i]+1 else c[j]=c[j]+1; for (i=0;i while (c[i]!=i) //若c[i] = i，则r[i] 正好是第i个元素;否则，需要调整 { k=c[i]; 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构——用C语言描述》+课后题答案(7)在线全文阅读。
相关推荐：