模板类的练习——排序小结

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

搜集了几个常用的排序算法:如直接插入排序,折半插入排序,希尔排序,起泡排序,快速排序,选择排序,堆排序,主要参照《数据结构(C语言版)》

#define MAXSIZE 100

template<class T>

class CSortArithmethic

{

public:

static struct _tagSqList

{

T r[MAXSIZE];

int length;

};

private:

typedef _tagSqList SqList;

public:

// 直接插入排序

static void InsertSort(SqList& l);

// 折半插入排序

static void BInsertSort(SqList& l);

//希尔排序

static void ShellSort(SqList& l,int dlta[],int n);

// 起泡排序

static void BubbleSort(SqList& l);

// 快速排序

static void QuickSort(SqList& l);

// 选择排序

static void SelectSort(SqList& l);

// 堆排序

static void HeadSort(SqList& l); //采用顺序表存储表示

static void swapT(T& t1,T& t2);

private:

static void shellInsert(SqList& l,int dk);

static void qSort(SqList& l,int low,int high);

};

template<class T>

void CSortArithmethic<T>::InsertSort(SqList& l)

{

T tTemp;

int j=0;

for(int i=1;i<l.length;i++)

{

if(l.r[i] <l.r[i-1])

{

tTemp = l.r[i];

for(j= i-1;j>=0&&tTemp <= l.r[j]; --j)

{

l.r[j+1] = l.r[j];

}

l.r[j+1] = tTemp;

}

}

}

template<class T>

void CSortArithmethic<T>::BInsertSort(SqList& l)

{

T tTemp;

int low,high;

int mid;

int j=0;

for(int i=1;i<=l.length;i++)

{

tTemp = l.r[i];

low = 0;high = i - 1;

while(low<high)

{

mid = (low + high) / 2;

if(tTemp <= l.r[mid]) high = mid -1;

else low = mid +1;

}

for( j = i-1;j>=high+1; --j)

l.r[j+1] = l.r[j];

l.r[high+1] = tTemp;

}

}

template<class T>

void CSortArithmethic<T>::shellInsert(SqList& l,int dk)

{

int i=0;

int j=0;

T temp;

for(i = dk;i<l.length;++i)

{

if(l.r[i] < l.r[i - dk])

{

temp = l.r[i];

for(j = i-dk; j>0&&(temp<l.r[j]);j-=dk)

{

l.r[j+dk] = l.r[j];

}

l.r[j+ dk] = temp;

}

}

}

template<class T>

void CSortArithmethic<T>::ShellSort(SqList& l,int dlta[],int n)

{

for(int i=0;i<n;i++)

shellInsert(l,dlta[i]);

}

template<class T>

void CSortArithmethic<T>::BubbleSort(SqList& l)

{

for(int i= l.length;i>=0;i--)

{

for(int j=0;j<i-1;j++)

{

if(l.r[j+1] < l.r[j])

swapT(l.r[j],l.r[j+1]);

}

}

}

template<class T>

void CSortArithmethic<T>::swapT(T& t1,T& t2)

{

T temp = t2;

t2 =t1;

t1 =temp;

}

template<class T>

void CSortArithmethic<T>::qSort(SqList& l,int low,int high)

{

int i,j;

int middle;

i = low;

j = high;

T temp = l.r[(low+high)/2];

do{

while((l.r[i]<temp) && (i<high))

i++;

while((l.r[j]>temp) && (j>low))

j--;

if(i<=j)

{

swapT(l.r[i],l.r[j]);

i++;

j--;

}

}while(i<=j);

if(low<j)

qSort(l,low,j);

if(high>i)

qSort(l,i,high);

}

template<class T>

void CSortArithmethic<T>::QuickSort(SqList& l)

{

qSort(l,0,l.length-1);

}

template<class T>

void CSortArithmethic<T>::SelectSort(SqList& l)

{

int smallIndex;

int i,j;

for(i=0;i<l.length;i++)

{

smallIndex = i;

for(j=i+1;j<l.length;j++)

{

if(l.r[smallIndex] > l.r[j])

smallIndex =j;

}

swapT(l.r[i],l.r[smallIndex]);

}

}

template<class T>

void CSortArithmethic<T>::HeadSort(SqList& l)

{

for(int i=(l.length-1) /2 ; i>=0; i--)

{

T rc = l.r[i];

for(int j=2 * i;j<= l.length-1; j *= 2)

{

if(j< l.length && (l.r[j] < l.r[j+1])) j++;

if( rc >= l.r[j]) break;

l.r[i] = l.r[j];

i = j;

}

l.r[i] = rc;

}

for( i = l.length-1; i>0;i--)

{

swapT(l.r[0],l.r[i]);

T r = l.r[i];

for(int j=2 * i;j<= l.length-1; j *= 2)

{

if(j< l.length && (l.r[j] < l.r[j+1])) j++;

if( r >= l.r[j]) break;

l.r[i] = l.r[j];

i = j;

}

l.r[i] = r;

}

}

/*

************************************************

综合比较各种内部排序方法,大致结果如下

排序方法 平均时间 最坏情况 辅助存储

简单排序 O(n*n) O(n*n) O(1)

快速排序 O(nlogn) O(n*n) O(logn)

堆排序 O(nlogn) O(nlogn) O(1)

************************************************

*/

/*

*************************************************************************************************

TEST

*************************************************************************************************

*/

int _tmain(int argc, _TCHAR* argv[])

{

cout<<"\nSortArithmetic--------------------------------"<<endl;

CSortArithmethic<int>::_tagSqList list;

for(int i=0;i<MAXSIZE;i++)

{

list.r[i] = i *rand()% MAXSIZE;

}

list.length = 100;

cout<<" befor sort"<<endl;

for(i=0;i<list.length;i++)

cout<<list.r[i]<<endl;

cout<<" after sort"<<endl;

CSortArithmethic<int>::QuickSort(list);

for(i=0;i<list.length;i++)

cout<<list.r[i]<<endl;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航