资源描述：
《最新10内部排序.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、精品资料10内部排序........................................精品资料第10章内部排序10.1以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：(1)直接插入排序(2)希尔排序(d[1]=5,d[2]=3,d[3]=1)(3)快速排序(第一个记录为基准记录)(4)堆排序(5)归并排序(6)基数排序解答：（1）直接插入排序：第一趟：087,503,512,061,908,170
2、,897,275,653,426第二趟：087,503,512,061,908,170,897,275,653,426第三趟：061,087,503,512,908,170,897,275,653,426第四趟：........................................精品资料061,087,503,512,908,170,897,275,653,426第五趟：061,087,170,503,512,908,897,275,653,426第六趟：061,087,170,275,503,512,8
3、97,908,653,426第八趟：061,087,170,275,503,512,653,897,908,426第九趟：061,087,170,275,426,503,512,653,897,908（2）希尔排序(d[1]=5,d[2]=3,d[3]=1)第一趟：170,087,275,061,426,503,897,512,653,908第二趟：061,087,275,170,426,503,897,512,653,908第三趟：........................................精品
4、资料061,087,170,275,426,503,512,653,897,908(3)快速排序(第一个记录为基准记录)第一趟：(426,087,275,061,170)503(897,908,653,512)第二趟：(170,087,275,061)426,503(512,653)897(908)第三趟：(061,087)170(275)426,503,512(653)897,908第四趟：061,087,170,275,426,503,512,653,897,908(4)堆排序（小根堆为例）建堆：061,087,
5、170,275,426,512,897,503,653,908第一趟：（输出061）087,275,170,503,426,512,897,653第二趟：（输出087）170,275,512,503,426,653,897,908第三趟：（输出170）275,406,512,503,908,653,897........................................精品资料第四趟：（输出275）406,503,512,897,908,653第五趟：（输出406）503,653,512,897,908
6、第六趟：（输出503）512,653,908,897第七趟：（输出512）653,897,908第八趟：（输出653）897,908第九趟：（输出897）908(5)归并排序第一趟：(087,503)(061,512)(170,908)(275,897)(426,653)第二趟：(061,087,503,512)(170,275,897,908)(426,653)第三趟：(061,087,170,275,503,512,897,908)(426,653)第四趟：061,087,170,275,426,503,512,
7、653,897,908(6)简单选择排序第一趟：........................................精品资料061,087,512,503,908,170,897,275,653,426第二趟：061,087,512,503,908,170,897,275,653,426第三趟：061,087,170,503,908,512,897,275,653,426第四趟061,087,170,275,908,512,897,503,653,426第五趟061,087,170,275,426,512
8、,897,503,653,908第六趟061,087,170,275,426,503,897,512,653,908第七趟061,087,170,275,426,503,512,653,897,90810.7不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。
（1）n=7时在最好情况下需进行多少次比较？
