副标题#e#
可以运用分而治之要领来办理排序问题，该问题是将n个元素排成非递减顺序。分而治之要领凡是用以下的步调来举办排序算法：若n 为1，算法终止；不然，将这一元素荟萃支解成两个或更多个子荟萃，对每一个子荟萃别离排序，然后将排好序的子荟萃合并为一个荟萃。
假设仅将n个元素的荟萃分成两个子荟萃。此刻需要确定如何举办子荟萃的分别。一种大概性就是把前面n- 1个元素放到第一个子会合（称为A），最后一个元素放到第二个子集里（称为B）。凭据这种方法对A递归地举办排序。由于B仅含一个元素，所以它已经排序完毕，在A排完序后，只需要用措施2 – 1 0中的函数i n s e r t将A和B归并起来。把这种排序算法与I n s e r t i o n S o r t（见措施2 – 1 5）举办较量，可以发明这种排序算法实际上就是插入排序的递归算法。该算法的巨大性为O (n 2 )。把n个元素分别成两个子荟萃的另一种要领是将含有最大值的元素放入B，剩下的放入A中。然后A被递归排序。为了归并排序后的A和B，只需要将B添加到A中即可。如果用函数M a x（见措施1 – 3 1）来找出最大元素，这种排序算法实际上就是S e l e c t i o n S o r t（见措施2 – 7）的递归算法。
如果用冒泡进程（见措施2 – 8）来寻找最大元素并把它移到最右边的位置，这种排序算法就是B u b b l e S o r t（见措施2 – 9）的递归算法。这两种递归排序算法的巨大性均为(n2 )。若一旦发明A已经被排好序就终止对A举办递归支解，则算法的巨大性为O(n2 )（见例2 – 1 6和2 – 1 7）。
上述支解方案将n个元素分成两个极不服衡的荟萃A和B。A有n- 1个元素，而B仅含一个元素。下面来看一看回收均衡支解法会产生什么环境： A荟萃中含有n/k个元素，B中包括其余的元素。递归地利用分而治之要领对A和B举办排序。然后回收一个被称之为合并（ m e rg e）的进程，将已排好序的A和B归并成一个荟萃。
例2-5 思量8个元素，值别离为[ 1 0，4，6，3，8，2，5，7 ]。假如选定k = 2，则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被别离独立地排序。功效别离为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始合并这两个已排序的序列。元素2比3更小，被移到功效序列；3与5举办较量，3被移入功效序列；4与5较量，4被放入功效序列；5和6较量，.。假如选择k= 4，则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序功效别离为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6 , 7 , 8 ]。当这两个排好序的序列被合并后，即可得所需要的排序序列。
图2 – 6给出了分而治之排序算法的伪代码。算法中子荟萃的数目为2，A中含有n/k个元素。
template
void sort( T E, int n)
{ / /对E中的n个元素举办排序，k为全局变量
if (n >= k) {
i = n/k;
j = n-i;
令A 包括E中的前i个元素
令B 包括E中余下的j个元素
s o r t ( A , i ) ;
s o r t ( B , j ) ;
m e rge(A,B,E,i,j,); //把A 和B 归并到E
}
else 利用插入排序算法对E 举办排序
}
图14-6 分而治之排序算法的伪代码
#p#副标题#e#
从对合并进程的大略描写中，可以明明地看出合并n个元素所需要的时间为O (n)。设t (n)为分而治之排序算法（如图1 4 – 6所示）在最坏环境下所需耗费的时间，则有以下递推公式：
个中c 和d 为常数。当n / k≈n-n / k 时，t (n)的值最小。因此当k= 2时，也就是说，当两个子荟萃所包括的元素个数近似相等时，t (n) 最小，即当所分另外子荟萃巨细靠近时，分而治之算法凡是具有最佳机能。
可以用迭代要领来计较这一递推方法，功效为t(n)= (nl o gn)。固然这个功效是在n为2的幂时获得的，但对付所有的n，这一功效也是有效的，因为t(n) 是n的非递减函数。t(n) =(nl o gn) 给出了合并排序的最好和最坏环境下的巨大性。由于最好和最坏环境下的巨大性是一样的，因此合并排序的平均巨大性为t (n)= (nl o gn)。
图2 – 6中k= 2的排序要领被称为合并排序（ m e rge sort ），或更准确地说是二路合并排序（two-way merge sort）。下面按照图1 4 – 6中k= 2的环境（合并排序）来编写对n个元素举办排序的C + +函数。一种最简朴的要领就是将元素存储在链表中（即作为类c h a i n的成员（措施3 -8））。在这种环境下，通过移到第n/ 2个节点并打断此链，可将E分成两个大抵相等的链表。
合并进程应能将两个已排序的链表合并在一起。假如但愿把所获得C + +措施与堆排序和插入排序举办机能较量，那么就不能利用链表来实现合并排序，因为后两种排序要领中都没有利用链表。为了能与前面接头过的排序函数作较量，合并排序函数必需用一个数组a来存储元素荟萃E，并在a 中返回排序后的元素序列。为此凭据下述进程来对图1 4 – 6的伪代码举办细化：当荟萃E被化分成两个子集适时，可以不必把两个子荟萃的元素别离复制到A和B中，只需简朴地在荟萃E中保持两个子荟萃的阁下界线即可。接下来对a 中的初始序罗列办排序，并将所获得的排序序列合并到一个新数组b中，最后将它们复制到a 中。图1 4 – 6的改造版见图1 4 – 7。
#p#分页标题#e#
template
M e rgeSort( T a[], int left, int right)
{ / /对a [ l e f t : r i g h t ]中的元素举办排序
if (left < right) {//至少两个元素
int i = (left + right)/2; //中心位置
M e rgeSort(a, left, i);
M e rgeSort(a, i+1, right);
M e rge(a, b, left, i, right); //从a 归并到b
Copy(b, a, left, right); //功效放回a
}
}
图14-7 分而治之排序算法的改造
可以从许多方面来改造图1 4 – 7的机能，譬喻，可以容易地消除递归。假如仔细地查抄图1 4 – 7中的措施，就会发明个中的递归只是简朴地反复支解元素序列，直到序列的长度酿成1为止。当序列的长度变为1时即可举办合并操纵，这个进程可以用n 为2的幂来很好地描写。长度为1的序列被合并为长度为2的有序序列；长度为2的序列接着被合并为长度为4的有序序列；这个进程不绝地反复直到合并为长度为n的序列。图1 4 – 8给出n= 8时的合并（和复制）进程，方括号暗示一个已排序序列的首和尾。
初始序列[8] [4] [5] [6] [2] [1] [7] [3]
合并到b [4 8] [5 6] [1 2] [3 7]
复制到a [4 8] [5 6] [1 2] [3 7]
合并到b [4 5 6 8] [1 2 3 7]
复制到a [4 5 6 8] [1 2 3 7]
合并到b [1 2 3 4 5 6 7 8]
复制到a [1 2 3 4 5 6 7 8]
图14-8合并排序的例子
另一种二路合并排序算法是这样的：首先将每两个相邻的巨细为1的子序列合并，然后对上一次合并所获得的巨细为2的子序罗列办相邻合并，如此重复，直至最后合并到一个序列，合并进程完成。通过轮番地将元素从a合并到b并从b合并到a，可以虚拟地消除复制进程。二路合并排序算法见措施1 4 – 3。
措施14-3 二路合并排序
template
void MergeSort(T a[], int n)
{// 利用合并排序算法对a[0:n-1] 举办排序
T *b = new T [n];
int s = 1; // 段的巨细
while (s < n) {
MergePass(a, b, s, n); // 从a合并到b
s += s;
MergePass(b, a, s, n); // 从b合并到a
s += s;
}
}
为了完成排序代码，首先需要完成函数M e rg e P a s s。函数M e rg e P a s s（见措施1 4 – 4）仅用来确定欲合并子序列的左端和右端，实际的合并事情由函数M e rg e (见措施1 4 – 5 )来完成。函数M e rg e要求针对范例T界说一个操纵符< =。假如需要排序的数据范例是用户自界说范例，则必需重载操纵符< =。这种设计要领答允我们按元素的任一个域举办排序。重载操纵符< =的目标是用来较量需要排序的域。
措施14-4 MergePass函数
template
void MergePass(T x[], T y[], int s, int n)
{//合并巨细为s的相邻段
int i = 0;
while (i <= n - 2 * s) {
//合并两个巨细为s的相邻段
Merge(x, y, i, i+s-1, i+2*s-1);
i = i + 2 * s;
}
// 剩下不敷2个元素
if (i + s < n) Merge(x, y, i, i+s-1, n-1);
else for (int j = i; j <= n-1; j++)
// 把最后一段复制到y
y[j] = x[j];
}
措施14-5 Merge函数
template
void Merge(T c[], T d[], int l, int m, int r)
{// 把c[l:m]] 和c[m:r]合并到d [ l : r ] .
int i = l, // 第一段的游标
j = m+1, // 第二段的游标
k = l; // 功效的游标
/ /只要在段中存在i和j，则不绝举办合并
while ((i <= m) && (j <= r))
if (c[i] <= c[j]) d[k++] = c[i++];
else d[k++] = c[j++];
// 思量余下的部门
if (i > m) for (int q = j; q <= r; q++)
d[k++] = c[q];
else for (int q = i; q <= m; q++)
d[k++] = c[q];
}
自然合并排序（natural merge sort）是根基合并排序（见措施1 4 – 3）的一种变革。它首先对输入序列中已经存在的有序子序罗列办合并。譬喻，元素序列[ 4，8，3，7，1，5，6，2 ]中包括有序的子序列[ 4，8 ]，[ 3，7 ]，[ 1，5，6 ]和[ 2 ]，这些子序列是按从左至右的顺序对元素表举办扫描而发生的，若位置i的元素比位置i+ 1的元素大，则从位置i 举办支解。对付上面这个元素序列，可找到四个子序列，子序列1和子序列2合并可得[ 3 , 4 , 7 , 8 ]，子序列3和子序列4合并可得[ 1 , 2 , 5 , 6 ]，最后，合并这两个子序列获得[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。因此，对付上述元素序列，仅仅利用了两趟合并，而措施1 4 – 3从巨细为1的子序列开始，需利用三趟合并。作为一个极度的例子，假设输入的元素序列已经排好序并有n个元素，自然合并排序法将精确地识别该序列不必举办合并排序，但措施1 4 – 3仍需要举办[ l o g2 n]趟合并。因此自然合并排序将在(n)的时间内完成排序。而措施1 4 – 3将耗费(n l o gn)的时间。
