然而,仔细观察可以发现,归并排序有两个地方值得商榷:一是分解直到只有 个元素。事实上,当元素比较少时,直接进行排序,比如用插入排序算法,比起 进一步分拆、合并排序要快得多。因为,在这种情况下,大量的时间都花在调用 分解、合并函数上。所以,在归并排序算法中,对于归并起点的规模应该有适当 的限制,即加 Small(p,q)判断。二是辅助数组B的借用,虽然不可避免,但应 该采用另一种方式,以避免数组A中的元素的频繁换位。为此,我们可以采用链 表,将数组A中的元素位置变动转化成链表值的变化。 程序4-2-6使用链接表的归并排序算法 MergeSort(1oW,high,p)//Link是全程数组A[low:high]的 //下标表,p指示这个表的开始处。利用Link将A按非 /降顺序排列。 global ALlow: high]: Link [low: high]: if high-low+1<l6then//设定子问题的最小规模 Small InsertSort(A, Link, low, high, p) else mid=(low+high)/2] MergeSort(1oW,mid,q);//返回q表 MergeSort(mid+1,high,r);//返回r表 MergeL(q,r,p);将表q和r合并成表p endif end Merge SortL 其中,合并程序 Mergel是合并函数 Merge的改进 程序4-2-7使用连接表的合并程序 MergeL(q,r,p)//由链接表q和r构造新的连接表p。q、r是全程数组 Link[1:n]中两个表指针,这两个链表指出被划分的两个子组的地址排 \\序,而p指针指出两组归并后的地址排序。实际上都是表的相互顺序 \在变 global n, ALl: n], Link [O: n]: local integer i, j, k i=q;j=r;k=0;//初始化,新表在Link[0]处开始 while i≠0&&j≠0do//当两个表皆非空时然而，仔细观察可以发现，归并排序有两个地方值得商榷：一是分解直到只有一 个元素。事实上，当元素比较少时，直接进行排序，比如用插入排序算法，比起 进一步分拆、合并排序要快得多。因为，在这种情况下，大量的时间都花在调用 分解、合并函数上。所以，在归并排序算法中，对于归并起点的规模应该有适当 的限制，即加 Small(p,q)判断。二是辅助数组 B 的借用，虽然不可避免，但应 该采用另一种方式，以避免数组 A 中的元素的频繁换位。为此，我们可以采用链 表，将数组 A 中的元素位置变动转化成链表值的变化。 程序 4-2-6 使用链接表的归并排序算法 MergeSortL(low, high, p) // Link 是全程数组 A[low:high]的 //下标表, p 指示这个表的开始处。利用 Link 将 A 按非 //降顺序排列。 global A[low:high]; Link[low:high]; if high-low+1<16 then //设定子问题的最小规模 Small InsertSort(A,Link, low,high,p)； else mid=(low+high)/2； MergeSortL(low,mid,q); //返回 q 表 MergeSortL(mid+1,high,r); //返回 r 表 MergeL(q,r,p); 将表q和r 合并成表 p endif end MergeSortL 其中，合并程序 MergeL 是合并函数 Merge 的改进： 程序 4-2-7 使用连接表的合并程序 MergeL(q,r,p) // 由链接表q和r 构造新的连接表 p。q、r 是全程数组 \\Link[1:n]中两个表指针，这两个链表指出被划分的两个子组的地址排 \\序， 而 p 指针指出两组归并后的地址排序。实际上都是表的相互顺序 \\在变。. global n,A[1：n], Link[0:n]; local integer i, j, k; i=q; j=r; k=0; // 初始化，新表在 Link[0]处开始 while i≠0 && j≠0 do //当两个表皆非空时