发一些常见的排序算法的c++代码(每个排序以成员函数形式集成到了每个类中)
这里的排序代码基本把所有常见排序代码都涉及了，半个月的心血，全部通过测试，正确运行。
#ifndef DATASORTLIST_H
#define DATASORTLIST_H
#include<iostream.h>
#include<stdlib.h>
const int DefaultSize=100;
////////////////////////////////////////////////////
//数据表元素Element<T,E>类模板的实现
//T是数据元素的关键码类型,E是元素的数据域的类型
////////////////////////////////////////////////////
template<class T,class E>
class Element
{
public:
T key; //数据元素的关键码
E data; //数据元素的数据域
Element() //默认构造函数
{key=0;data=0;};
Element(T k,E d) //构造函数
{key=k;data=d;};
T getkey() //获取关键码
{return key;};
T getdata() //获取关键码
{return data;};
//成员重载赋值运算符
Element<T,E>& operator=(Element<T,E>& R)
{key=R.key;data=R.data;return *this;}
//成员重载下列的关系运算符
bool operator==(Element<T,E>& R)
{return key==R.key;};
bool operator<=(Element<T,E>& R)
{return key<=R.key;};
bool operator>=(Element<T,E>& R)
{return key>=R.key;};
bool operator<(Element<T,E>& R)
{return key<R.key;};
bool operator>(Element<T,E>& R)
{return key>R.key;};
bool operator!=(Element<T,E>& R)
{return key!=R.key;};
//友元重载<<输出运算符
friend ostream& operator<<(ostream& os,Element<T,E>& R);
};
///////////////////////////////////Element类定义结束
////////////////////////////////////////////////////
//友元重载<<输出运算符
////////////////////////////////////////////////////
template<class T,class E>
ostream& operator<<(ostream& os,Element<T,E>& R)
{
os<<R.key<<":"<<R.data;
return os;
};
//////////////////////////////////////<<友元重载结束
////////////////////////////////////////////////////
//DataSortList<T,E>排序数据表类的定义
//T是关键码的类型,E是数据域的数据的类型
////////////////////////////////////////////////////
template<class T,class E>
class DataSortList
{
private:
Element<T,E>* Vector; //存储带排序的数据元素的向量
int maxSize; //Vector的最大容量
int currentSize; //当前的Vetor里的元素的个数
public:
DataSortList(int sz=DefaultSize)//默认构造函数
{maxSize=sz;currentSize=0;
Vector=new Element<T,E>[maxSize];};
DataSortList(Element<T,E> A[], //构造函数:通过数组来初始化本表
int n);
int Length() //得到当前表的长度
{return currentSize;};
void Swap(Element<T,E>& x,
Element<T,E>& y) //交换两个数据元素的内容
{Element<T,E> temp=x;x=y;y=temp;};
Element<T,E>& operator[](int i) //返回指定编号的结点
{return Vector[i];};
void Display() //显示当前排序表的内容
{for(int i=0;i<currentSize;i++)
cout<<Vector[i].key<<" ";};
void BubbleSort(); //对当前向量进行冒泡升序排序
void BSImprove(); //冒泡排序的一个改进算法
void InsertSort(int left
,int right); //直接插入排序
void BinaryInsertSort(int left
,int right); //折半插入排序
void ShellSort(int left //希尔排序
,int right);
void CompareSort(int left //顺序比较排序法
,int right);
int Partition(int low //对left到right进行划分(快排)
,int high);
int AnoPartition(int low //另一种双向的划分算法
,int high);
void QSort(int left
,int right); //递归:对序列进行快速排序
void QSortImprove1(int left
,int right); //递归:快排的第一种改进算法
void QSortImprove2(int left
,int right); //递归:快排的第二种改进算法
void HybridSort(int left //先快排,得到基本有序序列后
,int right) //再统一进行一趟直接插入排序
{QSortImprove2(left,right);
InsertSort(left,right);}
void SelectSort(int left //直接选择排序
,int right);
void RadixSort(int left, //采用MSD方法的基数排序
int right,int d);
int getDigit(Element<T,E>& v //获取关键码v的第d个排序码
,int d);
};
/////////////////////////DataSortList<T,E>类声明结束
////////////////////////////////////////////////////
//带参数的构造函数
////////////////////////////////////////////////////
template<class T,class E>
DataSortList<T,E>::DataSortList(Element<T,E> A[],int n)
{
maxSize=n+10;
Vector=new Element<T,E>[maxSize];
for(int i=0;i<n;i++) //初始化排序向量
Vector[i]=A[i];
currentSize=n;
};
////////////////////////////////////////构造函数结束
[[it] 本帖最后由 geninsf009 于 2008-11-23 20:51 编辑 [/it]]
