計(jì)算機(jī)應(yīng)用專業(yè)上機(jī)考試排序算法指導(dǎo)

  • 發(fā)布時(shí)間:2024-09-15 16:21:23
  • 來(lái)源:本站整理
  • 閱讀:
導(dǎo)讀:
  以關(guān)鍵字序列(265,301,751,129,937,863,742,694,076,438)為例,分別寫出執(zhí)行以下排序算法的各趟排序結(jié)束時(shí),關(guān)鍵字序列的狀態(tài)。
  (1) 直接插入排序 (2)希爾排序 (3)冒泡排序 (4)快速排序
 ?。?) 直接選擇排序 (6) 堆排序 (7) 歸并排序 (8)基數(shù)排序
  上述方法中,哪些是穩(wěn)定的排序?

以關(guān)鍵字序列(265,301,751,129,937,863,742,694,076,438)為例,分別寫出執(zhí)行以下排序算法的各趟排序結(jié)束時(shí),關(guān)鍵字序列的狀態(tài)。

(1) 直接插入排序 (2)希爾排序 (3)冒泡排序 (4)快速排序

(5) 直接選擇排序 (6) 堆排序 (7) 歸并排序 (8)基數(shù)排序

上述方法中,哪些是穩(wěn)定的排序?哪些是非穩(wěn)定的排序?對(duì)不穩(wěn)定的排序試舉出一個(gè)不穩(wěn)定的實(shí)例。

答:

(1)直接插入排序:(方括號(hào)表示無(wú)序區(qū))

初始態(tài): 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)

初始態(tài): 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)冒泡排序(方括號(hào)為無(wú)序區(qū))

初始態(tài) [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)快速排序:(方括號(hào)表示無(wú)序區(qū),層表示對(duì)應(yīng)的遞歸樹的層數(shù))

初始態(tài): [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

(5)直接選擇排序:(方括號(hào)為無(wú)序區(qū))

初始態(tài) [265 301 751 129 937 863 742 694 076 438]

第一趟: 076 [301 751 129 937 863 742 694 265 438]

第二趟: 076 129 [751 301 937 863 742 694 265 438]

第三趟: 076 129 265[ 301 937 863 742 694 751 438]

第四趟: 076 129 265 301 [937 863 742 694 751 438]

第五趟: 076 129 265 301 438 [863 742 694 751 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 [937 863]

第九趟: 076 129 265 301 438 694 742 751 863 937

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

初始態(tài) [265 301 751 129 937 863 742 694 076 438]

建立初始堆: [937 694 863 265 438 751 742 129 075 301]

第一次排序重建堆:[863 694 751 765 438 301 742 129 075] 937

第二次排序重建堆:[751 694 742 265 438 301 075 129] 863 937

第三次排序重建堆:[742 694 301 265 438 129 075] 751 863 937

第四次排序重建堆:[694 438 301 265 075 129] 742 751 863 937

第五次排序重建堆:[438 265 301 129 075] 694 742 751 863 937

第六次排序重建堆:[301 265 075 129] 438 694 742 751 863 937

第七次排序重建堆:[265 129 075] 301 438 694 742 751 863 937

第八次排序重建堆:[129 075]265 301 438 694 742 751 863 937

第九次排序重建堆:075 129 265 301 438 694 742 751 863 937

(7)歸并排序(為了表示方便,采用自底向上的歸并,方括號(hào)為有序區(qū))

初始態(tài):[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]

第一趟:[265 301] [129 751] [863 937] [694 742] [076 438]

第二趟:[129 265 301 751] [694 742 863 937] [076 438]

第三趟:[129 265 301 694 742 751 863 937] [076 438]

第四趟:[076 129 265 301 438 694 742 751 863 937]

(8)基數(shù)排序(方括號(hào)內(nèi)表示一個(gè)箱子共有10個(gè)箱子,箱號(hào)從0到9)

初始態(tài):265 301 751 129 937 863 742 694 076 438

第一趟:[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129]

第二趟:[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694]

第三趟:[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937]

在上面的排序方法中,直接插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定的,其他排序算法均是不穩(wěn)定的,現(xiàn)舉實(shí)例如下:以帶*號(hào)的表示區(qū)別。

希爾排序:[8,1,10,5,6,*8]

快速排序:[2,*2,1]

直接選擇排序:[2,*2,1]

堆排序:[2,*2,1]

相關(guān)閱讀

熱門標(biāo)簽

關(guān)于計(jì)算機(jī)應(yīng)用專業(yè)上機(jī)考試排序算法指導(dǎo)文章

2021年自學(xué)考試報(bào)考入口 2021年自學(xué)考試報(bào)考入口

熱門文章