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

《排序算法的实现和比较.docx》由会员分享，可在线阅读，更多相关《排序算法的实现和比较.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验七排序算法的实现和比拟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

2、 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 &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()

3、(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 的内容#includeusing namespace

4、std;enumError_codesuccess,fail,rang_error,range_error,underflow,overflow,not_present;6、Sortablejist的类的定义及函数实现template class Sortablejist: public List public:Sortable_list();virtual-Sortable_list();void insertion_sort();void selcction_sort();void shell_sort();void quick_sort();void heap_sort();void m

5、erge_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 ¤t, int low, int high);void build_heap();void recursive_merge

6、_sort(int low, int high);；/template 构造函数SortableistvRecord:Sortableist()template class Record析构函数Sortable_list:Sortable_list()()template 插入排序void Sortablc_list:insertion_sort()(int first_unsorted;int position;Record current;for(first_unsorted= l;first_unsortedcount;first_unsorted+) if(entryfirst_uns

7、orted0&entryposition-1 lcurrent);entryposition=cuncnt;template 选择排序 void Sortable_list:selection_sort()(for (int position = count - 1; position 0; position) (int max = max_key(0, position);swap(max, position);I)template void Sortable_list:swap(int low, int high)Record temp;temp = entry low;entryflow

8、l = entryfhighl;entryhighj = temp;1template int Sortable_list: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;)templatevoid Sorlableist:selection_sort()(for(position=count-

9、1 ;position0;position-)(int max=max_key(0,position);swap(max,position);)1teniplateint max_key(int low,int high)int cuiTent;int largest=low;for(current=low+1 ;current=high;current+) if(entrylargestentrycurrent)largest二current;return largest;)lemplatevoid swap(int low,int high);Record temp;temp=entryl

10、ow;entry low=entry high;entryhighl=temp;)template 希尔排序void Sorlable_lisl: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_unsorte

11、d count;first_unsorled += increment)if (entryfirst_unsorted start & entrylplace - increment current); entryplace = current;I1template void Sortable_list:shell_sort()int increment, / spacing of entries in sublist start; / starting point of sublistincrement = count;do(increment = increment / 3 + 1;for

12、 (start = 0; start 1);)template 快速排序void Sortable_list:quick_sort()recursive_quick_sort(0, count - 1);)template void Sorlable_lisl:recursive_quick_sort(int low, int high)(int pivot_position; /枢轴位置if (low high) / Otherwise, no sorting is needed.pivot_position = partition(low, high);分成两组 第一趟排序recursiv

13、e_quick_sort(low, pivot_position - 1); 枢轴左边的进行递归排序recursive_quick_sorl(pivot_position + 1, high); /枢轴右边的进行递归排序 I1template int Sortable_list: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)

14、;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

15、; 返回枢轴位置template 堆排序void Sortable_list:insert_heap(const Record ¤t, 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)break; / current bel

16、ongs 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 void Sortable_list:build_heap()(int low; / All entries beyond the position low form a heap, for (low = count/2-1; low= 0; low)(Record curr

17、ent = entrylow;insert_heap(cunent, low, count - 1);)template void Sortableist: 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;

18、 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 归并排序void Sorlableisl:merge_sort() (recursive_merge_sort(0, size()

19、 - 1);)template void Sortable_list: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+ = entryin

20、dex2+; )while (index 1 = mid)tempfindex+ = entryindexl+;while (index2 = high)tempindex+ = entry findex2+;for (index = low; index = high; index+) entryindex = tempindex -low;delete temp;)template void Sortable_list:recursive_merge_sort(int low, int high) if (high low) recursive_merge_sort(low, (high

21、+ 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()(Sortab

22、le_list the_list;SortableJist 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;cased: case *D*:cout ,nUnsorted list nH;the_list.traverse(write_entry

23、);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:堆排序