Problem Solving using C++

Algorithm Study using C++

排序算法总结(3)--归并排序

归并排序(Merge Sort),是非常好的一种排序方式。时间复杂度为O(nlogn)。空间复杂度为O(n)
同快速排序相比,其有稳定性以及最差情况下为O(nlogn)等特点。

归并排序是典型的分而治之方法,首先将排序任务分成自任务,即Divide过程,然后将各个子任务初步完成(Conquer),最后将所有的子任务合并(merge)就完成了整个任务。
整个算法框架如下:
void mergesort(int A[],int p,int r)
{
      if(p<r)
    {
           int q=(p+r)/2;
          mergesort(A,p,q);
          mergesort(A,q+1,r);
          merge(A,p,q,r);
    }
}
在merge中,首先将p->q的(q-p+1)个放到一个左边的数组L中,将q+1->r的(r-q)个放到右边的数组R中,然后将数组L和数组R的数按顺序放置到A中。
void merge(A,p,q,r)
{
       //construct the L and R array
         int left=q+1-p;
         int right = r-q;

         int* L=new int[left];
        int* R = new int[right];

//fill the L and R array
         int i,j,k;
    for(i=0;i<left;i++)
        L[i]=A[p+i];
    for(j=0;j<right;j++)
        R[j]=A[q+j+1];
       
//copy the value from L and R to A
//Notice there are three cases
    for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
    {
        if(L[i]<=R[j])
            {
                A[p+k]=L[i];
                i++;
            }
        else
        {
            A[p+k]=R[j];
            j++;
        }
    }
   
    if(i<left)
    {
        for(;i<left;i++,k++)
            A[p+k]=L[i];
    }
    if(j<right)
    {
        for(;j<right;j++,k++)
            A[p+k]=R[j];
    }
   
//delete the L and R
    delete [] L;
    delete [] R;
      
}
整个mergesort的可执行代码如下:
#include <iostream>
#include 
<algorithm>
#include 
<iterator>
#include 
<cstdlib>
#include 
<time.h>
#include 
<windows.h>

#define MAXSIZE    
100
int arr[MAXSIZE];

using namespace std;

void print(bool flag=true)
{
    
if(flag)
    {
        copy(arr,arr
+MAXSIZE,ostream_iterator<int>(cout," "));
        cout
<<endl;
    }
}

void merge(int A[],int p,int q,int r)
{
    
int left = q-p+1;
    
int right = r-q;
    
    
int* L=new int[left];
    
int* R = new int[right];
    
    
int i,j,k;
    
for(i=0;i<left;i++)
        L[i]
=A[p+i];
    
for(j=0;j<right;j++)
        R[j]
=A[q+j+1];
        
    
for(k=0,i=0,j=0;(i<left)&&(j<right);k++)
    {
        
if(L[i]<=R[j])
            {
                A[p
+k]=L[i];
                i
++;
            }
        
else
        {
            A[p
+k]=R[j];
            j
++;
        }
    }
    
    
if(i<left)
    {
        
for(;i<left;i++,k++)
            A[p
+k]=L[i];
    }
    
if(j<right)
    {
        
for(;j<right;j++,k++)
            A[p
+k]=R[j];
    }
    
    delete [] L;
    delete [] R;
}

void mergesort(int A[],int p, int r)
{
    
if(p<r)
    {
        
int q = (p+r)/2;
        mergesort(A,p,q);
        mergesort(A,q
+1,r);
        merge(A,p,q,r);
    }
}

int main(int argc,char* argv[])
{
    
int size = MAXSIZE;
    
    
for(int i=0;i<size;i++)
    {
        arr[i] 
= rand()%MAXSIZE;
    }
    
    print();

    DWORD start 
= timeGetTime();
    
    mergesort(arr,
0,MAXSIZE-1);
    
    DWORD end 
= timeGetTime();
    
    print();
    
    cout
<<end-start<<endl;
    
    system(
"pause");

    
return 0;
}


posted on 2007-08-22 16:13 Kingoal Lee's Alogrithm Study using cplusplus 阅读(247) 评论(0)  编辑 收藏 引用


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


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