The Fourth Dimension Space

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

SortWizard(排序精灵）——我的排序类

//排序精灵
//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>
class SortWizard
{
private:
    T *a;
    int n;
public:
    SortWizard(){    a=NULL;n=0;}
    SortWizard(T *a,int n){this->a=a;this->n=n;}
    void Set(T *a,int n){this->a=a;this->n=n;}
    void InsertSort();
    void ShellSort();
    void BubbleSort();
    void QuickSort();
    void SelectSort();
    void MergeSort();
    void HeapSort();
};

template<class T>
void SortWizard<T>:: InsertSort()//直接插入排序,时间复杂度为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 SortWizard<T>::ShellSort()//希尔排序,时间复杂度为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 SortWizard<T>::BubbleSort()//冒泡排序,时间复杂度为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<j && temp<=a[j])  
                j--;
        if(i<j)
        { 
            a[i]=a[j]; 
            i++; 
        }
        while(i<j && 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)////////////////////////



template <class T>
void SortWizard<T>::SelectSort()//选择排序，时间复杂度为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<m &&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 SortWizard<T>::HeapSort()//堆排序，建堆时间复杂度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<=m && 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)///////////////////////////////


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





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







如果您认为还可以改进的话 请留言告诉我:-)

posted on 2009-05-07 18:54 abilitytao 阅读(1851) 评论(14)  编辑 收藏 引用

评论

# re: SortWizard(排序精灵）——我的排序类 2009-05-07 20:55 adon

我想递减怎么办  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-07 21:55 zhaoyg

博主可否做成成员函数是模板函数的非模板类，这样可以用一个对象来处理所有类型的排序  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-07 22:41 abilitytao

@adon
不知道您有什么高见呢 我现在的方法是 重载运算符 不过这个对基本数据类型不管用  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-07 22:47 abilitytao

@zhaoyg
您的意思是不是让我拿掉私有成员变量？把它作为类里面函数的参数？  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-08 12:45 zhaoyg

@abilitytao
恩,是这样的.
不知你意下如何  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-08 12:47 zhaoyg

不过感觉像我这样一弄，好像也就没必要造这个类了，直接用库函数就是了。  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类[未登录] 2009-05-08 12:58 Charlie

@abilitytao
可以使用policy based做比较

template<typename element_t>
struct less_than {
static bool compare(const element_t lhs, const element_t rhs) {
return lhs<rhs;
}
};

template<typename element_t, typename cmp_policy = less_than<element_t> >
struct sort_wirzad {
void easy_sort() {
...
//做比较
if ( cmp_policy::compare(e1,e2) ) { /* do sth */ }
}
};

用户可以自定义自己的 compare_policy
比如定义一个 greater_than 可以这样传递给sort_wizard:

sort_wizard<int,greater_than> instance;  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-08 15:36 abilitytao

@Charlie
这个就是常用的cmp函数吧 呵呵 我还不是很理解呢   回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-08 20:07 Chuck

@abilitytao
这招很常用……特别是对使用模版的程序
假想我做了一个高精度整数类，这个整数在C++里面用字符串来表示字面值，我做一个累加的程序，当然是泛型的~
这些东西存在一个std::vector里面
template<typename element_t>
struct accum {
  static element_t accumlate(const std::vector<element_t>& container) {
    std::vector<element_t>::const_iterator i = container.begin();
    std::vector<element_t>::const_iterator end = container.end();
   
    element_t total = 0; /***注意这一行***/
    while ( i != end ) {
      total += *i;
      ++i;
    }
  }
};
前面的total = 0 对于普通数值类型不会出错，但是如果是对于我的big_int类
要把big_int初始化为0，应该是：
big_int = "0";
那么这个accum就不管用了
该怎么办呢？ 利用一个东西来完成……
template<typename element_t>
struct init_zero {
  static element_t zero() {
    return 0;
  }
};

// 一个偏特化
template<>
struct init_zero<big_int> {
  static big_int zero() {
    return big_int("0");
  }
};
那么之前的代码就可以写成这样：
template<typename element_t, typename init_zeror = init_zero<element_t> >
struct accum {
  static element_t accumlate(const std::vector<element_t>& container) {
    std::vector<element_t>::const_iterator i = container.begin();
    std::vector<element_t>::const_iterator end = container.end();
   
    element_t total = init_zeror::zero();
    while ( i != end ) {
      total += *i;
      ++i;
    }
  }
};
  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-08 20:08 Chuck

by the way
我是之前那个charlie
  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-08 20:10 Chuck

哦~ 我忘记return total了~ 不好意思~ 不伤大雅就OK~  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-05-08 21:41 abilitytao

@Chuck
多谢呵 讲解的很详细:-)
PS:话说BIG_INT我也有一个 不过要是有高精浮点类就好了 呵呵  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类 2009-11-20 12:11 tiny

qsort
实现的太过简单。。。。。。没啥实际价值。  回复  更多评论   

# re: SortWizard(排序精灵）——我的排序类[未登录] 2009-11-21 19:42 abilitytao

@tiny
请问您有什么改进的建议吗 当时写这个只是为了完成数据结构的作业呢 呵呵  回复  更多评论   


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