那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

原地归并算法

归并排序算法(mergesort)是将一个序列划分为同样大小的两个子序列,然后对两个子序列分别进行排序,最后进行合并操作,将两个子序列合成有序的序列.在合成的过程中,一般的实现都需要开辟一块与原序列大小相同的空间,以进行合并操作,归并排序算法的示例在这里.

这里介绍一种不需要开辟新的空间就可以进行归并操作的算法.算法的核心部分是以下代码:
 1 /**
 2 * 算法: 合并二已排序的连续序列
 3 **/
 4 template<typename T>
 5 void t_merge( T& v, size_t size, size_t pos )
 6 {
 7     size_t fir = 0, sec = pos;
 8     while ( fir < sec && sec < size )
 9     {
10         while ( fir < sec && v[fir] <= v[sec] ) fir++;
11         size_t maxMove = 0;
12         while ( sec < size && v[fir] > v[sec] ) maxMove++, sec++;
13         t_exchange( &v[fir], sec - fir, sec - fir - maxMove );
14         fir += maxMove;       
15     }
16 }

其中T是一个数组, size是数组尺寸, pos是归并划分的位置.也就是说[0,pos)和[pos, size)都分别是有序的.比如对序列1, 3, 5, 7, 2, 4, 6, 8进行归并操作, 此时size=8, pos = 4.

以<<算法导论>>中介绍的通过循环不变量的方法证明算法的正确性,在这个算法中, 循环不变量为[fir, sec)中的元素都是有序的:

1) 初始:此时fir = 0, sec = pos, 以前面介绍的函数参数的说明来看,满足循环不变量.

2) 迭代:来看看循环做了些什么操作.行10进行的操作为, 只要满足fir元素不大于sec元素, fir就一直递增;行12进行的操作是只要满足fir大于sec, sec就一直递增, 同时递增maxMove计数.因此, 进行完前面两个步骤之后, fir所指元素一定小于sec以及其后的所有元素.而位于sec之前的第二个子序列中的元素, 一定小于fir.因此, [sec-maxMove, sec)z中的元素小于所有[fir, sec - 1)的元素.通过调用t_exchange函数将位于[sec-maxMove, sec)中的元素"旋转"到fir之前.

也就是说, 这个过程在第二个已经排序好的子序列中寻找在它之内的小于目前第一个已经排序好的子序列的序列, 将它"旋转"到前面.

以序列 1, 3, 5, 7, 2, 4, 6, 8为例, 此时fir=1也就是指向3, sec=5也就是指向4, maxMove=1, 通过调用t_exchange函数之后将[sec-maxMove, sec)即[4,5)中的元素也就是2"旋转"到子序列3,5,7之前,于是该循环结束之后序列变为1,2,3,5,7,4,6,8, 此时fir=2, sec =5, 满足循环不变量.

3) 终止: 当循环终止时, fir或者sec之一超过了数组的尺寸, 显而易见, 此时序列变成了有序的.

完整的算法如下所示, 需要特别说明的是, 这段代码不是我想出来的, 原作者在这里:
#include <stdio.h>
#include 
<iostream>

using namespace std;

//int array[] = {1, 3, 5, 7, 2, 4, 6, 8};
int array[] = {3,5,7,8,1,2,4,6};
void display(int array[], int n)
{
     
for (int i = 0; i < n; ++i)
     {
         printf(
"%d ", array[i]);
     }
     printf(
"\n");
}

/**
* 算法: 交换二对象
*
*/
template
<typename T>
void t_swap( T& v1, T& v2 )
{
    T t 
= v1; v1 = v2; v2 = t;
}

/**
* 算法: 反转序列
*
*/
template
<typename T>
void t_reverse( T* v, size_t size )
{
    size_t s 
= 0, e = size-1;
    
while( s < e && s < size && e > 0 )
        t_swap( v[s
++], v[e--] );
}

/**
* 算法: 手摇算法,从指定位置旋转序列(见编程珠玑第二章)
*
*/
template
<typename T>
void t_exchange( T* v, size_t size, size_t n )
{
    t_reverse( v, n );
    t_reverse( v 
+ n, size - n );
    t_reverse( v, size );
}

/**
* 算法: 合并二已排序的连续序列
*
*/
template
<typename T>
void t_merge( T& v, size_t size, size_t pos )
{
    size_t fir 
= 0, sec = pos;
    
while ( fir < sec && sec < size )
    {
        
while ( fir < sec && v[fir] <= v[sec] ) fir++;
        size_t maxMove 
= 0;
        
while ( sec < size && v[fir] > v[sec] ) maxMove++, sec++;
        t_exchange( 
&v[fir], sec - fir, sec - fir - maxMove );
        fir 
+= maxMove;

        display(array, 
sizeof(array)/sizeof(int));
    }
}

/**
* 算法: 归并排序
*
*/
template
<typename T>
void t_merge_sort( T* v, size_t size )
{
    
if ( size <= 1 ) return;
    t_merge_sort( v, size
/2 );
    t_merge_sort( v 
+ size/2, size - size/2 );
    t_merge( v, size, size
/2 );
}

int main()
{
     display(array, 
sizeof(array)/sizeof(int));

     t_merge(array, 
sizeof(array) / sizeof(int), (sizeof(array)/sizeof(int))/2);
     
//t_merge_sort(array, sizeof(array) / sizeof(int));

     display(array, 
sizeof(array)/sizeof(int));
     
return 0;
}


补充说明:
其实前面采用"旋转"算法将元素前移不是必须的, 可以将所要移动的元素之前的部分后移, 再将元素插入到合适的位置.比如前面说的对于序列1, 3, 5, 7, 2, 4, 6, 8, 第一步要将元素2前移至3之前, 可以将3,5,7后移, 然后将2插入到合适的位置.
但是这样有一个问题, 如果要移动的元素多了, 那么就需要更多的临时空间保存要前移的元素, 这样对空间就不是O(1)的了.而旋转算法可以做到O(1)的空间达到要求.


posted on 2008-09-28 19:51 那谁 阅读(5492) 评论(7)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 原地归并算法  回复  更多评论   

呵呵 你对算法好有研究哇
2008-09-28 20:54 | 沈臻豪(foxtail)

# re: 原地归并算法  回复  更多评论   

“通过调用t_exchange函数将位于[sec-maxMove+fir, sec)中的元素"旋转"到fir之前.”——区间左端多了一个+fir

真是非常棒的对归并的改进!在较好的情况下,合并操作的时间开销会降低;而在最坏情况下,合并操作的开销从操作数量上来说是传统归并的三倍(swap相当于执行三次赋值),但是考虑传统归并中内存分配的时间,实践中估计是差不了太多。然而最关键在于这是个原地算法。
希望看到博主更多的算法研究文章。
2008-09-29 10:52 | E剑仙

# re: 原地归并算法  回复  更多评论   

@E剑仙
感谢指出错误,已经修改!
2008-09-29 15:48 |

# re: 原地归并算法  回复  更多评论   

重新看了下这个算法,发现补充说明那也不对,用插入+整体偏移的方法实现也是能只需要O(1)的空间,不会比旋转算法差
2008-11-13 22:05 | E剑仙

# re: 原地归并算法  回复  更多评论   

插入+整体偏移 对于数组来说是O(N2)的,旋转是O(N)的。。
当然空间是一样的
2010-07-08 19:00 | laowan

# re: 原地归并算法  回复  更多评论   

swap相当于执行三次赋值 其总的赋值平均时间代价为6n方 其代价反而高于最简单的挪动的原地归并(最简单的挪动的赋值平均时间代价为0.5n方)
2012-05-07 21:42 | Glawind

# re: 原地归并算法  回复  更多评论   

原地归并算法存在时间复杂度为O(n)空间复杂度为O(1)的实现
我就做了个
2013-08-08 08:24 | scof

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理