計算機應用專業上機考試指導：排序算法的各趟排序算法

　　以關鍵字序列 ()為例分別寫出執行以下排序算法的各趟排序結束時關鍵字序列的狀態

　　() 直接插入排序 ()希爾排序 ()冒泡排序 ()快速排序

　　() 直接選擇排序 () 堆排序 () 歸並排序 ()基數排序

　　上述方法中哪些是穩定的排序?哪些是非穩定的排序?對不穩定的排序試舉出一個不穩定的實例

　　答

　　()直接插入排序:(方括號表示無序區)

　　初始態 : [ ]

　　第一趟 [ ]

　　第二趟 [ ]

　　第三趟 [ ]

　　第四趟 [ ]

　　第五趟 [ ]

　　第六趟 [ ]

　　第七趟 [ ]

　　第八趟 []

　　第九趟

　　()希爾排序(增量為)

　　初始態 :

　　第一趟

　　第二趟

　　第三趟

　　()冒泡排序(方括號為無序區)

　　初始態 [ ]

　　第一趟 [ ]

　　第二趟 [ ]

　　第三趟 [ ]

　　第四趟 [ ]

　　第五趟 [ ]

　　第六趟

　　()快速排序(方括號表示無序區層表示對應的遞歸樹的層數)

　　初始態 [ ]

　　第二層 [ ] [ ]

　　第三層 [] [ ] [ ]

　　第四層 [] [ ] []

　　第五層 []

　　第六層

　　()直接選擇排序(方括號為無序區)

　　初始態 　[ ]

　　第一趟 [ ]

　　第二趟 [ ]

　　第三趟 [ ]

　　第四趟 [ ]

　　第五趟 [ ]

　　第六趟 [ ]

　　第七趟 [ ]

　　第八趟 [ ]

　　第九趟

　　()堆排序(通過畫二*樹可以一步步得出排序結果)

　　初始態 　　　[ ]

　　建立初始堆 [ ]

　　第一次排序重建堆 [ ]

　　第二次排序重建堆 [ ]

　　第三次排序重建堆 [ ]

　　第四次排序重建堆 [ ]

　　第五次排序重建堆 [ ]

　　第六次排序重建堆 [ ]

　　第七次排序重建堆 [ ]

　　第八次排序重建堆 [ ]

　　第九次排序重建堆

　　()歸並排序(為了表示方便采用自底向上的歸並方括號為有序區)

　　初始態[] [] [] [] [] [] [] [] [] []

　　第一趟 [ ] [ ] [ ] [ ] [ ]

　　第二趟 [ ] [ ] [ ]

　　第三趟 [ ] [ ]

　　第四趟 [ ]

　　()基數排序(方括號內表示一個箱子共有個箱子箱號從到)

　　初始態

　　第一趟[] [ ] [] [] [] [] [] [] [] []

　　第二趟 [] [] [] [ ] [] [] [ ] [] [] []

　　第三趟 [] [] [] [] [] [] [] [ ] [] []

　　在上面的排序方法中直接插入排序冒泡排序歸並排序和基數排序是穩定的其他排序算法均是不穩定的現舉實例如下以帶 *號的表示區別

　　希爾排序 [*]

　　快速排序[*]

　　直接選擇排序[*]

　　堆排序[*]

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