The Fourth Dimension Space

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

各种排序算法汇总——纪《数据结构》最后一课

/*<排序算法模板汇总>
这些模板适用于任意数据类型,包括结构体和类类型;
如果是结构体或者是类类型,请重载"<"符号;
PS:这里均按照从小到大的顺序来排序
Copyright:abilitytao,Nanjing University Of Science And Technology 
*/






/////////////////////////BEGIN_TEMPLATE_BY_ABILITYTAO_ACM//////////////////////////////////////
#include<iostream>
#include
<cstdio>
#include
<algorithm>
#include
<cmath>
using namespace std;

template
<class T>
void InsertSort(T a[],int n)//直接插入排序,时间复杂度为O(n^2)
{

    
int i,j;
    T temp;
    
for(i=1;i<n;i++)
    
{

        temp
=a[i];
        
for(j=i-1;j>=0;j--)
        
{

            
if(temp<a[j])
                a[j
+1]=a[j];
            
else
                
break;
        }

        a[j
+1]=temp;
        
    }

}




template
<class T>
void ShellSort(T a[],int n)//希尔排序,时间复杂度为O(n^1.5)

    
int i,j,d;
    T temp;
    d
=n>>1;
    
while(d>=1)
    
{
        
for(i=d;i<n;i++)
        

            temp
=a[i];
            
for(j=i-d;j>=0;j-=d)
            
{
                
if(a[j]>temp) 
                    a[j
+d]=a[j];
                
else 
                    
break;
            }

            a[j
+d]=temp;
        }
//这个while实际上是直接插入排序

        d
>>=1;//即d右移一位,d除以2;
    }

}
//ShellSort



template
<class T>
void BubbleSort(T a[],int n)//冒泡排序,时间复杂度为O(n^2)
{
    
int i,j;
    T temp;
    
for(i=n-1;i>0;i--)
    
{
        
for(j=0;j<i;j++)
        
{
            
if(a[j]>a[j+1])
            
{

                temp
=a[j];
                a[j]
=a[j+1];
                a[j
+1]=temp;
            }

        }

    }

}



/////////////////////快速排序,时间复杂度为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 QuickSort(T a[],int n)
{
    qsort(a,
0,n-1);
}


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



template 
<class T>
void SelectSort(T a[],int n)//选择排序,时间复杂度为O(n^2)
{
    
int i,j,k;
    T temp;
    
for(i=0;i<n-1;i++)
    
{   
        k
=i;
        
for(j=i+1;j<n;j++)
        
{
            
if(a[j]<a[k])
                k
=j;
        }

            temp
=a[k];
            a[k]
=a[i];
            a[i]
=temp;
    }

}


///////////////////////堆排序////////////////////////////
template <class T>
void Sift(T a[],int k,int m)//k筛选标号,m筛选范围
{
    
int i,j;
    T temp;
    i
=k;
    j
=2*i+1;//j指向左儿子;
    temp=a[i];//暂存a[i];
    while(j<=m)
    

        
if(j<&&a[j]<a[j+1])
                j
++;
        
if(temp<a[j])
        

            a[i]
=a[j];
            i
=j;
            (j
<<=1)++;//j*2+1
        }

        
else 
            
break;
    }

    a[i]
=temp; 
}
        


template 
<class T>
void HeapSort(T a[],int n)//堆排序,建堆时间复杂度O(n),筛选O(nlog2n);

{
    
int i;
    T temp;
    
for(i=(n>>1)-1;i>=0;i--)
        Sift(a,i,n
-1);

    
for(i=n-1;i>=1;i--)
    
{  
        temp
=a[0];
        a[
0]=a[i];
        a[i]
=temp;
        Sift(a,
0,i-1);
    }

}

/////////////////////HeapSort_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 MergeSort(T a[],int n)

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

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


/////////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM//////////////////////////////////////






int main ()
{
    
double test1[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
    InsertSort(test1,
sizeof(test1)/sizeof(double));
    
double test2[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
    ShellSort(test2,
sizeof(test2)/sizeof(double));
    
double test3[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
    BubbleSort(test3,
sizeof(test3)/sizeof(double));
    
double test4[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
    QuickSort(test4,
sizeof(test4)/sizeof(double));
    
double test5[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
    SelectSort(test5,
sizeof(test5)/sizeof(double));
    
double test6[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
    HeapSort(test6,
sizeof(test6)/sizeof(double));
    
double test7[]={10.4,9.1,8.4,7,6,5,4,3,2,1};
    MergeSort(test7,
sizeof(test7)/sizeof(double));
    
return 0;
}








写这些函数的过程中我遇到了一个奇怪的问题,就是merge这个函数前不能使用上模板类,如果将它改为:
template <class T>
void merge(T sr[],T tr[],int l,int m,int n)
编译器竟然会报错,不知道是怎么回事,希望各位大牛指点一下。

呵呵 问题已经解决,原来在C++标准库里面已经使用过merge这个关键字,只要将merge改为Merge便可通过编译了。


谨以此文,纪念数据结构最后一课。

posted on 2009-05-06 18:13 abilitytao 阅读(1806) 评论(4)  编辑 收藏 引用

评论

# re: 各种排序算法汇总——纪《数据结构》最后一课 2009-05-06 22:23 longe

学习下!!!  回复  更多评论   

# re: 各种排序算法汇总——纪《数据结构》最后一课 2009-05-06 22:29 longe


int x = a[i]
why?

a[i] 的类型不是T吗?
这样的话 好像 弄个模板 函数太浪费 了  回复  更多评论   

# re: 各种排序算法汇总——纪《数据结构》最后一课 2009-05-06 23:05 abilitytao

@longe
这是个BUG 呵呵 多谢提醒啊  回复  更多评论   

# re: 各种排序算法汇总——纪《数据结构》最后一课 2009-05-12 13:43 cookbook

done  回复  更多评论   


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