青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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<&& 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)////////////////////////



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<&&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<=&& 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 閱讀(1882) 評論(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
請問您有什么改進的建議嗎 當時寫這個只是為了完成數據結構的作業呢 呵呵  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美精品日韩www.p站| 亚洲精品一区二区三区在线观看 | 久久久福利视频| 欧美一区二区三区免费大片| 国内精品久久久久久久97牛牛| 久久噜噜噜精品国产亚洲综合 | 亚洲欧美视频在线观看| 国产一区二区三区在线观看免费视频 | 一区免费观看| 亚洲黑丝一区二区| 国产精品激情| 久久天天躁夜夜躁狠狠躁2022| 亚洲私拍自拍| 免费观看一区| 欧美日韩精品二区第二页| 亚洲天堂av在线免费| 久久爱www.| 在线天堂一区av电影| 性欧美超级视频| 99re热这里只有精品视频| 亚洲欧美国产高清| 最新亚洲视频| 欧美伊人影院| 一本久道久久综合中文字幕| 欧美一区二区三区免费观看视频| 亚洲国产精品精华液网站| 野花国产精品入口| 亚洲电影免费在线| 亚洲欧美日韩久久精品| 9i看片成人免费高清| 欧美一区二区在线视频| 亚洲卡通欧美制服中文| 欧美在线观看一区二区| 亚洲综合欧美日韩| 欧美顶级艳妇交换群宴| 久久综合成人精品亚洲另类欧美 | 亚洲永久免费视频| 99国产精品自拍| 久久亚洲精品欧美| 久久gogo国模啪啪人体图| 欧美日韩视频一区二区| 欧美激情一区二区三区四区| 国产亚洲综合性久久久影院| 一区二区三区精品国产| 亚洲精品久久久久久下一站| 久久精品首页| 久久国产直播| 国产伦精品一区二区| 中文av一区二区| 99视频精品| 欧美日韩精品伦理作品在线免费观看| 免费观看成人网| 国产尤物精品| 欧美中文字幕视频在线观看| 午夜精品久久久久久99热| 欧美日韩午夜在线| 99国内精品| 亚洲新中文字幕| 欧美午夜一区二区| 在线视频欧美日韩| 亚洲天堂偷拍| 国产精品美女999| 中国亚洲黄色| 性刺激综合网| 国产一区久久久| 久久久久久久综合| 欧美成年人视频网站| 亚洲国内自拍| 欧美日韩大片一区二区三区| 亚洲品质自拍| 亚洲视频成人| 国产精品video| 性做久久久久久免费观看欧美| 欧美中文日韩| 亚洲国产精品va在线看黑人 | 亚洲综合999| 久久久久9999亚洲精品| 国产伦理精品不卡| 久久精品欧美日韩精品| 母乳一区在线观看| 亚洲成色999久久网站| 免费成人在线观看视频| 激情久久久久久久久久久久久久久久| 久久久不卡网国产精品一区| 男人的天堂亚洲在线| 亚洲人成网站在线观看播放| 欧美日韩亚洲国产精品| 亚洲欧美日韩综合一区| 能在线观看的日韩av| 一本色道久久加勒比88综合| 国产欧美精品在线观看| 久热精品视频在线观看| 亚洲午夜高清视频| 麻豆国产精品777777在线| av成人黄色| 国内精品视频一区| 欧美日产国产成人免费图片| 亚洲欧美韩国| 91久久线看在观草草青青| 性欧美1819性猛交| 一区二区三区偷拍| 久久久伊人欧美| 伊人婷婷久久| 久久精品三级| 亚洲美女电影在线| 毛片一区二区三区| 小处雏高清一区二区三区| 亚洲国产高清在线观看视频| 国产精品视频免费一区| 免费在线观看精品| 亚洲欧美日韩综合aⅴ视频| 亚洲国内自拍| 欧美不卡视频一区| 久久麻豆一区二区| 亚洲欧美日韩在线高清直播| 亚洲精品乱码| 亚洲高清网站| 国产永久精品大片wwwapp| 国产精品国产三级国产专播精品人 | 欧美日韩在线另类| 亚洲精品日韩综合观看成人91| 久久久久国产精品午夜一区| 99ri日韩精品视频| 在线成人av.com| 国产欧美日韩在线视频| 欧美日韩成人在线观看| 欧美成人免费全部观看天天性色| 久久精品国产第一区二区三区最新章节 | 亚洲一区二区三区四区五区午夜| 亚洲日本中文字幕免费在线不卡| 黄色亚洲免费| 国产一区二区三区久久久| 国产欧美日韩91| 国产精品一区=区| 国产噜噜噜噜噜久久久久久久久 | 玖玖在线精品| 国产曰批免费观看久久久| 欧美日韩精品免费观看视频完整 | 久久久精品国产一区二区三区| 亚洲砖区区免费| 亚洲欧美激情一区二区| 午夜精品三级视频福利| 亚洲伊人网站| 亚洲欧美视频一区| 性欧美大战久久久久久久免费观看 | 亚洲欧美卡通另类91av| 亚洲欧美激情诱惑| 久久av资源网站| 久久视频这里只有精品| 免费观看国产成人| 亚洲第一福利视频| 亚洲人成高清| 中文精品视频| 欧美一级理论片| 久久婷婷国产综合精品青草| 免费黄网站欧美| 欧美欧美天天天天操| 国产精品高潮在线| 国产日韩精品久久久| 一区在线视频| 一区二区三区回区在观看免费视频 | 欧美高清视频一二三区| 欧美日韩免费在线观看| 国产精品自拍三区| 永久免费视频成人| 99国产精品一区| 久久av一区二区三区漫画| 欧美高清在线一区| 亚洲天堂av在线免费| 久久精品在线播放| 欧美日韩国产综合久久| 国产欧美一区二区在线观看| 尤物九九久久国产精品的分类| 亚洲精品中文在线| 欧美一级大片在线观看| 亚洲大胆美女视频| 亚洲午夜极品| 欧美第十八页| 国内精品久久久久久久果冻传媒| 亚洲精品国久久99热| 欧美综合激情网| 亚洲看片一区| 久久影院午夜论| 国产麻豆9l精品三级站| 日韩视频免费观看| 久久人人爽人人爽爽久久| 亚洲毛片在线看| 蜜桃伊人久久| 国产一区二区你懂的| 国产精品99久久久久久久女警| 老司机凹凸av亚洲导航| 亚洲综合日韩中文字幕v在线| 母乳一区在线观看| 精品69视频一区二区三区| 亚洲欧美一区二区三区久久 | 午夜亚洲视频| 欧美午夜在线一二页| 亚洲六月丁香色婷婷综合久久| 久久久久久亚洲精品中文字幕| 亚洲一本大道在线|