The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

快速排序,归并排序,两种基于分治策略的排序算法.

/////////////////////快速排序,时间复杂度为O(nlog2n)///////////////////////
template<class T>
int Partion(T a[],int i,int j)//划分函数
{  
    T temp;
    temp
=a[i];
    
while(i<j)
    
{  
        
while(i<&& temp<=a[j])  
                j
--;
        
if(i<j)
        

            a[i]
=a[j]; 
            i
++
        }

        
while(i<&& a[i]<=temp) 
            i
++;
        
if(i<j)
        

            a[j]
=a[i]; 
            j
--
        }

    }

    a[i]
=temp;
    
return i;
}



template 
<class T>
void qsort(T a[],int l,int h)
{
    
int m;
    
if(l<h) 
    

        m
=Partion(a,l,h);
        qsort(a,l,m
-1);
        qsort(a,m
+1,h); 
    }

}


template
<class T>
void SortWizard<T>::QuickSort()
{
    qsort(a,
0,n-1);
}


////////////////////QuickSort_O(nlog2n)////////////////////////


///////////////////////归并排序,时间复杂度O(nlog2n)/////////////////////////////

template 
<class T>
void Merge(T sr[],T tr[],int l,int m,int n)
{
    
int i,j,k;
    i
=l;
    j
=m+1;
    k
=l-1;
    
while(i<=&& j<=n)
    
{
        
if(sr[i]<sr[j]) 
            tr[
++k]=sr[i++];
        
else 
            tr[
++k]=sr[j++];
    }

        
while(i<=m)
            tr[
++k]=sr[i++];
        
while(j<=n)
            tr[
++k]=sr[j++];
        
for(i=l;i<=n;i++
            sr[i]
=tr[i];
}


template 
<class T>
void Msort(T a[],T st[],int s,int t)
{
    
int m;
    
if(s<t) 
    

        m
=(s+t)>>1;
        Msort(a,st,s,m);
        Msort(a,st,m
+1,t);
        Merge(a,st,s,m,t);
    }

}


template 
<class T>
void SortWizard<T>::MergeSort()

    T 
*st=new T[n];
    Msort(a,st,
0,n-1);  
    delete  [ ]st;
}

/**///////////////////////MergeSort_O(nlog2n)///////////////////////////////

posted on 2010-05-18 20:13 abilitytao 阅读(249) 评论(0)  编辑 收藏 引用


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