排序 - 交換排序 - 快速排序 （三）

　　快速排序執行過程

　　快速排序執行的全過程可用遞歸樹來描述

　　

　　

　　分析

　　()遞歸執行的路線如圖中帶箭頭的包絡線所示

　　() 遞歸樹上每一結點左旁方括號表示當前待排序的區間結點內的關鍵字是劃分的基准關鍵字

　　注意

　　葉結點對應的子區間只有一個關鍵字無須劃分故葉結點內沒有基准關鍵字

　　() 劃分後得到的左右兩個子區間分別標在該結點的左右兩個孩子結點的左邊方括號內

　　【例】根結點左旁方括號[ ]表示初始待排序的關鍵字根內的表示所選的劃分基准記錄的關

　　鍵字劃分結果是[][ _]其左右子區間分別標在根結點的兩個孩子的左邊

　　() 每個分支結點右旁圓括號中的內容表示對該結點左旁區間的排序過程結束之後返回的結果它是其左右孩子對應的區間排

　　序完成之後將左右孩子對應的排序結果分別放在該分支結點的關鍵字前後所得到的關鍵字序列

　　【例】分支結點的左右孩子對應的區間排序後的結果分別是(_)和()將它們分別放在的前後即得(

　　)這是對結點左旁區間[ ]排序的結果

　　() 算法的執行順序是遞歸樹中的箭頭順序實際上當把劃分操作視為訪問結點的操作時快速排序的執行過程相當於是先序

　　遍歷其遞歸樹

　　注意

　　任何遞歸算法均可用遞歸樹來描述其執行過程

　　快速排序各次劃分後的狀態變化

　　[ ] //初始關鍵字

　　[ ] [ ] //第次劃分完成之後對應遞歸樹第層

　　[ ] [ ] [ ] [ ] //對上一層各無序區劃分完成後對應遞歸樹第層

　　 [ ] //對上一層各無序區劃分完成後對應遞歸樹第層

　　 //最後的排序結果

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