以下是我的数据结构作业
学习算法，去HDU POJ找相应的题目，更容易练习掌握
/** Function：Mergesort 归并排序 Compiler：CodeBlocks 16.0 Developer：me Date: December 22, 2016 Version: 1.0 References：Data Structures and Algorithm Analysis in C++ (3rd Ed) Author: Mark Allen Weiss Pages: 274-279(3rd Ed) */ /** 归并排序是一个O(n log n)排序算法。 大多数实现产生一种稳定（实现输入的相等元素的在排序后顺序按输入顺序） 归并排序是一个分而治之算法,是约翰·冯·诺依曼在1945年发明的。 从概念上讲,归并排序的工作原理如下： 未排序的列表划分为n子列表,每个包含1元素(列表1元素被认为是排序)。 多次合并子列表产生新的经排序子列表,直到剩下只有1子列表，这将是排序列表。
归并排序算法是两个重要的分而治之的排序算法之一(另一个是快速排序)。 */ #include "iostream" #include "cstdlib" #include "cstdio" using namespace std; const int SPARE_CAPACITY=16; template <typename Object> class Vector { public: Vector(int InitSize = 0 )//创建空表 : theSize( InitSize ), theCapacity( InitSize + SPARE_CAPACITY ) { objects = new Object[ theCapacity ]; } Vector( const Vector & rhs ) : objects( NULL )//拷贝构造函数 { operator=( rhs ); } ~Vector() { delete [] objects; } const Vector & operator= ( const Vector & rhs )//赋值运算符以重载 { if( this != &rhs ) { delete [] objects; theSize = rhs.size(); theCapacity = rhs.theCapacity; objects = new Object[ capacity() ]; for( int k = 0; k < theSize; k++ ) objects[ k ] = rhs.objects[ k ]; } return *this; } void resize( int newSize )//重设大小 { if( newSize > theCapacity ) reserve( newSize * 2 + 1); theSize = newSize; } void reserve( int newCapacity )//重设容量 { if( newCapacity < theSize ) return; Object *oldArray = objects; objects = new Object[ newCapacity ]; for( int k = 0; k < theSize; k++ ) objects[ k ] = oldArray[ k ]; theCapacity = newCapacity; delete [] oldArray; } void Display(); int Partition ( const int low, const int high );//分割交换 const Object median3(int left,int right);//找基准 Object & operator[]( int index ) { return objects[ index]; } const Object & operator[]( int index ) const { return objects[ index]; } bool empty( ) const { return size() == 0; } int size( ) const { return theSize; } int capacity() const { return theCapacity; } void push_back( const Object & x ) { if( theSize == theCapacity ) reserve( 2 * theCapacity + 1 ); objects[ theSize++ ] = x; } void pop_back( ) { theSize--; } const Object & back () const { return objects[ theSize - 1]; } typedef Object * iterator; typedef const Object * const_iterator; iterator begin( ) { return &objects[ 0 ]; } const_iterator begin() const { return &objects[ 0 ]; } iterator end( ) { return &objects[ size() ]; } const_iterator end( ) const { return &objects[ size() ]; } private: int theSize; int theCapacity; Object * objects; }; template <typename Object> void mergeSort(Vector<Object> & a) { Vector<Object> tmpArray( a.size()); mergeSort(a, tmpArray, 0, a.size()- 1); } /** * 递归实现归并排序 * a是待排序序列 * tmpArray 存储排序结果 * left 是子序列最小下标 * right 是子序列最大下标 */ template <typename Object> void mergeSort(Vector<Object> & a,Vector<Object> & tmpArray, int left, int right) { if (left < right) { int center = (right + left) / 2;//分 mergeSort(a, tmpArray, left, center); mergeSort(a, tmpArray, center + 1, right); merge(a, tmpArray, left, center + 1, right);//合 } } /** * 合并两个子数组的排序部分 * a是待排序序列 * tmpArray 存储排序结果 * leftPos 子序列1最小下标 * rightPos子序列2最小下标 * rightEnd子序列2最大下标 */ template <typename Object> void merge( Vector<Object> & a, Vector<Object> & tmpArray, int leftPos, int rightPos, int rightEnd ) { int leftEnd = rightPos - 1; int tmpPos = leftPos; int numElements = right//2未并完End - leftPos + 1;//合并后个数 while( leftPos <= leftEnd && rightPos <= rightEnd ) if( a[ leftPos ] <= a[ rightPos ] ) //小者先并入 tmpArray[ tmpPos++ ] = a[ leftPos++ ]; else tmpArray[ tmpPos++ ] = a[ rightPos++ ]; while( leftPos <= leftEnd )//1未检测完 tmpArray[ tmpPos++ ] = a[ leftPos++ ]; while( rightPos <= rightEnd )//2未检测完 tmpArray[ tmpPos++ ] = a[ rightPos++ ]; for( int i = 0; i < numElements; i++, rightEnd-- )//将排序结果放回a a[ rightEnd ] = tmpArray[ rightEnd ]; } template<typename Object> void Vector<Object>::Display()//输出 { for(int i=0;i<theSize;i++) { cout<<objects[i]<<" "; } cout<<endl<<endl; } //#################################Main Entry############################## int main() { int a[]={6,3,9,1,5,4,7,2}; Vector<int> d; int t=9; while(--t){ d.push_back(a[10-t]); } cout<<"Style Weiss"<<endl; cout << "The Vector elements before sorting are: " << endl; d.Display(); cout << endl; mergeSort(d); cout << "The Vector elements after sorting(MergeSort) are: " << endl; d.Display(); cout << endl; system("PAUSE"); }
/** Function：Mergesort归并排序 Compiler：CodeBlocks 16.01 Developer：me Date: December 22, 2016 Version: 1.0 References: 参考文献 [1] Data Structures with OOP in C++ language 数据结构（用面向对象方法与C++语言描述） Authors: Yin Renkun殷人昆 Edition: 2 (June, 2007) Print: 11 (January, 2014) Publisher: Tsinghua University Press Pages:422-424 */ /** 归并排序是一个O(n log n)排序算法。 大多数实现产生一种稳定（实现输入的相等元素的在排序后顺序按输入顺序） 此代码采用两路归并排序 */ #include "iostream" #include "cstdlib" using namespace std; const int DefaultSize=100; template<typename T> class Element{//数据表元素定义 public: T key;//排序码 //field otherdata; Element<T>& operator=(Element<T>& x) { key=x.key; return *this; } bool operator==(Element<T>&x) { return key==x.key; } bool operator<=(Element<T>&x) { return key<=x.key; } bool operator>=(Element<T>&x) { return key>=x.key; } bool operator>(Element<T>&x) { return key>x.key; } bool operator<(Element<T>&x) { return key<x.key; } }; template<typename T> class dataList//数据表定义 { public: dataList(int MS=DefaultSize):maxSize(MS),currentSize(0)//构造函数 { Vector =new Element<T>[MS];//数组 } bool add(Element<T>& x) { if(currentSize==maxSize) { cerr<<"列表已满"<<endl; } Vector[currentSize]=x; currentSize++; } void Swap(Element<T>&x,Element<T>&y) { Element<T> temp; temp=x; x=y; y=temp; } int length() { return currentSize; } Element<T>&operator[](int i) { return Vector[i]; } void Display(); int Partition(const int low,const int high);//快速排序划分 private: Element<T> * Vector; int maxSize; int currentSize; }; template<typename T> void dataList<T>::Display()//输出 { for(int i=0;i<currentSize;i++) { cout<<Vector[i].key<<" "; } cout<<endl<<endl; } /** 合并 L1为待排序序列 L2为辅助序列 left */ template<typename T> void Merge(dataList<T>&L1,dataList<T>&L2, const int left,const int mid,const int right) { int s1=left,s2=right,t=left,k; for(k=left;k<=mid;k++)//正向复制 L2[k]=L1[k]; for(k=mid+1;k<=right;k++)//反向复制 L2[right+mid+1-k]=L1[k]; while(t<=right) //归并过程+排序 if(L2[s1]<=L2[s2]) L1[t++]=L2[s1++]; else L1[t++]=L2[s2--]; } /** L为待排序序列 L2为辅助序列 left right 为L序列中要排序的始末下标 */ template<typename T> void MergeSort(dataList<T>&L,dataList<T>&L2,int left,int right) { if(left>=right)return ; //if(right-left+1<M)return;//序列小于M时跳出循环 int mid=(left+right)/2;//分 MergeSort(L,L2,left,mid); MergeSort(L,L2,mid+1,right); Merge(L,L2,left,mid,right);//合并 } template<typename T> void MergeSort(dataList<T>&L) { dataList<T> temp; MergeSort(L,temp,0,L.length()-1); } //#############################Main Entry############################# int main() { Element<int> a[8]; a[0].key=6; a[1].key=3; a[2].key=9; a[3].key=1; a[4].key=5; a[5].key=4; a[6].key=7; a[7].key=2; dataList<int> d,d1; for ( int i=0; i < 8; i++ ) d.add(a[i]); cout<<"MergeSort Style--Yin"<<endl<<endl; cout << "The dataList elements before sorting are: " << endl; d.Display(); cout << endl; MergeSort(d); cout << "The dataList elements after sorting(Mergesort) are: " << endl; d.Display(); cout << endl; system("PAUSE"); }