各种内排序算法的实现及性能的比较

1、各种内排序算法的实现及性能的比较作者： 日期:实验报告（ 205 2016 学年 第 2 学期）课程名称实验名称实验时间指导单位指导教师数据结构 A各种内排序算法的实现及性能的比较016 年 6 月 20 日计算机科学与技术系骆健学生姓名学院（系）班级学号管理学院 专业 信息管理与信息系统问题陈述1）验证教材的各种内排序算法2）分析各种内排序算法的时间复杂度3）改进教材中的快速排序法，使得当子集和小于 1个元素时 改用直接插入排序4）使用随机数发生器产生大数据集合，运行上述 各排序算法， 使系统时钟测量个算法所需的实际时间 ,并进行比较。 系统时 钟包含在头文件“ tim .”中。二、概要设计

2、Mai cpp 调用 Menu. ,为主程序。 Men主菜单 le sor .h 简单选择排序In e t ort.h 直接插入排序Bubblesort.h 冒泡排序Quic sort.h 快速排序Mrge rt.h 合并排序三、详细设计 简单选择排序 :将初始序列 （ 0An-1）作为待排序序列 ,第一 趟在待排序序列 （A An-1）中找最小元素 ,与该序列中第一个元 素 A0交换，这样子序列 （A ）有序 ,下一趟排序在带牌子序列 （A1A-1）中进行。第 i 趟排序子序列 （ i-1An 1）中进行。 经过 n-1 趟排序后使得初始序列有序。程序流程图 : 直接插入排序 :一个元素插入

