數據結構考研分類復習真題 第十章 排序[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遞歸所需最大棧空間用量(設一層遞歸用一個單位棧空間)(分)【東南大學 四 (分)】

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22961.html