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

posted on 2009-07-14 16:17 abilitytao 閱讀(146) 評論(0) 編輯收藏引用

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




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

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

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

排序精靈(SortWizard)