数据结构考研分类复习真题 第十章 答案[41]

void QuickSort(rectype r[n+]; int n)

// 对r[n]进行快速排序的非递归算法

{typedef struct

{ int lowhigh; }node

node s[n+]//栈容量足够大

int quickpass(rectype r[]intint); // 函数声明

int top=; s[top]low=; s[top]high=n;

while (top>)

{ss=s[top]low; tt=s[top]high; top;

if (ss<tt)

{k=quickpass(rsstt);

if (kss>) {s[++top]low=ss; s[top]high=k;}

if (ttk>) {s[++top]low=k+; s[top]high=tt;}

}

} // 算法结束

int quickpass(rectype r[];int st)

{i=s; j=t; rp=r[i]; x=r[i]key;

while (i<j)

{while (i<j && x<=r[j]key) j;

if (i<j) r[i++]=r[j];

while (i<j && x>=r[j]key) i++;

if (i<j) r[j]=r[i];;

]

r[i]=rp;

return (i);

} // 一次划分算法结束

[算法讨论]可对以上算法进行两点改进一是在一次划分后先处理较短部分较长的子序列进栈二是用三者取中法改善快速排序在最坏情况下的性能下面是部分语句片段

int top=; s[top]low=; s[top]high=n;

ss=s[top]low; tt=s[top]high; top; flag=true;

while (flag || top>)

{k=quickpass(rsstt);

if (kss>ttk) // 一趟排序后分割成左右两部分

{if (kss>) // 左部子序列长度大于右部左部进栈

{s[++top]low=ss; s[top]high=k; }

if (ttk>) ss=k+; // 右部短的直接处理

else flag=false; // 右部处理完需退栈

}

else if (ttk>) //右部子序列长度大于左部右部进栈

{s[++top]low=k+; s[top]high=tt; }

if (kss>) tt=k // 左部短的直接处理

else flag=false // 左部处理完需退栈

}

if (!flag && top>)

{ss=s[top]low; tt=s[top]high; top; flag=true;}

} // end of while (flag || top>)

} // 算法结束

int quickpass(rectype r[];int st)

// 用三者取中法进行快速排序的一次划分

{ int i=s j=t mid=(s+t)/;

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 }

// 三者取中最佳次比较次赋值最差次比较次赋值

rp=r[i]; x=r[i]key;

while (i<j)

{while (i<j && x<=r[j]key) j;

if (i<j) r[i++]=r[j];

while (i<j && x>=r[j]key) i++;

if (i<j) r[j]=r[i];;

]

r[i]=rp;

return (i);

} // 一次划分算法结束

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []