我所理解的归并排序算法

 

作者:goal00001111(高粱)

           始发于goal00001111的专栏;允许自由转载,但必须注明作者和出处

 

      引子:这篇文章以前写过,最近复习排序算法,觉得以前的代码还可以改进,因此有了此文。

      归并排序算法以ONlogN)最坏情形运行时间运行,而所使用的比较次数几乎是最优的。

该算法中最基本的操作是合并两个已排序的表,这只需要线性的时间,但同时需要分配一个临时数组来暂存数据。

归并排序算法可以用递归的形式实现,形式简洁易懂。如果N=1,则只有一个元素需要排序,我们可以什么都不做;否则,递归地将前半部分数据和后半部分数据各自归并排序,然后合并这两个部分。

归并排序算法也可以用非递归的形式实现,稍微难理解一点。它刚好是递归分治算法的逆向思维形式,在使用递归分治算法时,程序员只需考虑将一个大问题分成若干个形式相同的小问题,和解的边界条件,具体如何解决这些小问题是由计算机自动完成的;而非递归形式要求程序员从最基本的情况出发,即从解决小问题出发,一步步扩展到大问题。

我这里两种形式都给出。

另外,很多人在写递归形式的归并排序算法时,临时数组是在MergeSort函数中分配的,这使得在任一时刻都可能有logN个临时数组处在活动期,如果数据较多,则开销很大,实用性很差

我把临时数组设置在Merge函数中,避免了这个问题。

///////////////////////////////////////////////////////////////////////

递归形式:

template <class T>

void MSort(T a[], int left, int right)

{

      if (left < right)

      {

            int center = (left + right) / 2;

            MSort(a, left, center);

            MSort(a, center+1, right);

            Merge(a, left, center+1, right+1);

      }

}

 

template <class T>

void MergeSort(T a[], int n)

{

      MSort(a, 0, n-1);

}

///////////////////////////////////////////////////////////////////////

非递归形式:

算法介绍:先介绍三个变量beforeLenafterLeni的作用:

int beforeLen; //合并前序列的长度

int afterLen;//合并后序列的长度,合并后序列的长度是合并前的两倍

int i = 0;//开始合并时第一个序列的起始位置下标,每次都是从0开始

ii+beforeLeni+afterLen定义被合并的两个序列的边界。

算法的工作过程如下:

开始时,beforeLen被置为1i被置为0。外部for循环的循环体每执行一次,都使beforeLenafterLen加倍。内部的while循环执行序列的合并工作,它的循环体每执行一次,i都向前移动afterLen个位置。当n不是afterLen的倍数时,如果被合并序列的起始位置i,加上合并后序列的长度afterLen,超过输入数组的边界n,就结束内部循环;此时如果被合并序列的起始位置i,加上合并前序列的长度beforeLen,小于输入数组的边界n,还需要执行一次合并工作,把最后长度不足afterLen,但超过beforeLen的序列合并起来。这个工作由语句Merge(a, i, i+beforeLen, n);完成。

 

template <class T>

void MergeSort(T a[], int n)

{

      int beforeLen; //合并前序列的长度

      int afterLen = 1;//合并后序列的长度

     

      for (beforeLen=1; afterLen<n; beforeLen=afterLen)

      {

            afterLen = beforeLen << 1; //合并后序列的长度是合并前的两倍

           

            int i = 0;//开始合并时第一个序列的起始位置下标,每次都是从0开始

            for ( ; i+afterLen<n; i+=afterLen)

                  Merge(a, i, i+beforeLen, i+afterLen);

           

            if (i+beforeLen < n)

                  Merge(a, i, i+beforeLen, n);

      }

}

///////////////////////////////////////////////////////////

      上面两种算法都要用到下面的合并函数。

/*函数介绍:合并两个有序的子数组

输入:数组a[],下标leftcenter,元素个数lena[left]~a[center-1]a[center]~a[len-1]已经按非递减顺序排序。

输出:按非递减顺序排序的子数组a[left]~a[len-1]

*/

template <class T>

void Merge(T a[], int left, int center, int len)

{

      T *t = new T[len-left];//存放被合并后的元素

      int i = left;

      int j = center;

      int k = 0;

 

      while (i<center && j<len)

      {

            if (a[i] <= a[j])

                  t[k++] = a[i++];

            else

                  t[k++] = a[j++];

      }

     

      while (i < center)

            t[k++] = a[i++];

           

      while (j < len)

            t[k++] = a[j++];

           

      //t[]的元素复制回a[]

      for (i=left,k=0; i<len; i++,k++)

            a[i] = t[k];

 

      delete []t;

}  

 

Posted on 2009-06-09 08:25 梦想飞扬 阅读(7623) 评论(4)  编辑 收藏 引用

Feedback

# re: 我所理解的归并排序算法(新)  回复  更多评论   

2009-06-09 11:54 by Wang Feng
void Merge(T a[], int left, int center, int len)

{

T *t = new T[len-left];//存放被合并后的元素
----------------------------------------------------------------
C++支持这样的语法
T t[len-left];

我猜想效率会比
T *t = new T[len-left];

更高

# re: 我所理解的归并排序算法(新)  回复  更多评论   

2009-06-09 22:01 by wzc
T t[len-left];
这是在栈空间定义的。如果是递归的话本来就会占用栈空间,T t[len-left]更会加剧占内存的减少,数据大的话,我猜会华丽的堆栈溢出

# re: 我所理解的归并排序算法(新)[未登录]  回复  更多评论   

2009-08-05 16:57 by 1
写的很棒哦

# re: 我所理解的归并排序算法(新)  回复  更多评论   

2009-10-20 11:06 by notme
诸多版本皆同;不知那个是源;

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理