南郵數(shù)據(jù)結(jié)構(gòu)上機實驗四內(nèi)排序算法的實現(xiàn)以及性能比較

1、 實驗報告 課程名稱 （2015/2016學(xué)年 第二學(xué)期） 數(shù)據(jù)結(jié)構(gòu)A 實驗名稱 內(nèi)排序算法的實現(xiàn)以及性能比較 實驗時間 2016 年 5 月 26 日 指導(dǎo)單位 計算機科學(xué)與技術(shù)系 指導(dǎo)教師 駱健 學(xué)生姓名 耿宙 班級學(xué)號 B14111615 學(xué)院係） 管理學(xué)院專 業(yè)信息管理與信息系統(tǒng) 2 卅 E貝U )2 Ht afUtil0- nF* * 實習(xí)題名：內(nèi)排序算法的實現(xiàn)及性能比較 班級B141116姓名 耿宙 學(xué)號 B14111615 日期2016. 05. 26 問題描述 驗證教材的齊種內(nèi)排序算法，分析齊種排序算法的時間復(fù)雜度；改進教材中的快速 排序算法，使得當子集合小于10個元素師改用宜

2、接插入排序；使用隨即數(shù)發(fā)生器產(chǎn)生 大數(shù)拯集合，運行上述齊排序算法，使用系統(tǒng)時鐘測量各算法所需的實際時間，并進行 比較。系統(tǒng)時鐘包含在頭文件“time.h中。 概要設(shè)計 文件Sgt. cpp中包括了簡單選擇排序SelectSort 0 直接插入排序InsertSort () 冒泡排序BubbleSort ()兩路合并排序Merge()快速排序Quicksort ()以及改進的快 速排序GQuickSortO六個內(nèi)排序算法函數(shù)。主主函數(shù)main的代碼如下圖所示: Ul vM| t WB I h III Utinh uMnh tl|Ah HMOk 爼I:肚 I 負-vis f toy b 祁協(xié)F B

3、H心“ 0 詳細設(shè)計 1. 類和類的層次設(shè)計 在此次程序的設(shè)訃中沒有進行類的定義。程序的主要設(shè)訃是使用齊種內(nèi)排序算法對隨機 生成的數(shù)列進行排列，并進行性能的比較除此之外還對快速排序進行了改進。下圖為主函 數(shù)main的流程圖: 歡迎下載 I c bck.zarcfwuUi; c 2utgiy ： i卄 C6Ut-*ndl; S * rturaO; mainO 2. 核心算法 1）簡單選擇排序: 簡單選擇排序的基本思想是：第1趟，在待排序記錄r1-rn沖選出垠小的記錄，將它與 r交換；第2趟，在待排序記錄r2l-rn沖選出最小的記錄，將它與交換：以此類推, 第i趟在待排序記錄riHrn中選出最小的

4、記錄，將它與ri交換，使有序序列不斷增長直到 全部排序完畢。 2）直接插入排序: 插入排序的思想是將組無序的元素分別插入一個已經(jīng)有序的的數(shù)組里.并保證插入后的數(shù)組 也是有序的。當所有無序組的元素都插入完畢時，一個有序數(shù)組構(gòu)造完成。數(shù)組nl-r為初 始的一個無序數(shù)組（為了直觀起見，我們這里設(shè)定數(shù)組從1開始，而不是0）,則nl默認為 只有一個元素的有序數(shù)組，n2插入只有nl構(gòu)成的有序數(shù)組中，則此時有序數(shù)組的元素數(shù)量 變?yōu)?。以此類推，到第1個元素時，前個元素己經(jīng)是有序的，此時只需將第1個元素插 入到有序數(shù)組中并使之保持有序。如此宜至最后一個元素插入完畢，整個插入拙序完成。 3冒泡排序: 冒泡排序每

5、遍歷一次數(shù)組，便將最大的元素放到數(shù)組最后邊。下次遍歷將次人的元素放到數(shù)組 倒數(shù)第二位，依次類推，直至將最小的元素放到最前邊，此時冒泡拙序完成。 4）快速排序: 快速扌4序是采用了分而治之的思想.但與合并排序有所不同的是快速排序先“工作”（這里是 分割或partition）,再遞歸?？焖倥判虻闹饕枷胧潜ＷC數(shù)組前半部分小于后半部分的元素, 然后分別對前半部分和后半部分再分別進行排序.直至所有元素有序。 5）兩路合并排序 兩路合并排序算法的基本思想是：將待扌舊芋元素平分成大小人致相同的兩個了序列，然后對每 個子序列分別使用遞歸的方法進行兩路合并排序.直到了序列長度變?yōu)?，最后利用合并算法 將得到的

