上传第10章排序习题(4)

【算法源代码】

void dbSort(int r[ ],int n) {int i=1,j,t,b=1; while(b) }

4．写出快速排序的非递归算法。

【算法分析】设对记录空间R[1..n]进行快速排序，要求用非递归算法，可以利用一个栈s来进行，其类型类型为SqStack，每个栈元素含两个域：一个是top域，即栈顶指针；另一个为data域，用于存放元素，其中data数组元素含两个域，一个为low，一个为high，分别指示某个子文件的首、尾记录的首、尾地址，设栈空间最大容量为MAXSIZE，而且假定在整个排序过程中不会发生溢出。

{b=0;

for(j=n-i;j>=i;j--) /*找最小元素*/ if (r[j]

{b=1; t=r[j];r[j]=r[j-1];r[j-1]=t; for(j=i;jr[j+1])

{b=1; t=r[j];r[j]=r[j+1]; i++; }

r[j+1]=t;}

}

【算法源代码】 QuikSort(int R[ ],int n) {int i,j,lw,hg,temp; SqStack *s; s->top=1;

s->data[s->top].low=1;s->data[s->top].high=n;

while(s->top!=0) /*栈非空，则取出一个子文件进行划分*/

{

lw=s->data[s->top].low; hg= s->data[s->top].high; s->top--;

i=lw; j=hg; temp=R[i]; do

{while(itemp)j--; if(i

if (i+1

}

{s->top++;

s->data[s->top].low=i+1; }

s->data[s->top].high=hg;

if (lw

{ s->top++;

s->data[s->top].low=lw; }

s->data[s->top].high=i-1;

5．对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。

【算法分析】利用快速排序方法排序时，若low小于high，此时应找出基准位置，若基准位置恰是要找的第j个位置，则直接返回该位置的数，若刚才的基准位置大于要找位置，则查找区域的上限改为刚才划分的基准位置-1，否则查找区域的下限改为刚才划分的基准位置+1。 【算法源代码】

int QuickSort(SqList R,int j,int low,int high) { int pivotpos; if(low

{ pivotpos=Partition(R,low,high) /*对R[low..high]做划分*/

if (pivotpos==j) return R[j]; else if (pivotpos>j)

return quicksort(R,j,low,pivotpos-1); else

return quicksort(R,j,pivotpos+1,high); } }

6．将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重新编写直接插入排序算法。 【算法分析】

用R[n]作哨兵，则在插入数据时则是由后向前递推，即来一个待插入的数，把该数插入到其后的序列是有序的数据序列中，此时把待插入的数放到R[n]中，然后找到插入其后序列的合适位置，此时需要把后续数据中的部分逐个前移，空出适当位置后，把R[n]中保存的插入值直接放到空位置中去。 【算法源代码】

void InsertSort(SqList R) { int i,j;

for(i=n-2;i>=0;i--) if(R[i].key>R[i+1].key) { 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]插入到正确位置上*/ } }