分而治之算法---归并排序
文章类别:
C语言程序设计 | 发表日期:2008-9-24 14:46:27
可以运用分而治之方法来解决排序问题,该问题是将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 分而治之排序算法的伪代码
从对归并过程的简略描述中,可以明显地看出归并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。
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) 的时间。