内部排序算法比较.doc

内部排序算法比较 北京邮电大学05117班 杨登锋内部排序算法比较问题描述 在课本中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶数或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 需求分析（1）对以下5种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。 （2）待排序表的表长不小于100；其中的数据要用伪随机数函数产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（其中关键字交换计为3次移动）。 （3）最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解释。测试数据 由随机数产生函数生成。实现关键 主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性；如正序、逆序和不同程度的乱序。程序的运行图如下程序设计如下：Sort.h:#ifndef sort_h#define sort_h#include #include#include #include#includeusing namespace std;template class SeqListpublic: SeqList (const int size = 100); SeqList();SeqList& operator = (SeqList& );void Bubble();/冒泡排序void InsertSort();/插入排序void SelectSort();/选择排序void QuickSort();/快速排序void Shell();/希尔排序void HalfInsertSort();/折半插入排序void MergeSort();/归并排序的非递归算法void HeapSort();/堆排序void BidirInsert();/二路插入排序void Del();/删除线型表里的元素int Length() const;/线形表长度int Find( const T & x ) const;/查找值为x的位置 int Insert ( T & x, int i );/将x插入位置i bool IsEmpty()const;/判空 bool IsFull() const;/判满 T Get( int i );/查找i位置的元素 void Print();/打印T *data;/线型表的表头指针private: int maxsize;/线型表的最大容纳元素个数 int last;/线型表表尾指针;template SeqList :SeqList(const int size) assert (size = 0);/Tests a string to see if it is NULL, empty, or longer than 0 characters if (size 0)maxsize = size;last = 0;data = new Tmaxsize;if(data = NULL)cout内存申请错误!endl; ;template SeqList :SeqList()delete data;template SeqList & SeqList :operator = (SeqList& s)if (s.last 0)delete data;maxsize = s.maxsize;last = s.last;data = new Tmaxsize;for(int i=1;i=last;i+)datai = s.datai; return *this;template void SeqList :Bubble()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+;cout比较次数为:yendl;cout移动次数为:xendl;template void SeqList :InsertSort()/*SeqList sTemp(Length()+1);int temp=0; sTemp.Insert(temp,0); for(int i=0;iLength()+1;i+) temp = Get(i);sTemp.Insert(temp,i+1);*/int x = 0;int y = 0;for(int i=2;i=last;i+)data0 = datai;x+;for(int j=i-1;data0dataj;j-)dataj+1 = dataj;x+;y+;dataj+1 = data0;cout比较次数为:yendl;cout移动次数为:xendl;/*Del();for(i=0;iLength()+1;i+)temp = sTemp.Get(i+1);Insert(temp,i);*/templatevoid SeqList :SelectSort()int a;int b = 0;/int temp;int n = 0;int x = 0;int y = 0;for(int i=1;iLength();i+)a = datai;for(n=i;nLength();n+)x+;if(datan+1a)a = datan+1;b = n+1;if(a=datai)continue;data0 = a;datab = datai;datai = data0;y += 3;cout比较次数为:xendl;cout移动次数为:yendl;template void SeqList:QuickSort()int x = 0,y = 0;QSort(*this,1,Length(),x,y);cout比较次数为:yendl;cout移动次数为:xendl;template void 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;i0&data0dataj;j=j-t)dataj+t = dataj;x+;y+;dataj+t = data0;cout比较次数为:yendl;cout移动次数为:xendl;/*Del();for(i=0;iLength()+1;i+)temp = sTemp.Get(i+1);Insert(temp,i);*/template void SeqList :Del()if(IsEmpty()return;last=0;template int SeqList :Length() constreturn last;template int SeqList :Find(const T & x ) const int i = 1; while (i last )return 0; elsereturn i;template int SeqList :Insert(T & x, int i) if (i last+1 | last = maxsize - 1 )return 0; elselast+;for (int j = last; j i; j-)dataj = dataj-1;datai = x;return 1; template bool SeqList :IsEmpty()constif(last = 0)return 1;elsereturn 0;template bool SeqList :IsFull() constif(last = maxsize - 1)return 1;elsereturn 0;template T SeqList :Get(int i)if(i last)return NULL;else return datai;int Partition(SeqList &L,int first,int end,int &x,int &y)/快速排序划分int Mark=L.datafirst;int pivotkey=L.datafirst;while(firstend)while(first=pivotkey)end-;y+;if(firstend) L.datafirst = L.dataend;L.dataend = -1;x+;while(firstend&L.datafirst=pivotkey)first+;y+;if(firstend) L.dataend = L.datafirst;L.datafirst = -1;x+;y += 2;L.datafirst = Mark;return first;void QSort (SeqList &L,int low,int high,int &x,int &y)/快速排序int pivotloc;if(lowhigh)pivotloc=Partition(L,low,high,x,y);if(pivotloc!=0)QSort(L,low,pivotloc-1,x,y);if(pivotloc!=high)QSort(L,pivotloc+1,high,x,y);template void SeqList :Print() if ( last = 0 )cout It is empty ; elsefor (int i=1;i=last;i+)coutsetw(5)datai ;if (i%8 = 0) coutendl;cout endl;template void SeqList :HalfInsertSort()int x = 0;int y = 0;for(int i=2;i=last;i+)data0 = datai;x+;int low = 1;int high = i-1;while(low=high)/在Keylow.high中折半查找有序插入的位置int m=(low+high)/2;if(data0=high+1;-j) dataj+1 = dataj;x+;dataj+1 = data0;y+;cout比较次数为:yendl;cout移动次数为:xendl;template void Merge(SeqList &r, SeqList & r1, int s, int m, int t,int &y,int &x)int i = s;int j = m+1;int k = s;while (i=m & j=t) if (r.datai=r.dataj) r1.datak+ = r.datai+; /取ri和rj中较小者放入r1kelse r1.datak+ = r.dataj+; y+;x+;if (i=m) while (i=m) /若第一个子序列没处理完，则进行收尾处理 r1.datak+ = r.datai+; else while (j=t) /若第二个子序列没处理完，则进行收尾处理 r1.datak+ = r.dataj+;template void MergePass(SeqList & r, SeqList &r1, int n, int h,int &y,int &x)/一趟归并int i = 0;while (i=n-2*h+1) /待归并记录至少有两个长度为h的子序列Merge(r, r1, i, i+h-1, i+2*h-1,y,x); i += 2*h;if (i=(n-h) Merge(r, r1, i, i+h-1, n,y,x); /待归并序列中有一个长度小于helsefor (int k=i;k=n;k+) /待归并序列中只剩一个子序列r1.datak = r.datak;x+;template void SeqList :MergeSort()/归并排序的非递归算法 int h=1;int x = 0;int y = 0;int temp;int n = Length()+1;SeqList r1(Length()+1);for(int i=0;iLength()+1;i+)temp = Get(i);r1.Insert(temp,i+1);while (h=n) MergePass(*this,r1,n-1,h,y,x); /归并h = 2*h;MergePass(r1,*this,n-1,h,y,x);h = 2*h;cout比较次数为:yendl;cout移动次数为:xendl;template void SeqList :HeapSort()/堆排序int i;int temp;int n = Length();int x = 0;int y = 0;for (i=n/2; i=1; i-) /初始建堆，从最后一个非终端结点至根结点Sift(*this,i,n,y,x); for (i=1; in; i+) /重复执行移走堆顶及重建堆的操作temp = datan-i+1;datan-i+1 = data1;data1 = temp;x = x+3;Sift(*this,1,n-i,y,x);cout比较次数为:yendl;cout移动次数为:xendl;template void Sift(SeqList &L1,int k,int m,int &y,int &x)int temp;int i = k; int j = 2*i; /置i为要筛的结点，j为i的左孩子while (j=m) /筛选还没有进行到叶子if (jm &L1.datajL1.dataj)/根结点已经大于左右孩子中的较大者break;elsetemp = L1.datai;L1.datai = L1.dataj;L1.dataj = temp; /将根结点与结点j交换i = j;j = 2*i; /被筛结点位于原来结点j的位置x = x+3; y+;template void SeqList :BidirInsert()SeqList sTemp(Length()+1);int x=0,y=0;int i;int first = 1;int final = 1;int n = Length()+1;sTemp.data1 = data1; /* 将第一个元素放入辅助数组 */利用辅助数组 sTemp.data 进行二路插入排序 for ( i = 2; in; i+ )if ( sTemp.datafinal = datai ) y+;sTemp.data+final = datai;x+; else if ( datai = sTemp.datafirst )y+;first = (first - 1 + n) % n;sTemp.datafirst = datai;x+;elseint index; for ( index = (final - 1 + n) % n;index = (index - 1 + n) % n)if ( sTemp.dataindex = datai )y+;int mid = final+;/* 元素后移 */while ( mid != index )sTemp.data(mid + 1) % n = sTemp.datamid;x+;mid = (mid - 1 + n) % n;sTemp.data(index + 1) % n = datai;x+;break;/ 将 sTemp.data 的内容按顺序复制到 keys 中 for ( i = 1; in; i+ )datai = sTemp.datafirst;x+;first = (first + 1) % n;cout比较次数为yendl;cout交换次数为xendl; / End of bidir_insert #endifTest.cpp:#include sort.h#include #include #include using namespace std;void main()int num = 100;LARGE_INTEGER litmp ; LONG64QPart1,QPart2 ; doubled=0; char choice = a;while(num=0)coutnum;if(num0)cout谢谢使用!Bye!endl;elseif (num = 0)num = 100;SeqList s1(num+1),pSort(num+1),shunxu(num+1),nixu(num+1);int i,keyin=1,y=0,a=0,b=0;srand(unsigned)time(NULL);while(s1.IsFull()=0)i = rand();if(i0)s1.Insert(i,keyin);keyin+;pSort = s1;pSort.Bubble();shunxu = pSort;for(i=1;i=num;i+)nixu.Insert(pSort.datanum-i+1,i);docoutendl;cout1.起泡排序endl;cout2.直接插入排序endl;cout3.简单选择排序endl;cout4.快速排序endl;cout5.希尔排序endl;cout6.折半插入排序endl;cout7.二路归并排序endl;cout8.堆排序endl;cout9.二路插入排序endl;cout10.打印数组endl;cout11.打印排序结果endl;cout0.退出endl;coutkeyin;coutendl;if(keyin = 10)coutendl原数组:endl;if (choice = A|choice = a)s1.Print();else if(choice = B|choice = b)shunxu.Print();else if(choice = C|choice = c)nixu.Print();coutendl;else if(keyin = 11)coutendl排序后的数组:endl;pSort.Print();coutendl;