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

實 驗 報 告（ 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é)號B學(xué)院(系) 管理學(xué)院專 業(yè)信息管理與信息系統(tǒng) 實習(xí)題名:內(nèi)排序算法的實現(xiàn)及性能比較班級 B 姓名 耿宙 學(xué)號 B 日期2016.05.26 一、 問題描述驗證教材的各種內(nèi)排序算法，分析各種排序算法的時間復(fù)雜度；改進教材中的快速排序算法，使得當(dāng)子集合小于10個元素師改用直接插入排序；使用隨即數(shù)發(fā)生器產(chǎn)生大數(shù)據(jù)集合，運行上述各排序算法，使用系統(tǒng)時鐘測量各算法所需的實際時間，并進行比較。系統(tǒng)時鐘包含在頭文件“time.h”中。二、 概要設(shè)計文件Sort.cpp中包括了簡單選擇排序SelectSort()，直接插入排序InsertSort()，冒泡排序BubbleSort()，兩路合并排序Merge()，快速排序QuickSort()以及改進的快速排序GQuickSort()六個內(nèi)排序算法函數(shù)。主主函數(shù)main的代碼如下圖所示：三、 詳細(xì)設(shè)計1. 類和類的層次設(shè)計在此次程序的設(shè)計中沒有進行類的定義。程序的主要設(shè)計是使用各種內(nèi)排序算法對隨機生成的數(shù)列進行排列，并進行性能的比較，除此之外還對快速排序進行了改進。下圖為主函數(shù)main的流程圖：main()2. 核心算法1) 簡單選擇排序：簡單選擇排序的基本思想是：第1趟，在待排序記錄r1rn中選出最小的記錄，將它與r1交換；第2趟，在待排序記錄r2rn中選出最小的記錄，將它與r2交換；以此類推，第i趟在待排序記錄rirn中選出最小的記錄，將它與ri交換，使有序序列不斷增長直到全部排序完畢。2) 直接插入排序：插入排序的思想是將一組無序的元素分別插入一個已經(jīng)有序的的數(shù)組里，并保證插入后的數(shù)組也是有序的。當(dāng)所有無序組的元素都插入完畢時，一個有序數(shù)組構(gòu)造完成。數(shù)組n1r為初始的一個無序數(shù)組（為了直觀起見，我們這里設(shè)定數(shù)組從1開始，而不是0），則n1默認(rèn)為只有一個元素的有序數(shù)組，n2插入只有n1構(gòu)成的有序數(shù)組中，則此時有序數(shù)組的元素數(shù)量變?yōu)?。以此類推，到第i個元素時，前i-1個元素已經(jīng)是有序的，此時只需將第i個元素插入到有序數(shù)組中并使之保持有序。如此直至最后一個元素插入完畢，整個插入排序完成。3) 冒泡排序：冒泡排序每遍歷一次數(shù)組，便將最大的元素放到數(shù)組最后邊。下次遍歷將次大的元素放到數(shù)組倒數(shù)第二位，依次類推，直至將最小的元素放到最前邊，此時冒泡排序完成。4) 快速排序：快速排序是采用了分而治之的思想，但與合并排序有所不同的是快速排序先“工作”（這里是分割或partition），再遞歸。快速排序的主要思想是保證數(shù)組前半部分小于后半部分的元素，然后分別對前半部分和后半部分再分別進行排序，直至所有元素有序。5) 兩路合并排序兩路合并排序算法的基本思想是：將待排序元素平分成大小大致相同的兩個子序列，然后對每個子序列分別使用遞歸的方法進行兩路合并排序，直到子序列長度變?yōu)?，最后利用合并算法將得到的已排序好的兩個子序列合并成一個有序的序列。 兩路合并排序算法的核心部分是將子問題的解組合成原問題解得合并操作。常用的操作是新建一個序列，序列的大小等于要合并的兩個子序列的長度之和。比較兩個子序列中的最小值，輸出其中較小者到新建的序列中，重復(fù)此過程直到其中一個子序列為空。如果另一個子序列中還有元素未輸出，則將剩余元素依次輸出到新建序列中即可。最終得到一個有序序列。 此外還對快速排序進行了改進，改進算法流程圖如下所示：GQuickSort ()四、程序代碼templatevoid GQuickSort(T A,int n) /改進的快速排序GQSort(A,0,n-1);templatevoid GQSort(T A,int left,int right)int i,j;if(right=9)if(leftright)i=left;j=right+1;dodo i+;while (AiAleft);if(ij)Swap(Ai,Aj);while(ij);Swap(Aleft,Aj);QSort(A,left,j-1); QSort(A,j+1,right);elseInsertSort(A,right-left+1);return ;五、測試和調(diào)試1. 測試用例和結(jié)果測試結(jié)果如下圖1) 生成隨機數(shù)據(jù)2) 簡單選擇排序及其所需時間3) 直接插入排序及其所需時間4) 冒泡排序及其所需時間5) 快速排序及其所需時間6) 改進快速排序及其所需時間7) 兩路合并排序及其所需時間2. 結(jié)果分析簡單選擇排序的最好、最壞的平均情況的時間復(fù)雜度都為O(n2),是不穩(wěn)定的排序方法；直接插入排序的最好情況的時間復(fù)雜度為O(n)，最壞情況的時間復(fù)雜度為O(n2)；冒泡排序最好情況的時間復(fù)雜度為O(n)，最壞情況的時間復(fù)雜度為O(n2)，是穩(wěn)定的排序方法；快速排序最好情況的時間復(fù)雜度為O(n2)，最壞情況的時間復(fù)雜度為O(nlog2n)，是不穩(wěn)定的排序方法；兩路合并排序的時間復(fù)雜度為O(nlog2n)，是穩(wěn)定的排序方法。六、 實習(xí)小結(jié)在這次實驗中,我們對內(nèi)部排序算法進行了比較以及性能分析,通過這次實驗,我們加深了對內(nèi)部排序算法的理解,對內(nèi)部排序算法的基本運算的實現(xiàn)有所掌握,對課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進一步理解和掌握,學(xué)會了如何把學(xué)到的知識用于解決實際問題,鍛煉了自己動手的能力。通過這次實驗，我明白了，沒有總是最好的排序方法。對于一般列表，快速排序、希的性能較好。通過本次實驗，我深刻體會到問題解決方案的重要性，算法效率分析的必要性。法時。附錄：#include#include#includetemplatevoid Swap(T &a,T &b)T temp=a;a=b;b=temp;templatevoid SelectSort(T A,int n) /簡單選擇排序int small;for(int i=0;in-1;i+)small=i;for(int j=i+1;jn;j+)if(AjAsmall)small=j;Swap(Ai,Asmall);templatevoid InsertSort(T A,int n) /直接插入排序for(int i=1;i0&tempAj-1)Aj=Aj-1;j-;Aj=temp;templatevoid BubbleSort(T A,int n) /冒泡排序int i,j,last;i=n-1;while(i0)last=0;for(j=0;ji;j+)if(Aj+1Aj)Swap(Aj,Aj+1);last=j;i=last;templatevoid QuickSort(T A,int n) /快速排序QSort(A,0,n-1);templatevoid QSort(T A,int left,int right)int i,j;if(leftright)i=left;j=right+1;dodo i+;while (AiAleft);if(ij)Swap(Ai,Aj);while(ij);Swap(Aleft,Aj);QSort(A,left,j-1);QSort(A,j+1,right);templatevoid GQuickSort(T A,int n) /改進的快速排序GQSort(A,0,n-1);templatevoid GQSort(T A,int left,int right)int i,j;if(right=9)if(leftright)i=left;j=right+1;dodo i+;while (AiAleft);if(ij)Swap(Ai,Aj);while(ij);Swap(Aleft,Aj);QSort(A,left,j-1); QSort(A,j+1,right);elseInsertSort(A,right-left+1);return ;templatevoid Merge(T A,int i1,int j1,int i2,int j2) /兩路合并排序T* Temp=new Tj2-i1+1;int i=i1,j=i2,k=0;while(i=j1&j=j2)if(Ai=Aj)Tempk+=Ai+;else Tempk+=Aj+;while (i=j1)Tempk+=Ai+;while(j=j2)Tempk+=Aj+;for(i=0;ik;i+)Ai1+=Tempi;delete Temp;templatevoid MergeSort(T A,int n)int i1,j1,i2,j2;int size=1;while(sizen)i1=0;while(i1+sizen-1)j2=n-1;elsej2=i2+size-1;Merge(A,i1,j1,i2,j2);i1=j2+1;size*=2;int main()clock_t start,finish;srand(time(NULL); int n=1000;int *a=new intn;int *b=new intn;int *c=new intn;int *d=new intn;int *e=new intn;int *f=new intn;cout待排序序列為:endl;for(int i=0;in;i+)ai=rand()%91;coutai ;bi=ai;ci=ai;di=ai;ei=ai;fi=ai;coutendl;start=clock();SelectSort(a,n);cout經(jīng)過簡單選擇排序后的序列為:endl; for(i=0;in;i+)coutai ;coutendl;finish=clock();cout開始時間為:start結(jié)束時間為:finish 持續(xù)時間為:(double)(finish - start)/ CLOCKS_PER_SECendl;start=clock();InsertSort(b,n);cout經(jīng)過直接插入排序后的序列為:endl;for(i=0;in;i+)coutbi ;coutendl;finish=clock();cout開始時間為:start結(jié)束時間為:finish 持續(xù)時間為:(double)(finish - start)/ CLOCKS_PER_SECendl;start=clock();BubbleSort(c,n);cout經(jīng)過冒泡排序后的序列為:endl;for(i=0;in;i+)coutci ;coutendl;finish=clock();cout開始時間為:start結(jié)束時間為:finish 持續(xù)時間為:(double)(finish - start)/ CLOCKS_PER_SECendl;start=clock();QuickSort(d,n);cout經(jīng)過快速排序后的序列為:endl;for(i=0;in;i+)coutdi ;coutendl;finish=clock();cout開始時間為:start結(jié)束時間為:finish 持續(xù)時間為:(double)(finish - start)/ CLOCKS_PER_SECendl;start=clock();MergeSort(e,n);cout經(jīng)過兩路合并排序后的序列為:endl;for(i=0;in;i+)coutei ;coutendl;finish=clock();cout開始時間為:start結(jié)束時