以关键字序列 ()为例分别写出执行以下排序算法的各趟排序结束时关键字序列的状态
() 直接插入排序 ()希尔排序 ()冒泡排序 ()快速排序
() 直接选择排序 () 堆排序 () 归并排序 ()基数排序
上述方法中哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例
答
()直接插入排序:(方括号表示无序区)
初始态 : [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟 [ ]
第七趟 [ ]
第八趟 []
第九趟
()希尔排序(增量为)
初始态 :
第一趟
第二趟
第三趟
()冒泡排序(方括号为无序区)
初始态 [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟
()快速排序(方括号表示无序区层表示对应的递归树的层数)
初始态 [ ]
第二层 [ ] [ ]
第三层 [] [ ] [ ]
第四层 [] [ ] []
第五层 []
第六层
()直接选择排序(方括号为无序区)
初始态 [ ]
第一趟 [ ]
第二趟 [ ]
第三趟 [ ]
第四趟 [ ]
第五趟 [ ]
第六趟 [ ]
第七趟 [ ]
第八趟 [ ]
第九趟
()堆排序(通过画二*树可以一步步得出排序结果)
初始态 [ ]
建立初始堆 [ ]
第一次排序重建堆 [ ]
第二次排序重建堆 [ ]
第三次排序重建堆 [ ]
第四次排序重建堆 [ ]
第五次排序重建堆 [ ]
第六次排序重建堆 [ ]
第七次排序重建堆 [ ]
第八次排序重建堆 [ ]
第九次排序重建堆
()归并排序(为了表示方便采用自底向上的归并方括号为有序区)
初始态[] [] [] [] [] [] [] [] [] []
第一趟 [ ] [ ] [ ] [ ] [ ]
第二趟 [ ] [ ] [ ]
第三趟 [ ] [ ]
第四趟 [ ]
()基数排序(方括号内表示一个箱子共有个箱子箱号从到)
初始态
第一趟[] [ ] [] [] [] [] [] [] [] []
第二趟 [] [] [] [ ] [] [] [ ] [] [] []
第三趟 [] [] [] [] [] [] [] [ ] [] []
在上面的排序方法中直接插入排序冒泡排序归并排序和基数排序是稳定的其他排序算法均是不稳定的现举实例如下以带 *号的表示区别
希尔排序 [*]
快速排序[*]
直接选择排序[*]
堆排序[*]
