The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

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 閱讀(1888) 評論(14) 編輯收藏引用

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

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

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

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

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

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

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

# re: SortWizard(排序精靈）——我的排序類[未登錄] 2009-05-08 12:58 Charlie

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

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

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

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

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

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

# re: SortWizard(排序精靈）——我的排序類[未登錄] 2009-11-21 19:42 abilitytao

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

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

SortWizard(排序精靈）——我的排序類

評論