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

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

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

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

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

5、 S ele c t S o r t(T A , intn)int sm a 1 l;f o r (int i=0; in 1 ;i+) small=i ；fo r(i n t j=i+1;jn ; j+)if(A j A s mall) small=j;S w ap (Ai, A s mall);I n se rtsort. h# include /直接插入排序template v oid I nsertSort (T A , in t n)?for(in t i = 1; i 0 & &temp templa t e void Bu b b 1 eSort(T A, in t n) ?i

6、n t i ,j, l a s t;i =n-1;w h il e (i0) ?las t = 0;?for (j=0;j/改进的快速排序t e mplatev o id qui c k (TA , i nt n)int * a;int top= 0 , r igh t, le f t, j ;a= new int n;if( a = NU L L) re tu r n;a t op+= 0 ;a top + + =n 1;/ /1 c!=NULL;j+ +)?for( j =0;a : j=a :j +;le ft?right=a j :;? if (leftrig?S);? if (ri

7、ght- 1 ef t 15)I n se rt S o r tEx t (A, left,right);e lse? ?a t op+ + = lef t ;?at o p+=Qu i c kSo rt(A,left, ri ght ) 1; a t op+ += atop-2 +2;?atop+=ri g ht;?t emp 1 a te in t Quick So rt( T A, int left,int rig h t) ?in t i, j ;?if(lef t r i ght) ?i = left;j=r i ght+ 1 ;? do?do i+ ;while(A i A : l

8、ef t); ?if(ij) S w a p(Ai, A j);? while(ivoid In s e r tSo r tExt( T A , in t left, i n t right)for(int i=left+1 ; i0 & tempA j-1 ) ?A : j=Aj-1 : ;j;? Aj=temp;?Me rge sort. h# in clude /两路合并的C+程序template v o id M er ge(T A,i nti1,i ntj 1, in t i2 , int j2)T * Temp = n ew Tj2- i 1+1;int i=i1 , j =i2,

9、 k = 0;w h i 1 e (i=j1 & & j= j 2 )?if(Ai= Aj )Temp k +=Ai+;? el s e Temp k + =A j + +;? w h i le( i = j 1 ) Te mpk+= A i+;whi 1 e( jv =j2)Tem pk+=A j+;for(i=0;ik ; i+) Ai1+=Tem pi;?delete T e mp;/合并排序的C+程序templ a te void M er geSo rt (T A , i n t n)?in t i1 , j1,i2,j2 ;in t size= 1;?whi 1e (si z e

10、n -1 )?j2 = n-1 ;? ?el s e j 2=i2+size -1;?M e r ge(A,i1 , j1,i2 , j2 );i 仁 j2+ 1;? s ize*=2;?Mea u.h#in elude in c lud e v std io .hincl u de inc lu d e i n c lu de s elec t sor t . hHin cludei ns ert s o r t. h #in clu de b ubblesort.h#incl u d e quic k sor t.h #i n clu de m er gesort. h# de f ine

11、 SIZE 400#def ine T IMES 1 0 00tem pl ate vc la s s Tc l ass Men upu b lic:vo id printme n u();?vo id sel ect sort() ;/ / 简单选择排序 ?vo i d in s ertSo r t() ;/ /直接插入排序 ? v oid b ubbleSort(); / 冒泡排序v oid qui ck Sor t ();/ /快速排序void m e r g eSor t () ;/两路合并排序 void childmenu() ； / 子菜单 1 vo id c h i l dme

12、n u2(); / 子菜单 2 ?vo i d switc h a();private:int a ,b,c；;tem p l ate vo i d Menu:pri nt m e n u () cout内排序测试系统v end l;cou t v v endl vve ndlen d l;c out1.简单选择排序 v en d l;cou t 2 .直接插入排序v endl;co u t v 3 .冒泡排序 ve ndl;?cout4.快速排序v en d l;? c out v 5.两路合并排序e ndl ;? c out6.退出v sw i t c ha ();t emplate v

13、o id Menu:chi ld m e nu()cout - - - - e ndl;?cout1 .最好情况en d l;? c ou t 2.最坏情况 e n d l;? co ut3.平均情况 e ndl;cout 4.返回主菜单b;?if(b=4)t h i s -prin tm enu();t e mp l ate v c l a s s Tvoi d Me n u vT: childm e nu 2()? c ou tv e n d l co ut1.原始算法e nd l ;c out 2.改进算法 v en dl;co u t 3.返回主菜单c ;if( c = 3)t h i

14、s-p ri ntme n u ();temp la te v o i d M e n u :s wit cha()/coutok a ;swi t ch(a)?case 1: this- s elects o rt(); b reak;/ok?case 2: t his-ins e r t Sort(); break;/okca se 3: t his b u b bl eS ort() ; b r e a k; / ok?ca se 4:t h is- q ui ckSo r t() ; br eak; / o kcase 5:th is merg eSo rt();br e a k ;/

15、 ok?ca se 6:exi t (1 );b re ak;?default:couterr o r p r i ntm en u ();bre ak ;temp late v oid print o ut(T A, i n t n) / /打印数组，测试时用for(int i =0;i n ; i +)?coutA i ”；cou t T *p rod u ce da te (int x)/ /产生顺序，逆序，随机的数组i nt i;T * A=new T : SIZE;? s witch (x )?case 1:?f o r(i=0 ; i 0;i - )Ai-1=Sl ZEi;r e

16、tur n A;/逆序?break;ca s e 3: s rand(time(N U LL);?for(i=0 ; i SI ZE;i+) A i = ra nd () %1000+1; ret u r nA;/随机 ? b rea k ;? d ef a ul t :co uterr or v en dl ;return A; br e a k;templ ate voi d S w ap( T & a,T &b)/ 交换 2 个元素?T temp= a ;a=b ;? b =t e m p;t em pl a te void Me nu :bu bb leSort()?cou tv 冒泡

17、排序 childme n u();T *A;d o u b 1 e duration ;?c 1 ock_t s tart,fin i sh;?st a rt=cl o c k ();cout o k e ndl;fo r(int i=0; i(b);? Bu bbl e Sort(A,SIZE );? de lete A;?fi ni s h=cl o ck ();?d u ra ti on=(d oubl e) (f i n ish- st a r t)/CLOCK S_PERCSE C;?/p r intou t (A ,SIZ E);c out 用时：b ub ble So rt()

18、;?/*ok * /templ a t e void Me nu：: in s er t Sort ()?cou t v 直接插入排序 c h ildm e nu();T *A;d o u b l e du r ati o n;?/A= p rod u cedat e (b );? / / i f (A =NULL )cout v i n sertSort(); ?/pr i nto ut (A ,SI ZE);clock _ t st a rt,finish;? st a rt =clock();?cou t v o ke n dl;?for( i nt i =0;i(b);In ser t

19、Sor t (A,SIZE ;? delete A ;?finish= c lo ck();?dura t ion= (d ouble) ( f ini s h-star t )/CLOCKS _PER _SEC;?/ p rintout(A,SIZ E );cout v 用时：du ra tio n inse r t S ort();t e mpl a te void Men uv T: me rg eSor t ()?/ t his- ch i Idmenu(); cout合并排序vv endl;co ut v 直接用随机数据测试e n dl;T * A ;?d o ub le dur a

20、tio n ;? cl ock _ t s t ar t , fi ni s h;st ar t =clo c k();coutvv ok e nd l ;?for(int i=0; iv TIMES; i+ )? A =pro d ucedate(3);M e rgeS ort(A , SI ZE );?de lete A ;?finish = clock ();?d ur ati o n= (doub l e)(fi n i s h-sta r t) /CLOCKS_PERSEC;p ri nto u t( A ,SI ZE);co u t 用时：duration p r intm e n

21、u();/*o k */t emplate vcl ass Tvoid Me n u vT :qui c kSo rt()?this-chi l dmenu2();T *A;t i o n ; r t, f in is h;d ouble d ur ac loc k_ t sta?if(c= 1)? ? co ut原始快速排序v endl;? co ut直接用随机数据测试vend l;?start=cloc k ();?cout v ok e ndl;? for (i nt i = 0;iT IM ES;i+ +)? A = pr oducedate (3 );? q u i ck( A,SI

22、 ZE);? de lete A;?f in ish=cl o ck ();?d ura tion= (dou ble) (fin i sh-star t )/ CLO CKS_FE R_SEC;cout 用时： quick So rt();?e 1 se if(c=2)?cou tv 改进的快速排序e ndl;cout v 直接用随机数据测试 ve ndl;/* A =produced ate (3);printout(A,S IZ E);?quick (A,S IZ E);?prin t o u t(A,SIZE );delete A ;? t his- pr in t me n u();

23、?* /T* A;?s t art=c 1 ock ();co ut v oke n d 1;?fo r(int i = 0; iTIM E S; i+ + )?A=producedate (3 );?quick(A,SIZE);dele t e A ;?fin i sh =c1 ock();?du r atio n =(do u ble) (f in ish star t) / C LO CKS_PE R_SECc o u t v 用时： d ur a t i o*qui c kSor t();?e 1 seco u terror v p rint m enu();tem p late vc la s s Tvo id M e n u:： sele cts o rt()/t h is-ch ildme n u();cou tvv 简单选择排序 e nd 1 ;? c out v 直接用随机数据测试endl;?T *A;do ubl e du r ati on ;clock_t star t , f in i sh;sta r t= c1 ock();c out ok v vend 1 ;?fo r (int i= 0; i T IMES;