在待排序序列已有序的情况下就是如此 25.(1)直接插入排序 第一趟(3)[8,3],2,5,9,1,6第二趟(2)[8,3,2],5,9,1,6 (5)[8,5,3,2],9,1,6 第四趟(9)[9,8,5,3,2],1,6第五趟(1)[9,8,5,3,2,1],6 (6)[9,8,6,5,3,2,1] (2)直接选择排序(第六趟后仅剩一个元素,是最小的,直接选择排序结束) 第一趟(9)[9],3,2,5,8,1,6第二趟(8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2 第四趟(5)[9,8,6,5],3,1,2第五趟(3)[9,8,6,5,3],1,2 第六趟 (2)[9,8,6,5,3,2],1 (3)直接插入排序是稳定排序,直接选择排序是不稳定排序。 26.这种看法不对。本题的叙述与稳定性的定义无关,不能据此来判断排序中的稳定性。例 如5,4,1,2,3在第一趟冒泡排序后得到4,1,2,3,5。其中4向前移动,与其最终位置相反 但冒泡排序是稳定排序。快速排序中无这种现象 125,,22,34,15,4,76,66,100,8,14,20,2,5,1 设D=7 15;2,5,66;100,22,34,20,4,76,1 1,11,2,5,15,8,14,34,20,22,66,100,44,76,125 1,2,5,8,11,14,15,20,22,34,44,6,76,100,125 28.设待排序记录的个数为n,则快速排序的最小递归深度为 Logan h+1,最大递归深度n 29.平均性能最佳的排序方法是快速排序,该排序方法不稳定 初始序列:50,10,50,40,45,85,80 趟排序:[45,10,50,40]50[85,80]二趟排序:[40,10]45[50]50[80] 三趟排序:10,40,45,50,50,80,85 30.快速排序 31.(1)在最好情况下,假设每次划分能得到两个长度相等的子文件,文件的长度n=2-1, 那么第一遍划分得到两个长度均为n/2的子文件,第二遍划分得到4个长度均为Ln/4的 子文件,以此类推,总共进行k=1og2(n+1)遍划分,各子文件的长度均为1,排序完毕。当 n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件(长度均为3, k=2)进行排序,各需2次,共10次即可。 (2)在最好情况下快速排序的原始序列实例:4,1,3,2,6,5,7 (3)在最坏情况下,若每次用来划分的记录的关键字具有最大值(或最小值),那么只能 得到左(或右)子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排 列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为 0(n2)。所以当n=7时,最坏情况下的比较次数为21次 (4)在最坏情况下快速排序的初始序列实例:7,6,5,4,3,2,1,要求按递增排序。 32.该排序方法为快速排序在待排序序列已有序的情况下就是如此。 25. (1)直接插入排序 第一趟 (3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 第三趟 (5)[8,5,3,2],9,1,6 第四趟 (9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6 第六趟 (6)[9,8,6,5,3,2,1] (2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束） 第一趟 (9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2 第四趟 (5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2 第六趟 (2)[9,8,6,5,3,2],1 (3)直接插入排序是稳定排序，直接选择排序是不稳定排序。 26.这种看法不对。本题的叙述与稳定性的定义无关，不能据此来判断排序中的稳定性。例 如 5,4,1,2,3 在第一趟冒泡排序后得到 4,1,2,3,5。其中 4 向前移动，与其最终位置相反。 但冒泡排序是稳定排序。快速排序中无这种现象。 27. 125，11，22，34，15，44，76，66，100，8，14，20，2，5，1 设 D=7 1，11，8，14，15，2，5，66，100，22，34，20，44，76，125 D=3 1，11，2，5，15，8，14，34，20，22，66，100，44，76，125 D=1 1，2，5，8，11，14，15，20，22，34，44，66，76，100，125 28. 设待排序记录的个数为 n，则快速排序的最小递归深度为 log2n+1，最大递归深度 n。 29. 平均性能最佳的排序方法是快速排序，该排序方法不稳定。 初始序列: 50，10，50，40，45，85，80 一趟排序: [45，10，50，40] 50 [85，80] 二趟排序: [40，10] 45 [50] 50 [80] 85 三趟排序: 10，40，45，50，50，80，85 30. 快速排序。 31. (1) 在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度 n=2k -1， 那么第一遍划分得到两个长度均为 n/2 的子文件，第二遍划分得到 4 个长度均为 n/4 的 子文件，以此类推，总共进行 k=log2(n+1)遍划分，各子文件的长度均为 1，排序完毕。当 n=7 时，k=3，在最好情况下，第一遍需比较 6 次，第二遍分别对两个子文件（长度均为 3， k=2）进行排序，各需 2 次，共 10 次即可。 (2) 在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。 (3) 在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能 得到左(或右)子文件，其长度比原长度少 1。因此，若原文件中的记录按关键字递减次序排 列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为 O(n2 )。所以当 n=7 时，最坏情况下的比较次数为 21 次。 (4) 在最坏情况下快速排序的初始序列实例： 7,6,5,4,3,2,1，要求按递增排序。 32.该排序方法为快速排序