实验五 内部排序算法比较.doc

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

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

3、td;template class SeqListpublic:SeqList (const int size = 100);SeqList();SeqListvoid Bubble();/冒泡排序void InsertSort();/插入排序void SelectSort();/选择排序void QuickSort();/快速排序void Shell();/希尔排序void HalfInsertSort();/折半插入排序void MergeSort();/归并排序的非递归算法void HeapSort();/堆排序void BidirInsert();/二路插入排序void Del();/

4、删除线型表里的元素int Length() const;/线形表长度int Find( const T /查找值为x的位置int Insert ( T /将x插入位置ibool IsEmpty()const;/判空bool IsFull() const;/判满T Get( int i );/查找i位置的元素void Print();/打印T *data;/线型表的表头指针private:int maxsize;/线型表的最大容纳元素个数int last;/线型表表尾指针;内部排序算法比较 北京邮电大学 05117 班 杨登锋第 4 页 共 21 页template SeqList :SeqLi

5、st(const int size)assert (size = 0);/Tests a string to see if it is NULL, empty, or longer than 0 charactersif (size 0)maxsize = size;last = 0;data = new Tmaxsize;if(data = NULL)coutSeqList :SeqList()delete data;template SeqList maxsize = s.maxsize;last = s.last;data = new Tmaxsize;for(int i=1;ivoid

6、 SeqList :Bubble()内部排序算法比较 北京邮电大学 05117 班 杨登锋第 5 页 共 21 页int a=1;int i=0;/ int temp;int x=0;int y=0;while(a)a = 0;for(i=1;idatai+1)data0=datai;datai=datai+1;datai+1=data0;a+;x+=3;y+;coutvoid SeqList :InsertSort()/* SeqList sTemp(Length()+1);int temp=0;sTemp.Insert(temp,0);for(int i=0;ivoid SeqList :

7、SelectSort()int a;int b = 0;/ int temp;int n = 0;int x = 0;int y = 0;for(int i=1;ivoid SeqList:QuickSort()int x = 0,y = 0;QSort(*this,1,Length(),x,y);coutvoid SeqList :Shell()/* SeqList sTemp(Length()+1);int temp=0;sTemp.Insert(temp,0);for(int i=0;i=1;t=t/2)for(int i=t+1;i0last=0;template int SeqLis

8、t :Length() constreturn last;内部排序算法比较 北京邮电大学 05117 班 杨登锋第 9 页 共 21 页template int SeqList :Find(const T while (i last )return 0;elsereturn i;template int SeqList :Insert(T elselast+;for (int j = last; j i; j-)dataj = dataj-1;datai = x;return 1;template bool SeqList :IsEmpty()constif(last = 0)return 1

9、;elsereturn 0;template bool SeqList :IsFull() const内部排序算法比较 北京邮电大学 05117 班 杨登锋第 10 页 共 21 页if(last = maxsize - 1)return 1;elsereturn 0;template T SeqList :Get(int i)if(i last)return NULL;else return datai;int Partition(SeqList int pivotkey=L.datafirst;while(first=pivotkey)end-;y+;if(firstend) L.datafirst = L.dataend;L.dataend = -1;x+;while(firstendy+;if(firstend) L.dataend = L.datafirst;L.datafirst = -1;x+;