关于对教材第七章算法7.15的改进
关于第七章归并排序一节中的优化归并排序（算法7.15）
我对这个算法有几个问题？
1. 为什么不把DoSort( )函数的代码直接放到Sort( )函数里，而是在Sort( )函数外
定义DoSort( )函数？在类 Class ImprovedTwoWayMergeSorter：public……里也没定义成员函数DoSort( )啊。我觉得把函数DoSort( )放在函数Sort( )的外面定义对理解递归显得不太清晰。
2. 优化后的算法是不用像算法7.10(我认为此处应该是算法7.14)那样需要检查子序列是否结束. 但它增加了比较的次数. 算法7.14中当一个子序列的元素插入完后,另一个子序列中的元素直接插入到Array[]中,而不需要比较.
例如 原序列为: 12 37 49 41 30 71 58 19 65 15
先分为2个子序列
(12 37 49 41 30) (71 58 19 65 15)
对 这两个子序列分别再分解,然后分别归并,
归并后的序列为:
(12 30 37 41 49) (71 65 58 19 15)(颠倒过来后)
在插入元素49后Array[] 为:12 15 19 30 37 41 49, 此时index1移动到元素71下, index2在元素58下,然后还得分别比较 71>58 和 71>65 和71>=71 (比较三次)来插入元素58 65 71, 在算法7.14中,此时左边子序列已空了,右边子序列的三个元素无需比较直接插入Array[]中就行了
而且在数组大于16时才进行这种归并,当数据量很大时,这种额外的比较开销对算法的时间性能没有影响吗?
1. 为什么不把DoSort( )函数的代码直接放到Sort( )函数里
答：这个早就勘误了的。不知道出版社为什么翻来覆去总搞错。
2. 算法7.14与7.15的代价比较。
答：
比较算法7.14和7.15，首先，二者的赋值运算都是一样的，对于长度为n的待排序序列，merge一次则赋值2n次（一轮倒入临时数组为n次赋值，一轮每个值都从临时数组归并到位为n次赋值）
不同的是比较次数；
（1）在处理完一个子串之前
算法7.14每次合并操作都有三个比较运算：
while ((index1 <= middle)&&
(index2 <= right))
和if (Compare::le(TempArray[index1], TempArray[index2]))
而7.15在处理完一个子串之前，每次合并操作都只有一个比较运算if (Compare::le(TempArray[index1], TempArray[index2]))
这里的运算代价显然7.14高于7.15
（2）某一个子串处理完之后，
算法7.14对每次合并操作都有一个比较运算，“while (index1 <= middle)”或“while (index2 <= right)”（二者取一）
算法7.15对每次合并操作也有一个比较运算，if (Compare::le(TempArray[index1], TempArray[index2]))
这里的运算代价7.14与7.15相同
数排序算法中,P240的算法7.20有几处错误
1. 在Sort()函数中的第一个for循环中,i从0到i<n,
为什么先用for循环使Array[n-1]=i+1;
再在下面加语句 Array[n-1]=-1; 为什么不把for循环中的循环
条件改为i<n-1呢?
1. 在Sort()函数中的第一个for循环中
答：这里没有问题，不是错误！效果是等价的。赋初值的习惯不同而已，教材算法多赋一次初值。
2. 学习指导的对习题7.2的解答也有问题.在解法一中:图解中对直接插入排序算法的交换次数没错,但二分插入排序(算法7.7)没有交换啊,只有TempRecord = Array[];和Arrat[] = TempRecord;两次赋值操作,而且是在每次外循环时都各执行一次,当然最后的for循环里移动的次数每次可能不同.但在解答中确也分比较和交换来分析就不对了吧,我感到在二分插入法中没有交换,只有移动,直接插入是交换(swap), 一次交换为三次赋值(移动).应该分为比较和移动来分析较合理. 解法二是正确的,而且与解法一是矛盾的.
今年上网看到张老师对这些问题进行了回答，所以又重新编辑了此贴
[此贴子已经被作者于2006-11-5 18:56:00编辑过]
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 计算机考研交流 』 → 数据结构教材第七章内排序的错误与改进
(订阅本版)
2006/11/4 23:40:00
新浪微博
数据结构教材第七章内排序的错误与改进
