全国计算机等级考试C语言上机考试专业指导一

以关键字序列(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 1228] ]第二趟:265 301 751[129 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]
第八趟

(2) Hill排序(增量为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

(3)冒泡排序(方括号为无序区)
初始状态[265 301 751 129 937 863 742 694 076 438]
第一趟:076[265 301 751 129 937 863 742 694 438][/br/第二趟:076 129[265 301 751 438 937 863 748

(4)快速排序:(方括号表示无序区域， 表示对应于该层的递归树的数目)
初始状态:[265 301 751 129 937 863 742 694 076 438]
第二层:[076 129]265[751 937 863 742 694 301 438]
25[438 301 694 742]751[863 937][/br 第六层:076 129 265 301 438 694 742 751 863 937
(5)直接选择排序:(方括号为无序区域)
初始状态[265 301 751 129 937 863 742 692
第一次行程:076[301 751 129 937 863 742 694 265 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]
第七趟

(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[/br 四阶重建堆:[694 438 301 265 075 129]742 751 863 937
五阶重建堆:[438 263] 64 742 751 863 937
六阶重建堆:[301 265 075 129]438 694 742 751 863 937
七阶重建堆:[266

(7)合并排序(为方便起见，采用自底向上合并，带方括号的有序区域)
初始状态:[265][301][751][129][937][863][742][694][076][438]
第一次行程:[265 301第二次行程:[129 265 301 751][694 742 863 937][076 438]

(8)基数排序(方括号表示一个盒子有10个盒子，盒子数从0到9)
初始状态:265 301 751 129 937 863 742 694 076 438
第一趟:[][301 751][742][863][694][265][076][][129][937 438][742][751][863 263]以下是一些例子:不同之处用*号表示。
希尔排序:[8，1，10，5，6，*8]
快速排序:[2，*2，1]
直接选择排序:[2，*2，1]
堆排序:[2