WEB开发网
开发学院软件开发数据结构 c语言算法 - 分而治之算法 - 归并排序 阅读

c语言算法 - 分而治之算法 - 归并排序

 2010-01-28 11:58:33 来源:WEB开发网   
核心提示:可以运用分而治之方法来解决排序问题,该问题是将n个元素排成非递减顺序,c语言算法 - 分而治之算法 - 归并排序,分而治之方法通常用以下的步骤来进行排序算法:若n 为1,算法终止;否则,算法中子集合的数目为2,A中含有n/k个元素,将这一元素集合分割成两个或更多个子集合,对每一个子集合分别排序

可以运用分而治之方法来解决排序问题,该问题是将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 分而治之排序算法的伪代码

1 2 3  下一页

Tags:语言 算法 分而治之

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接