排序算法的各趟排序算法
以關鍵字序列(265,301,751,129,937,863,742,694,076,438)爲例,分別寫出執行以下排序算法的各趟排序結束時,關鍵字序列的狀態。
(1) 直接插入排序 (2)希爾排序 (3)冒泡排序 (4)快速排序
(5) 直接選擇排序 (6) 堆排序 (7) 歸竝排序 (8)基數排序
上述方法中,哪些是穩定的排序?哪些是非穩定的排序?對不穩定的排序試擧出一個不穩定的實例。
答: (1)直接插入排序:(方括號表示無序區)
初始態: 265[301 751 129 937 863 742 694 076 438]
第一趟:265 301[751 129 937 863 742 694 076 438]
第二趟:265 301 751[129 937 863 742 694 076 438]
第三趟:129 265 301 751[937 863 742 694 076 438]
第四趟:129 265 301 751 937[863 742 694 076 438]
第五趟:129 265 301 751 863 937[742 694 076 438]
第六趟:129 265 301 742 751 863 937[694 076 438]
第七趟:129 265 301 694 742 751 863 937[076 438]
第八趟:076 129 265 301 694 742 751 863 937[438]
第九趟:076 129 265 301 438 694 742 751 863 937
(2)希爾排序(增量爲5,3,1)
初始態: 265 301 751 129 937 863 742 694 076 438
第一趟:265 301 694 076 438 863 742 751 129 937
第二趟:076 301 129 265 438 694 742 751 863 937
第三趟:076 129 265 301 438 694 742 751 863 937
(3)冒泡排序(方括號爲無序區)
初始態 [265 301 751 129 937 863 742 694 076 438]
第一趟: 076 [265 301 751 129 937 863 742 694 438]
第二趟: 076 129 [265 301 751 438 937 863 742 694]
第三趟: 076 129 265 [301 438 694 751 937 863 742]
第四趟: 076 129 265 301 [438 694 742 751 937 863]
第五趟: 076 129 265 301 438 [694 742 751 863 937]
第六趟: 076 129 265 301 438 694 742 751 863 937
(4)快速排序:(方括號表示無序區,層表示對應的遞歸樹的層數)
初始態: [265 301 751 129 937 863 742 694 076 438]
第二層: [076 129] 265 [751 937 863 742 694 301 438]
第三層: 076 [129] 265 [438 301 694 742] 751 [863 937]
第四層: 076 129 265 [301] 438 [694 742] 751 863 [937]
第五層: 076 129 265 301 438 694 [742] 751 863 937
第六層: 076 129 265 301 438 694 742 751 863 937
0條評論