3、到有序表中，首先将其存入临时变 量 tep，然后从后往前查找插入位置。 当emp 小于表中元素时， 就将该元素后移一个位置， 继续比较、移动 ,直到 tem大于等于表 中元素或者到了有序表的第一个元素结束 ,这时就可将 te存入刚后移的元素的位置了程序流程图 : 冒泡排序 :第一趟在序列 （0An- ）中从前往后进行两个相 邻元素的比较 ,若后者小 ,则交换 , 比较 -1 次；第一趟排序结束，最 大元素被交换到 n-1中（即沉底 ）下一趟排序只需在子序列（ 0A-2）中进行 ;如果在某一趟排序中未进行交换元素 ,说明子序 列已经有序，则不再进行下一趟排序。程序流程图：Aj+Swap(Ai=

4、快速排序： 取第一个元素作为分割元素，初始化 l t,= ght+1,i 从左往右寻找第一个大于等于分割元素的元素 ,j 从右往 左找第一个小于等于分割元素的元素并交换 ,i和j 继续移动,重复上 述步骤,直到当 i时将 j 与第一个元素交换。程序流程图 :Swap(ASwap(Aleft,A 两路合并排序 :将有 n 个元素的序列看成是 n 个长度为 1 的有序 子序列,然后两两合并子序列， 得到n 个长度为 2或的有序 子序列, 再两两合并直到得到一个长度为 n 的有序序列时结束。程序流程图：四、程序代码sele t ort.h# lude / 简单选择排序 template oid el

5、et o t（ , int n）int s a l; o （int i=0; in ; i+） small=i； r（i t j=i+1;jn ； j+）if（A j mall） small=j; w （Ai ， A mall）;I srts hinclude / 直接插入排序template oid nsertSort （ T , in n）?for（in 1; &tempA -）?Aj=Aj-1 ； j-;?Aj=t mp；?* !* Bubblesort.h#include templa e void Bu b eSort（T A, in n） ? n ,j，l s； =n-1;wil(

6、i0)? t 0;?for（ j=0;ji;j+）? （Aj+1 A）?Swp（j，Aj+1） ；? las j;?i st;Q icksor .h#in l e / 改进的快速排序t mplateo quik（T , nt n） int a;int top= , i t， le t, ; anew ; if（=NU L） rtun; op+= ; top + =n 1;/ c?for（ =0;ale ?right=a ； ? if（ leftrig ? ?S）；!=NULL;j+）=a + ;t)? if（ ght- ef 15）I srt otEx（A，left,right） ； lse?

7、 ?a op + lef;?atp+=Quc rt（A,left, g ）； op+atop-2 +2;?atop+=ri ht;?mp a t in Quic S rt（ A， int left,int rig t） ?in i, ；?if（lef rght）?i left;j=r ght+;? d?do i+ ;while（A A lef ）;?if（ij）wp（Ai,j）；? while（ij ）;? ap（l t,j）;?retur j;?return 0;em latevoid InetSr（ T ，in left，it right ） for（int i=left+1 ； i0 &

8、 tempA j- ）?A j=Aj-1 ;j- ;?Aj=temp;? rg sort h # clude / 两路合并的 C+程序 template vid M ge（ A,int i1,int 1，in i2 ， int j2） T Tem=ew Tj2- 1+1； int i=i1 ， =i2, =； w ie（i=j1 j= ） ?if（Ai= ）Temp+=Ai+;? ele Tem + = j +; ?hle（j） mpk+= i+;whi e（ =j2）Te pk+=A j+ ； for（i=0;ik；i+）Ai1+=Tepi;?delete T mp;/ 合并排序的 C+程序

9、 templ te M gert（T ， it n） ?in i1 ， j1,i2,j2 ；in size 1;?whi （si en） 1=;?hil （i1+size -）?j2 n-;? ?el e 2=i2+siz -1; ? e ge（A,i1 ， j1,i2 ， ）;1= 1;? ize*=2;? u.h#include in lud incl de inc d #nc de elec sor . include i ert ot #inclu ubblesort.h #incl d quic sor #in de m gesort hde ine SIZE 40 # ine IM

10、ES 1 00 tem ate cass M u pu lic: id printme u();?vo sel sort() ； / 简单选择排序 ?vi inertSot();/ 直接插入排序 ?oid ubbleSort() ； / 冒泡排序oid qui Sor ();/ 快速排序void mreSor() ;/ 两路合并排序 void childmenu() ； / 子菜单 1 vid c i dme u2() ；/ 子菜单 ?vo d switc a() ;private:int ,b,c；;te p ate i Menu:pri mn () cout - 内排序测试系统 - - e

11、 l; t endl ndlen l;out1. 简单选择排序 en l;c t .直接插入排序 endl ； c u 3冒泡排序 ndl；?cout4. 快速排序 en l；?out 5.两路合并排序 end ;? out6.退出swt ha()；emplate vid Menu:chi m nu()cout - - - - - - - - - - e dl;?cout1 最好情况 en l;?ou 2.最坏情况 nl；? ut3. 平均情况 ndl；cout 4.返回主菜单 b;?if(b=4)t i -prin enu(); tmpate voi Me u :： childm n2()

12、?ou - - - - - - - ed ; ut1. 原始算法 end ; o 2.改进算法 en； cot3.返回主菜单 ;if( = 3)t is-p ntme u ()；temp te vi Mn :s cha()/ coutok ; swich(a)?case 1： this- elects rt() ； reak;/ok ?case 2: his-ins rSort()； break;/okcs 3: his u bl ort() ； r a； / ?ca 4:tis-qckSot();ea；/ kcase 5:tismerg rt();br a;/ ?c se 6:exi ( )

13、;b ak；?default:couterr rrntm u( );bre ;；te late oid print ut（T A， n n）/ 打印数组 ,测试时用for（int =0;i ;+）?coutA ;cou endl;templ te T rod ce te （ int x） /产生顺序，逆序，随机的数组 n i;T A T SIZE;? witch （ ）?case 1:?fr（i=0；i0;i）Ai-1=SZEi;rtur ；逆序?break;ca e 3: rand（time（N LL）;?for（i=0 ； ZE;i+）A= nd（） %1000+1; un A;/随机 ?

14、 rea;?eful:c ut or en ;return A; ek；templ voi w（ T a,T &b） /交换 2 个元素?T temp= ;a ;?=tm；t plte void Me :bu leSort（ ）?cou 冒泡排序 childme u（）;T *A; o b e duration ；?c ock_t tart,fin sh;?st rt=cl c （）；cout k ndl； r（int i=0； i IMES； i+）? ? A pr uc ate（b）；? bbl Sort（A,SI ）;? lete A；? nih=cl ck（）；?d ra on=（d

15、e）（ f nish- a t）/CLOC S PER SC；?/p intou （ ,SIE）； out用时： d at on b ble rt（ ）;?/*ok /templ t void nu： iner Sor （）?c t直接插入排序 c ildm nu（ ） ;T *A ； o b e r o；?/A= rod cedat（）;?/ f（ =NUL ）cout i sertSort（） ； ?/pr nto （ ,S ZE）；cloc _ st rt,finish;? a =clock（） ;?co t ke dl;?for（ nt =0;iTME; +）? =pro u edat

16、e（b）; In tSor （A,SIZE） ;? delete ;?finish= lo（ ）;?dura ion= （ ouble ） （ ini h-star ）/CLOCK _PE _SEC;?/ rintout（A,SIZ ）;cout 用时： du tio inse t ort（） ；t mpl te void en:： me eSo t（）?/ his-chldmenu(); cout 合并排序 endl; co 直接用随机数据测试 edl； * ;?d ub d atio ;? oc_ sar, ni h; ar =clo k(); cout ok nd ;?for(int i

17、=0; TIMES；i+)? =pro ucedate(3);M r ort(A ，SZ); ? lete ;?finish cloc ();?d ati n=( doub e)(fi i h-sta t) CLOCKS_PER SEC; /p nto t( ,S ZE);c u 用时 : duration p intm nu() ；/*o */ emplate void Me u:qui kSrt() in ； t, inis；?this-chi dmenu2(); T ； ouble ur c k_ sta?if(c=1) ? ? ut 原始快速排序 endl；? c ut直接用随机数据测

18、试 enl; ?start=cloc （）；? cout okndl;? for（ nt i0;iT ES;i +）?= oducedate（ ）;? u c（ A， ZE）;? dlete A;?f ish=cl c （）；?d tion= （ dou ） （fin sh-star ） CLCKS_P R SE；cout用时 : durati nquick rt();?e se if(c=2)?cou 改进的快速排序 endl;cout 直接用随机数据测试 ndl ；/* =produced ( 3); printout(A,S E);?quick (A,S E);?prino t(A,SIZ );delete ;?his-prt nu();?* A;?s art=coc ();c ut oke d；?fr(int i 0；iTIMS；i+)?A=producedate ();?quick(A,SIZE);dele e ;?fin s = ock();?du