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