学历改变命运
24小时客服:4008135555/010-82335555
当前位置:首页 > 笔记串讲 > 计算机应用专业上机考试排序算法指导

计算机应用专业上机考试排序算法指导

2006年06月20日    来源:北京自考热线 怪狗   字体:   打印

  以关键字序列(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

  (5)直接选择排序:(方括号为无序区)

  初始态  [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)堆排序:(通过画二*树可以一步步得出排序结果)

  初始态    [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)归并排序(为了表示方便,采用自底向上的归并,方括号为有序区)

  初始态:[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)基数排序(方括号内表示一个箱子共有10个箱子,箱号从0到9)

  初始态: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]

  在上面的排序方法中,直接插入排序、冒泡排序、归并排序和基数排序是稳定的,其他排序算法均是不稳定的,现举实例如下:以带*号的表示区别。

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

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

  直接选择排序:[2,*2,1]

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

关闭