内部排序算法比较.doc

《内部排序算法比较.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内部排序算法比较北京邮电大学05117班杨登锋内部排序算法比较问题描述在课本中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶数或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。需求分析（1）对以下5种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。（2）待排序表的表长不小于100；其中的数据要用伪随机数函数产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（其中关键字交换计为3次移动）。

2、（3）最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解释。测试数据由随机数产生函数生成。第21页共21页内部排序算法比较北京邮电大学05117班杨登锋实现关键主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性；如正序、逆序和不同程度的乱序。程序的运行图如下程序设计如下：Sort.h:第21页共21页内部排序算法比较北京邮电大学05117班杨登锋#ifndefsort_h#definesort_h#include#include

3、stream>#include#include#includeusingnamespacestd;templateclassSeqList{public:SeqList(constintsize=100);~SeqList();SeqList&operator=(SeqList&);voidBubble();//冒泡排序voidInsertSort();//插入排序voidSelectSort();//选择排序voidQuickSort();//快速

4、排序voidShell();//希尔排序voidHalfInsertSort();//折半插入排序voidMergeSort();//归并排序的非递归算法voidHeapSort();//堆排序voidBidirInsert();//二路插入排序voidDel();//删除线型表里的元素intLength()const;//线形表长度intFind(constT&x)const;//查找值为x的位置intInsert(T&x,inti);//将x插入位置iboolIsEmpty()const;//判空boolIsFull

5、()const;//判满TGet(inti);//查找i位置的元素voidPrint();//打印T*data;//线型表的表头指针private:intmaxsize;//线型表的最大容纳元素个数intlast;//线型表表尾指针};第21页共21页内部排序算法比较北京邮电大学05117班杨登锋templateSeqList::SeqList(constintsize){assert(size>=0);//TestsastringtoseeifitisNULL,empty,orlongerthan

6、0charactersif(size>0){maxsize=size;last=0;data=newT[maxsize];if(data==NULL)cout<<"内存申请错误!"<SeqList::~SeqList(){delete[]data;}templateSeqList&SeqList::operator=(SeqList&s){if(s.last>0){delete[]data;maxsize=s.maxsize;las

7、t=s.last;data=newT[maxsize];for(inti=1;i<=last;i++){data[i]=s.data[i];}}return*this;}templatevoidSeqList::Bubble()第21页共21页内部排序算法比较北京邮电大学05117班杨登锋{inta=1;inti=0;//inttemp;intx=0;inty=0;while(a){a=0;for(i=1;idata[i+1]){data[0]=data[

8、i];data[i]=data[i+1];data[i+1]=data[0];a++;x+=3;}y++;}}cout<<"比较次数为:"<voidSeqList::InsertSort(){/*SeqList<