排序算法的实现和比较.docx

实验七排序算法的实现和比拟1、List类的定义及实现方法运用顺序线性表，详见实验五List类的实现和应用2、Key类的定义及实现方法class Key int key;public:static int comparisons;static int assignments;static void initialize();static int counter();Key (int x = 0 );int the_key() const;Key &operator =(const Key &y); )；bool operator =(const Key &y,const Key &x);bool operator !=(const Key &y,const Key &x);bool operator >=(const Key &y,const Key &x);bool operator <=(const Key &y,const Key &x);bool operator >(const Key &y,const Key &x);bool operator <(const Key &y,const Key &x); /-int Key:comparisons = 0;int Key:assignments = 0;void Kcy:initializc()(comparisons = 0;)int Key:counter()( return comparisons;1Key:Key (int x)(key = x;)Key &Key: operator =(const Key &x) Key:assignments+;key = x.key;return *this;)bool operator =(const Key &x, const Key &y)cout « "Time: " «clock.elapsed_time() « " seconds An”« "Comparisons: " « Key:comparisons « "n"« "Assignments: '' « Key:assignments« endl;break;case T: case 'F':the_list.clear();copy_list.clear();break;case *i*: case T:int i=O,list_entries,kind; ifstream inFile;cout «nHow many list entries would you like? n«H(20,200,2000)0; cin»list_cntries;cout « ”which kind of list would you choose? n" vv''(0随机顺序 list,1顺序 list,逆序 list)cin»kind;if(kind=0)if(list_entries=20)inFile.open("F:随机顺序 list20.txt*);else if(list_entries=200)inFile.open("F:随机顺序 list200.txt");else inFilc.opcn("F:随机顺序 list2000.txt*');)else if(kind=l) 翻开 顺序 List )else 翻开逆序List if(!inFile.is_open()cout«*Could not opened!nH;for(string str;getline(inFile,str);) int a;for(istringstream siii(str);sin»a;)(the_list.insert(i,a);copy_list.inscrt(i,a);i+；)inFile.close();break;/ end of outer switch statement/ end of outer while statementreturn 0;Key: :comparisons+;return x.the_key() = y.the_key();)bool operator !=(const Key &x, const Key &y)Key:comparisons+;return x.the_key() != y.the_key();)bool operator >=(const Key &x, const Key &y)(Kcy:comparisons+;return x.the_key() >= y.the_key();)bool operator <=(const Key &x, const Key &y)(Key:comparisons+;return x.thc_kcy() <= y.thc_kcy();)bool operator >(const Key &x, const Key &y)Key: :comparisons+;return x.the_key() > y.the_key();1bool operator <(const Key &x, const Key &y)(Key: :comparisons+;return x.the_key() < y.the_key();)int Key:the_key() const(return key;13、Timer类的定义及函数实现 详见书本6804、Random类的定义及函数实现 详见书本6686715、utility.h 的内容#include<iostream>using namespace std;enumError_codesuccess,fail,rang_error,range_error,underflow,overflow,not_present;6、Sortablejist的类的定义及函数实现template <class Record>class Sortablejist: public List<Record> public:Sortable_list();virtual-Sortable_list();void insertion_sort();void selcction_sort();void shell_sort();void quick_sort();void heap_sort();void merge_sort();private:void sort_interval(int start, int increment);void swap(int low, int high);int max_key(int low, int high);int partition(int low, int high);void recursive_quick_sort(int low, int high);void insert_heap(const Record &current, int low, int high);void build_heap();void recursive_merge_sort(int low, int high);；/template <class Record> 构造函数SortableistvRecord>:Sortableist()template <class Record析构函数Sortable_list<Record>:Sortable_list()()template <class Record> 插入排序void Sortablc_list<Record>:insertion_sort()(int first_unsorted;int position;Record current;for(first_unsorted= l;first_unsorted<count;first_unsorted+) if(entryfirst_unsorted<entryfirst_unsorted-1 )(position=first_unsorted;cuiTent=entryfirst_unsortcd;do(entryposition=entryposition-1 ;position;)while(position>0&&entryposition-1 l>current);entryposition=cuncnt;template <class Record> 选择排序 void Sortable_list<Record>:selection_sort()(for (int position = count - 1; position > 0; position) (int max = max_key(0, position);swap(max, position);I)template <class Record>void Sortable_list<Record>:swap(int low, int high)Record temp;temp = entry low;entryflowl = entryfhighl;entryhighj = temp;1template <class Record>int Sortable_list<Record>:max_key(int low, int high)(int largest, current;largest = low;fbr (current = low + 1; current <= high; currcnt+)if (entryflargest < entryfeurrent)largest = current;return largest;)template<class Record>void Sorlableist<Record>:selection_sort()(for(position=count-1 ;position>0;position-)(int max=max_key(0,position);swap(max,position);)1teniplate<class Record>int max_key(int low,int high)int cuiTent;int largest=low;for(current=low+1 ;current<=high;current+) if(entrylargest<entrycurrent)largest二current;return largest;)lemplate<class Record>void swap(int low,int high);Record temp;temp=entrylow;entry low=entry high;entryhighl=temp;)template <class Record> 希尔排序void Sorlable_lisl<Record>:sort_inlerval(int start, int increment)(int first_unsorted; / position of first unsorted entryint place; / searches sorted part of listRecord current; / used to swap entriesfor (first_unsorted = start + increment; first_unsorted < count;first_unsorled += increment)if (entryfirst_unsorted < enttyfirst_unsorted - increment) (place = first_unsortcd;current = entry first_unsorted;/ Pull entryfirst_unsorted out of the list, do / Shift all previous entries one place down the list entryplace = entryplace - increment;/ until the proper place is found.place -= increment;/ Position place is now available for insertion.)while (place > start && entrylplace - increment > current); entryplace = current;I1template <class Record>void Sortable_list<Record>:shell_sort()int increment, / spacing of entries in sublist start; / starting point of sublistincrement = count;do(increment = increment / 3 + 1;for (start = 0; start < increment; start+) sort_interval(start, increment); / modified insertion sort)while (increment > 1);)template <class Record>快速排序void Sortable_list<Record>:quick_sort()recursive_quick_sort(0, count - 1);)template <class Record>void Sorlable_lisl<Record>:recursive_quick_sort(int low, int high)(int pivot_position; /枢轴位置if (low < high) / Otherwise, no sorting is needed.pivot_position = partition(low, high);分成两组 第一趟排序recursive_quick_sort(low, pivot_position - 1); 枢轴左边的进行递归排序recursive_quick_sorl(pivot_position + 1, high); /枢轴右边的进行递归排序 I1template <class Rccord>int Sortable_list<Record>:partition(int low, int high)Record pivot;int i, / used to scan through the listlast_small; / position of the last key less than pivotswap(low, (low + high) / 2);pivot = entrylowj; / First entry is now pivot.Iast_small = low;for (i = low + 1; i <= high; i+)if (entryi < pivot)(last_small = last_small + 1;第一个比 pivot 大的数swap(last_small, i);/ Move large entry to right, small to left.)swap(low, last_small); / Put the pivot into its proper position.return last_small; 返回枢轴位置template <class Record> 堆排序void Sortable_list<Record>:insert_heap(const Record &current, int low, int high)int large; / position of child of entrylowl with the larger key large = 2 * low + 1 'JI large is now the left child of low. while (large <= high) (if (large < high && entry large < entry large + 1) large+； / large is now the child of low with the largest key.if (current >= entry large)break; / current belongs in position low.else / Promote entry large and move down the tree.(entryllowj = entry largej;low = large;large = 2 * low + 1;I)entry low = current;)template <class Record>void Sortable_list<Record>:build_heap()(int low; / All entries beyond the position low form a heap, for (low = count/2-1; low>= 0; low)(Record current = entrylow;insert_heap(cunent, low, count - 1);)template <class Record>void Sortableist<Record>: he 叩 _sori()(Record current; / temporary storage for moving entriesint last_unsortcd; / Entries beyond last_unsortcd have been sorted. build_heap(); / First phase: Turn the list into a heap.for (last_unsorled = count - 1; last_unsorted > 0; Iast_unsorled-) (current = entrylast_unsortedl; / Extract last entry from the list. entr)zlast_unsorted = entry(); / Move top of heap to the end insert_heap(current, 0,1 ast_unsorted - 1); / Restore the heap)template <class Record> 归并排序void Sorlableisl<Record>:merge_sort() (recursive_merge_sort(0, size() - 1);)template <class Record>void Sortable_list<Record>:merge(int low, int high) (Record *temp = new Recordhigh - low + I;int index = 0;int index 1 = low, mid = (low + high) / 2, index2 = mid + 1;while (index 1 <= mid && index2 <= high) (if (entryindexl J < entryindex2J) temp index+ = entryfindexl+;elsetempi index+ = entryindex2+; )while (index 1 <= mid)tempfindex+ = entryindexl+;while (index2 <= high)tempindex+ = entry findex2+;for (index = low; index <= high; index+) entryindex = tempindex -low;delete temp;)template <class Record>void Sortable_list<Record>:recursive_merge_sort(int low, int high) if (high > low) recursive_merge_sort(low, (high + low) / 2);recursive_merge_sort(high + low) / 2 + 1, high); mcrgc(low, high); ) 7、主函数void write_entry(Record &c) (cout « (Key) c).the_key() « '；)void help()cout« "User options are:nH « HH,h help n“)void intro()cout « ”Testing program for sorting methods for a contiguous Iist.H« endl; help ();)int main()(Sortable_list<Record> the_list;SortableJist<Record> copyjist;intro();char command = * *;while (command != *q* && command != 'Q')(cout « "Enter a command of H, I, Q, F, O, D, 0,1, 2, 3, 4, 5: *« flush;cin » command;switch (command)(case *h*: case *H':help();break;case'd': case *D*:cout « ,nUnsorted list nH;the_list.traverse(write_entry);cout« endl;break;case 'o': case *O':cout « "nLast sorted list nM;copy_list.traverse(write_entry);cout« endl;break;case 'O': case '1': case 2: case 3: case '41: case '5':copy_list=the_list;Key: comparisons = 0;Key: assignments = 0;Timer clock;switch (command)case '1':选择排序case '1':选择排序case '3': 快速排序case 5: 归并排序(case 'O': 插入排序cout « ”Insertion Sort nM;copy_list.insertion_sort();break;case 2:希尔排序case '4':堆排序