各种排序算法课程设计报告

1、封面 课程设计题目 内部排序算法比较 学院 软件学院 专业 软件工程 年级 2008级 已知参数和设计要求： 问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶， 或大概执行时间。 试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 学生应完成的工作： 基本要求 （1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。 （2）待排序表的表长不少于100;其中的数据要用伪随机数产生程序产生；至少要用5 组不向的输入数据作比较；比较的指标为有关键字参

2、加的比较次数和关键字移动次数（关键字 交换计为3次移动）。 测试数据由随机产生器决定。 目前资料收集情况（含指定参考资料）： C+嗷据结构与程序设计RobertL.KruseAlexanderJ.Ryba北京，清华大学出版社，2004.1 课程设计的工作计划： 先制作规划大纲，在从基础的表开始做，冉研究核心的算法，各种排序函数的实现，最后用其他辅助类用于实现效率的比较，和测试数据的产生。最后在优化程序，添加注释。 任务下达日期2010年4月26日完成日期2010年5月30日 指导教师（签名）学生（签名） 说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003重庆大学本科学生课

3、程设计任务书 课程设计题目 学院专业年级 已知参数和设计要求： 学生应完成的工作: 目前资料收集情况（含指定参考资料） 课程设计的工作计划: 重庆大学本科学生课程设计任务书 课程设计题目 学院专业年级 已知参数和设计要求： 学生应完成的工作: 目前资料收集情况（含指定参考资料） 课程设计的工作计划:重庆大学本科学生课程设计任务书 课程设计题目 学院专业年级 已知参数和设计要求： 学生应完成的工作: 目前资料收集情况（含指定参考资料） 课程设计的工作计划: 摘要 本文主要针对各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和

4、关键字移动次数，以取得直观感受，对各种算法比较次数和移动次数的比较，针对各种不同数组如何选择更高效的排序方法，给出一定的指导。各种算法的稳定性也至关重要，对于各种不同类型的数据，各种算法的效果有明显差异，所以针对每种算法，都有不同的数据与之对应，该稳定性表明算法的稳定程度。有效时间则为各种算法针对每组数据实际用掉的计算机时间，可以分析各种排序算法的时间效率。 关键字时间复杂度有效时间稳定性一问题重述 1.1 问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 1.2 基本要求 (1

5、)对以下10种常用的内部排序算法进行比较： 直接插入排序； 折半折入排序;二路插入排序； 希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。 (2)待排序表的表长不少于100;其中的数据要用伪随机数产生程序产生； 至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数(关键字交换计为3次移动)。 二算法构建 () 算法思想 所谓排序,就是要整理文件中白记录,使之按关键字递增(或递减)次序排列起来。 当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。 在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字

6、的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。 要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。 .2 插入排序 插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。 .直接插入排序(稳定) 接插入排序的过程为：在插入第i个记录时，R1,R2,.Ri-1已经排好序，将第i个记录的排序码Ki依次和R1,R2,.,Ri

7、-1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。 .希尔排序(不稳定)： 希尔(Shell)排序的基本思想是： 先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d2d1重复上述的分组和排序，直至 所取的增量di=1,即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。 一般取d1=n/2,di+1=di/2。如果结果为偶数，则加1,保证di为奇数。 希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平

8、均时间复杂度为O(n7.3). .2 选择排序选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。 .直接选择排序(不稳定) 直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换依次类推，直到所有记录排完为止。 无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n(n-1)/2=O(nA2)o当初始文件为正序时， 移动次数为0;文件初态为反序时， 每趟排序均要执行交换