6、己拙序好的兩個了序列合并成個有序的序列。兩路介井排序算法的核心部分是將子 問題的解組合成原問題解得合并操作。常用的操作是新建個序列序列的大小等于耍合并的 兩個子序列的長度之和。比較兩個了序列中的最小值，輸出其中較小者到新建的序列中.重復(fù) 此過程宜到其中一個了序列為空。如果另一個了序列中還有元素未輸出，則將剩余元素依次輸 出到新建序列中即可.最終得到一個有序序列。 此外還對快速排序進行了改進，改進算法流程圖如下所示: GQuickSort () 四. 程序代碼 改進的快速排序 icmp late void GQuickSort(T A(ljni n) GQSort(AAn-l): icmp la

7、te void GQSorl(T Ajnt leftJnt right) int ij; if(right=9) j=right+l; do do i+;while (A(il6 52 *7 k 27 *2 29 / 69 創(chuàng) 29 27 K 84 * 兀 76 tt 71 73 23 F 44 22 M 26 49 6S 鈿 frt 73 S 76 K 04 22 41 W 12 21 4 21 宀 M 4 n n 41 M K(1 70 Gi 2 39 M n 32 u Gt I? $ tt n u 也)i i 73 Td 17 il 60 23 Z1 K V? IT 54 i3 191

8、$5 1 M SB U 31 i $2 1167*9319g717 Id 79 M 51 1) 64 S 3S 414S92? *4 I l M30m54614764$ 64 , 9 a 76 2$ 69 3 7B*7ttd7t :f M 34 H 32 74 74 4* 1 M 79 37 f ZS It 65 tS 76 (4 8V 3 ；M 33028075)“64鉛 29 74 71 4 64 616421S)7S a=b; b=teinp; icmp laie void SelectSort(T Aunt n) 簡單選擇排序 int small; for(int i=O:ifAljA

9、smaIl) small: Swap(A(i,A(smalll): icmp laie void InsertSortd AJnt n)/宜接插入排序 for(int i=l:i0 while(i0) lasl=0: for(j=0:ji:j+) if(AU+nAU) Swap(Arjl，A|j+lJ): lasi=j: i=Iast; icmp lale void QuickSortd Aunt n)快速排序 QSort(AAn-l); templaie void QSort(T A(jni leftjnt right) int i j: ifleftAEIeft): Swap(A(i,A|

10、j); while(ij): Swap(Alefl.Ajl); QSort(AJeftJ-l): QSort( A j+bright)： icmp laie void GQuickSorUT Ajnt n) 改進的快速排序 GQSort(A.O.n-l); icmp laie void GQSorifT Aunt lefldnt right) int i j; if(righl=9) i=left: j=righl+l; do do i+;while (AiAleft): if(ij) Swap(A(iJ,A|j3): while(ij): Swap(A|lefl,Atj)； QSort(AJ

11、eftJ-l): QSort( A j+bright)： else InsertSort(Ajight-left+1); return; icmp lale void MergefT AEJjnt i bint j I ant i2.ini j2)兩路合并排序 T* Temp=new Tfj2-i 1+1： int i=il J=i2.k=O: while(i=j 1 else Tempk+=Aj+; while (i=jl ) Tempk 卄=Ai 卄; while(j=j2) Tempk 卄=Aj +; for(i=0：ik:i+) Ail+=Tempil； de 一 etc 二 Temp

12、- -emp 蟲 CAC-ass TV woid Mcrgcsort(T Asm n) int 二 JLi2J2- iiU size= wh=c(sizcAn) ig whi一c (二+sizc:n) i2il+siza j正2三 if(i2+sizclvni T- C 一 SC j2Hi2+sizc一八 Mcrgc(A二 Ji2j2= 二 Hj2 二 J sizcf 2- c 一 ocks 一 art. finish 八 srand(=mc(NULL)r in【3H3S- iiU *aHncw in二nK in【*b=newm二nk in【薛new亙nk iiu *dHnewm二nk iiU

13、 *CHncw in二n一八 ini *fHncw in二nk colkaq崙辛豪弔空訝.AACndr for(in 二=oxcn=+) coluAAa 三八d, b三盤三 c三點m d三點m Nv”持續(xù)時間 Nv”持續(xù)時間 coutendl: siart=clock(); SeleclSort(a.n): cout經(jīng)過簡單選擇排序后的序列為:endl; fori=0:in:i+) coutai ”； coutendl: finish=clock(); couivv”開始時間為:“vvslartvv “vv”結(jié)束時間為:finish* 為:(double)(finish start)/ CLO

14、CKS_PER_SECendl; siart=clock(); InsertSort(b.n)： coiK”經(jīng)過直接插入排序后的序列為:endl; for(i=0;in:i+) coutbfij couivvcndl: finish=clock(); couivv”開始時間為:“vvsiartvv “vv“結(jié)朿時間為:“vvfinishvT 為:(double)(finish - start)/ CLOCKS_PER_SECendl; siart=clock(); BubblcSort(cm); cout經(jīng)過冒泡排序后的序列為:cndl; for(i=0：in:i+) coutci ”； co

15、utendl: finish=clock(); couivv”開始時間為:“vvsiartvv “vv“結(jié)朿時間為:“vvCinishvv“ 為:(double)(finish - start)/ CLOCKS_PER_SECendl; siart=clock(); QuickSortdn); cout過快速排序后的序列為:cndl; for(i=0：in:i+) coutd(i ”； coutendl: finish=clock(): couivv”開始時間為:“vvslartvv “vv”結(jié)束時間為:finish* 為:(double)(finish start)/ CLOCKS_PER_SECendl; siart=clock(); MergeSort(e.n); cout經(jīng)過兩路合并排序后的序列為:endl; for(i=0;in:i+) coutei ”； couivvcndl: finish=clock(); couivv”開始時間為:“vvsiartvv “VV”結(jié)朿時間為:“vvfinishvv“持續(xù)時間 為:(double)(finish - st