数据结构考研分类复习真题 第十章 排序[45]

．下面是一改进了的快速分类算法

PROCEDURE qsort(VAR list:afile;mn:integer);

(设list[m]key<list[n+]key)

VAR ijk:integer;

BEGIN

WHILE m<n DO

BEGIN

i:=m;j:=n+; k:=list[m]key;

REPEAT

REPEAT i:=i+ UNTIL list[i]key>=k;

REPEAT j:=j UNTIL list[j]key<=k;

IF i<j THEN interchange (list[i]list[j]);

UNTIL i>=j;

interchange( list[m]list[j]);

IF nj>=jm

THEN BEGIN qsort(listmj+);m:=j+;END

ELSE BEGIN qsort(listj+n);n:=j;END

END;(OF WHILE)

END

问

() 将第行中的＞=＜=分别改成＞＜行吗？为什么？ (分)

() 该排序算法稳定否？举例说明 (分)

() 对输入文件()列表表示该文件在每次调用qsort时的状态及相应mn值(分)

() 若输入文件有n个记录简要说明支持qsort递归所需最大栈空间用量(设一层递归用一个单位栈空间)(分)【东南大学 四 (分)】

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