9、操作，总的移动次数取最大值3(n-1)0 直接选择排序的平均时间复杂度为O(nA2)。直接选择排序是不稳定的。 .堆排序(不稳定) 堆排序是一种树形选择排序,是对直接选择排序的有效改进。n个关键字序列 K1,K2,.,Kn称为堆，当且仅当该序列满足(Ki=K2i且Ki=K2i且Ki=K2i+1),(1=ik2,则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置，称第1次起泡，共执行n-1次比较。 与第一步类似，从k1和k2开始比较，至ijkn-2和kn-1为止，共执行n-2次比较。比较(1=i=n-1),且每次比较

10、都必须移动记录三次来达到交换记录位置。在这种情况下，比较次数达到最大值n(n-1)/2=O(nA2),移动次数也达到最大值3n(n-1)/2=O(nA2)。因此，冒泡排序的最坏时间复杂度为O(nA2)。 虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均性能比直接插入排序要差得多。冒泡排序是就地排序，且它是稳定的。 .快速排序：(不稳定的) 快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程如下： 第一步，在待排序的n个记录中任取一

11、个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。 第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。 .2 归并排序 归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。 归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现，对长度为n的文件，需进行10g2n趟二路归并，

12、每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。归并排序需要一个辅助向量来 暂存两个有序子文件归并的结果，故其辅助空间复杂度为O(n),显然它不是就地排序。 五.基数排序 设单关键字的每个分量的取值范围均是C0=Kj=Crd-1(0=j=(constKey&y,constKey&x);booloperator(constKey&y,constKey&x); booloperator(constKey&y,constKey&x); 随机数数据类型 classRandom public: Random

13、(boolpseudo=true); intrandom_integer(intlow,inthigh); doublerandom_real(); private: intreseed();/Re-randomizetheseed. intseed, multiplier,add_on;/constantsforuseinarithmeticoperations; 可排序的顺序表数据类型 template classsortable_list:publicmylist ( public: sortable_list():mylist() voidinsertion_sort(); voids

14、election_sort(); voidswap(intlow,inthigh); intmax_key(intlow,inthigh); voidquick_sort(); voidrecursive_quick_sort(intlow,inthigh); intpartition(intlow,inthigh); voidmerge_sort(); voidrecursive_merge_sort(intlow,inthigh); voidmerge(intlow,inthigh); voidheap_sort(); voidinsert_heap(constList_entry&

15、;current,intlow,inthigh); voidbuild_heap(); voidscan_sort(); voidinsertion_binary(); voidbubble_sort(); voidshell_sort(); voidsort_interval(intstart,intincrement); ;一 计算机时间数据类型 classTimer public: Timer(); doubleelapsed_time(); voidreset(); private: clock_tstart_time; ; 三算法实现 源程序 #include #includesor

16、table_list.h #includeTimer.h #includeRandom.h usingnamespacestd; sortable_listthe_list; sortable_listcopy_list; voidwrite_entry(Key&c) (. cout(Key)c).the_key(); . voidhelp()/帮助函数 ( coutUseroptionsare:n HelpQuit(re)Filllistn writeDatawritesortedOutputn 0insertionsort-Project2P1dn 1selectionsort-P

17、roject3P1n 2shellsort-Project4P2n 3quicksortn 4heapsortn 5insertion,withbinarysearch-project2P2n 6scansort-Project2P3n 7bubblesort-Project2P4n 8mergesort-Project7P4n endl; voidintro()/介绍函数 ( coutTestingprogramforsortingmethodsforacontiguouslist. endl; help(); voidmain() ( intro(); intn; Randomdice;/

18、随机数Error_codereport; Keytarget;/目标键 charcommand=; while(command!=q&command!=Q)coutEnteracommandofH,Q,F,O,D, 0,1,2,3,4,5,6,7,8,9,b: command; switch(command) caseh:caseH: help(); break; cased:caseD: coutnUnsortedlistn; /大循环函数，不退出一直循环执行 the_list.traverse(write_entry); coutendl; break; caseo:caseO:

19、coutnLastsortedlistn; copy_list.traverse(whte_entry);/写出数组 coutendl; break; case0:case1:case2:case3:case4:case5: case6:case7:case8:case9:caseb:caseB:/选择不同的排序函数copy_list=the_list; Key:comparisons=0; Key:assignments=0; Timerclock; switch(command) case0: coutInsertionSort; copy_list.insertion_sort(); b

20、reak; case1: coutSelectionSort; copy_list.selection_sort(); break; case2: coutShellSort; copy_list.shell_sort(); break; case3: coutQuickSort; copy_list.quick_sort(); break; case4: coutHeapSort; copy_list.heap_sort(); break; case5: coutInsertionSortwithbianrysearch; copy_list.insertion_binary(); brea

21、k; case6: coutScanSort; copy_list.scan_sort(); break; case7: coutBubbleSort; copy_list.bubble_sort(); break; case8: coutMergeSort; copy_list.merge_sort(); break; ) coutTime:clock.elapsed_time()seconds.n输出运行时间 Comparisons:Key:comparisonsn Assignments:Key:assignments endl; ) break; casef:caseF: the_li

22、st.clear();/清空表 coutHowmanylistentrieswouldyoulike? n; for(inti=0;in;i+)/循环赋予表中数组随机数 target=dice.random_integer(0,10*n); report=the_list.insert(i,target); if(report=overflow) coutAvailablelistspacef川edupati entries.endl; break; ) if(report!=success)i-;更新计数i ) break; /endofouterswitchstatement /endof

23、outerwhilestatement #includeRandom.h #include #include #includeusingnamespacestd; intRandom二reseed()/产生随机数种子函数/* Post:Theseedisreplacedbyapseudorandomsuccessor. */ seed=seed*multiplier+add_on; returnseed; ) Random二Random(boolpseudo)幽造函数/* Post:Thevaluesofseed,add_on,andmultiplierare initialized.Thes

24、eedisinitializedrandomlyonlyifpseudo=false.*/ if(pseudo)seed=1; elseseed=time(NULL)%INT_MAX; multiplier=2743; add_on=5923; ) doubleRandom:random_real()/产生随机实数函数/* Post:Arandomrealnumberbetween0and1isreturned. */ doublemax=INT_MAX+1.0; doubletemp=reseed(); if(temphigh)returnrandom_integer(high,low);

