加文

在这个世界上取得成就的人,都努力去寻找他们想要的机会,如果找不到机会,他们便自己创造机会。 -- 萧伯纳
随笔 - 14, 文章 - 56, 评论 - 1, 引用 - 0
数据加载中……

二路归并迭代算法

#include <iostream>
using namespace std;
//有序表归并算法
void merge( int r[],int s,int m,int t)
{
    
int tempr[50];
    
for(int k = s; k <= t; k++ )
        tempr[k] 
= r[k];
    
int s1 = s;
    
int s2 = m+1;
    
int rs = s;
    
while(s1 <= m && s2 <= t)
        
if(tempr[s1]<=tempr[s2])
            r[rs
++= tempr[s1++];
        
else
            r[rs
++= tempr[s2++];
    
while(s1 <= m)
        r[rs
++= tempr[s1++];
    
while(s2 <= t)
        r[rs
++= tempr[s2++];
}  
// 一趟归并排序算法
void MergePass(int r[],int len,int n)
{
    
int i;
    
for(i=0;i+2*len-1<=n;i=i+2*len)
        merge(r,i,i
+len-1,i+2*len-1);
    
if(i+len-1<n)
        merge(r,i,i
+len-1,n);
}
 
// 归并迭代算法
 
// 函数名:MergeSort;
 
// 参数:r[]表示想要排序的数组;tempr[]表示临时数组;n表示数组元素个数
 void MergeSort(int r[],int n)
 {
     
int len;
     len 
= 1;
     
while(len<n)
     {
         MergePass(r,len,n);
         len 
= 2*len;
         MergePass(r,len,n);
 
     }
 }
int main()
{
    
int r[14= {10,2,12,3,4,89,5,45,21,7,90,112,78,91};
    MergeSort(r,
13);
    
for(int i=0;i<14;i++)
        cout
<<r[i]<<endl;     

    getchar();
    
return 0;
}

posted on 2011-10-25 00:43 chxzwj 阅读(199) 评论(0)  编辑 收藏 引用 所属分类: 常用算法


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