内部排序算法比较.doc

内部排序算法比较 北京邮电大学05117班 杨登锋 第 PAGE 21 页 共 NUMPAGES 21 页 内部排序算法比较 问题描述 在课本中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶数或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 需求分析 （1）对以下5种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。 （2）待排序表的表长不小于100；其中的数据要用伪随机数函数产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（其中关键字交换计为3次移动）。 （3）最后要对结果做出简单分析，包括对各组数据得出结果波动大小的解释。 测试数据 由随机数产生函数生成。 实现关键 主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性；如正序、逆序和不同程度的乱序。 程序的运行图如下 程序设计如下： Sort.h: #ifndef sort_h #define sort_h #include stdio.h #includeiostream #include assert.h #includecstdlib #includeiomanip using namespace std; template class T class SeqList { public: 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 class T SeqList T::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 T[maxsize]; if(data == NULL) cout内存申请错误!endl; } }; template class T SeqList T::~SeqList() { delete[] data; } template class T SeqList T SeqList T::operator = (SeqListT s) { if (s.last 0) { delete[] data; maxsize = s.maxsize; last = s.last; data = new T[maxsize]; for(int i=1;i=last;i++) { data[i] = s.data[i]; } } return *this; } template class T void SeqList T::Bubble() { int a=1; int i=0; //