25、elsereturn(int)(high-low+1)*random_real()+low; 一 #includekey.h #include intKey:comparisons=0; intKey:assignments=0; voidKey:initialize()初始化函数 comparisons=0; intKey:counter()/计数函数 returncomparisons; Key:Key(intx) key=x; Key&Key:operator=(constKey&x)/重载赋值运算符 Key:assignments+; key=x.key; return

26、*this; booloperator=(constKey&x,constKey&y) Key:comparisons+; returnx.the_key()=y.the_key(); 一一 booloperator!=(constKey&x,constKey&y) Key:comparisons+; returnx.the_key()!=y.the_key(); 一一 booloperator=(constKey&x,constKey&y) Key:comparisons+; returnx.the_key()=y.the_key(); ) b

27、ooloperator=(constKey&x,constKey&y) ( Key:comparisons+; returnx.the_key()(constKey&x,constKey&y) ( Key:comparisons+; returnx.the_key()y.the_key(); )一一 booloperator(constKey&x,constKey&y) ( Key:comparisons+; returnx.the_key()y.the_key(); )一一 intKey:the_key()const (. returnkey;

28、 ) 四结果与分析 测试数据 测试数据为100个随机数，应该Random类，我们可以给表中赋随机数组，可以用于检验各种排序函数的性能。随机数可以在控制台上显示，便于观察。 例： 产生100个随机数： UnsortcdlistUnsortcdlist M M13?065561760224283875413?0655617602242838754整66074612?552264561?378491188881444?321239575166074612?552264561?378491188881444?321239575192S92S2456096283474768?99862456096283

29、474768?99861B11B17?37?3S41S415935208932705935208932706ME236ME231098942259810989422598979782119333167919479166148781821193331679194791661487818 83S3S33&156451615417804718687711718233&156451615417804718687711718224y24y5196549372?56475?375196549372?56475?3703136127&0693096644403136127&0

30、69309664449 9S943RS943R823758998237589943g43g9634232843896342328438。456999470324344439113456999470324344439113 测试结果 nsertionSortTintei0seconds.nsertionSortTintei0seconds. onparisonsonparisons：25952595 占wWgnmentwWgnment等二268268初 electionSortTimeelectionSortTime：0seconds.0seconds. ：onparisonsonparison

31、s：49504950 ssi9nmentsssi9nments：297297 She11SShe11SortIime=0secondsortIime=0seconds ConparisonsConparisons：790790 AssignmentsAssignments- -807807 QuickSoi*tTineQuickSoi*tTine：dsecondsdseconds ComparisonsComparisons：5858月 AcsignittentsAcsignittents：13381338 HeapSortTimeHeapSortTime: :0seconds0seconds

32、 ConpapisonsConpapisons：工日5 50 0 RsignmenRsignmen七s=B39s=B39 InsertionSortwithbianrysearchTimeInsertionSortwithbianrysearchTime：0seconds.jompairisons0seconds.jompairisonst t618tssignments618tssignments：27072707 ScanSortTineScanSortTine：0sec0secondsonds ComparisonsComparisons：50915091 AssignmentsAssi

33、gnments：74887488 BubbleSortTimeBubbleSortTime：&seconds&seconds ompaiompai自onsons：4?504?50 ssi9nmentsssi9nments：74887488 rlersfeSortIrlersfeSortITIDETIDE：0seconds0seconds ComparisonsComparisons：S42S42 AssignmentsAssignments：13441344 排序后表中数据为:目101115476732899710?101115476732899710? 113113 1171

34、27136117127136 14414414fi14fi 161161 166166 18181S21S2 18G18G 193193 2 2Q Q24224524927028429529242245249270284295295 5 324324 331331344347344347 3733733?S3?S 378378 380380 395395 422422 423423 43M43M 4 43 304394444564614704734760439444456461470473476 479479 491506519491506519 528522528522 S23S23 541

35、541 573573 593593 598598 E02E02 6 6E E660?609617617628645645660?609617617628645645 647647 654655686654655686 7B37B3751751 754754 773773 780780 781781 821821 S36S36 8 83 38838877888388778出出093899899093899899 910910 92A92A93093?93093? 956959956959 9696的 963963 986986 999999 结论分析 按平均时间将排序分为四类： (1)平方阶(O

36、(n2)排序 一般称为简单排序，例如直接插入、直接选择和冒泡排序； (2)线性对数阶(O(nlgn)排序 如快速、堆和归并排序； (3)O(n1+)阶排序 是介于0和1之间的常数，即01,如希尔排序； (4)线性阶(O(n)排序 如基数排序。 各种排序方法比较 简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。 影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应 综合考虑下列因素： 待排序的记录数目n； 记录的大小(规模)； 关键字的结构及其初始状态； 对稳定性的要求； 语言工具的条件； 存储结构； 时间和辅助空间复杂度等。 不同条件下，排序方法