試驗7：內(nèi)部排序算法比較

1、實驗7:內(nèi)部排序算法比較一、問題描述程序?qū)σ韵?種內(nèi)部排序（冒泡排序、直接插入排序、簡單選擇排序、快速排 序）算法進行實測比較，測試各種算法在對同樣的數(shù)據(jù)排序時的比較次數(shù)和移動次 數(shù)。二、輸入與輸出輸入：根據(jù)用戶需要輸入待排表的表長（100至1000）和不同測試數(shù)據(jù)的組數(shù) （8至18）,不輸入則按照默認(rèn)值進行測試輸出：每次測試完畢，列表顯示各種比較指標(biāo)值：比較次數(shù)和移動次數(shù) 二、需求分析.本演示程序?qū)σ韵?種常見的內(nèi)部排序算法進行實測比較：冒泡排序、直接插入 排序、簡單選擇排序、快速排序.待排序表的元素的關(guān)鍵字為整數(shù)。用正序、逆序和不同亂序程度的不同數(shù)據(jù)做測 試比較。比較的指標(biāo)為由關(guān)鍵字參加的

2、比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換計為3次移動）.演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上菜單，根據(jù)用戶需 要輸入待排表的表長（100至1000）和不同測試數(shù)據(jù)的組數(shù)（8至18）, 不輸入則按照默認(rèn)值進行測試。四、開發(fā)工具與環(huán)境硬件設(shè)備：微型計算機系統(tǒng)軟件環(huán)境：操作系統(tǒng) Windows,開發(fā)工具Devc+五、功能分析存儲結(jié)構(gòu)typedef int Typekey;typedef struct Typekey key;Type;typedef struct Type rMAXSIZE+1;/ 順序表int length;PList;/排序表函數(shù)一覽表int OneTimeSqC

3、reate(PList &L)/*手動輸入創(chuàng)建排序序列函數(shù)*/int ManyTimeSqCreate(PList &L,int m)/*自動生成排序序列函數(shù) */void BubbleSort(PList &L)/*冒泡排序*/void InsertSort(PList &L)/*插入排序*/void SelectSort(PList &L)/*簡單選擇排序*/int Partition(PList &L,int l ow,int high)/* 一次快速排序*/void QSort(PList &L,int l ow,int high)/*遞歸形式的快速排序算法*/ void QuickS

4、ort(PList &L)/*快速排序*/六、程序代碼#include #include #include #include #define MAXSIZE 10000 using namespace std; typedef int Typekey;/關(guān)鍵字的比較次數(shù)/關(guān)鍵字的移動次數(shù)int compCount;int shiftCount;typedef struct Typekey key;Type;typedef struct Type rMAXSIZE+1;/ 順序表 int length;PList;/排序表int OneTimeSqCreate(PList &L)/手動輸入創(chuàng)建排

5、序序列函數(shù)int x,h;for ( x=1; 1; x+)cinh;L.rx.key=h ;if(getchar()=n)/只讀入一行，換行則終止break;L.length=x;int ManyTimeSqCreate(PList &L,int m)/自動生成排序序列函數(shù)L.length=m;for (int x=1; x=m; x+)L.rx.key= rand() % m;/隨機數(shù)的取值范圍為0kreturn 1;void BubbleSort(PList &L) /冒泡排序int i,j,l,m=0,n=0;for(i=1;i=L.length-1;+i)/只需要比較 length-

6、1 次for(j=1;jL.rj+1.key)l=L.rj.key;L.rj.key=L.rj+1.key;L.rj+1.key=l;n+=3;/關(guān)鍵字移動次數(shù) coutendl冒泡排序：；cout比較次數(shù)：m;cout交換次數(shù)：nendl;void InsertSort(PList &L)/插入排序int i,j,m=0,n=0;/m是比較次數(shù)，n是交換次數(shù)coutendl;for(i=2;i=L.length;+i)if(L.ri.keyL.ri-1.key)+m;/比較次數(shù)加1n+=3;/移動次數(shù)加3 ,按實驗報告要求一次交換代表3次移動L.r0=L.ri;/設(shè)置哨兵L.ri=L.ri-

7、1;/后移一位for(j=i-2;L.r0.keyL.rj.key;-j)/ 一直找到該插入的位置 ( +m;/ L.rj+1=L.rj;/后移元素L.rj+1=L.r0;/將哨兵也就是原來的Li插入序列 cout直接插入排序：；cout比較次數(shù)：m;cout交換次數(shù)：nendl; void SelectSort(PList &L) / 簡單選擇排序int l,i,j,m=0,n=0;/m是比較次數(shù)，n是移動次數(shù)coutendl;for(i=1;iL.length;+i)L.r0=L.ri;j=i+1;/從j開始尋找最小元素 l=i;/l是最小元素的位置 for(j;jL.rj.key)/ 表

8、明 j 處 key 值更小 l=j;/記錄下j的值 L.r0=L.rj; if(l!=i)/需要交換位置n+=3;/移動次數(shù)加3 ,按實驗報告要求一次交換代表3次移動L.rl=L.ri;L.ri=L.r0;cout簡單選擇排序：；cout比較次數(shù)：m;cout交換次數(shù)：nendlendl;int Partition(PList &L,int l ow,int high)/一次快速排序int pivotkey;/ 中間軸L.r0=L.rl ow;/ 記錄軸元素pivotkey=L.rl ow.key;/ 軸取 low while(l owhigh)while(l ow=pivotkey) +co

9、mpCount; 比較次數(shù)加1 -high;/high 左移shiftCount+=3;/移動次數(shù)加3 ,按實驗報告要求一次交換代表3次移動L.rlow=L.rhigh;/此時應(yīng)當(dāng)交換位置while(l owhigh&L.rl ow.key=pivotkey)+compCount;/比較次數(shù)加1 +low;shiftCount+=3;移動次數(shù)加3 ,按實驗報告要求一次交換代表3次移動L.rhigh=L.rl ow;L.rl ow=L.r0;/找到位置插入軸元素return l ow;/返回位置void QSort(PList &L,int l ow,int high)/ 遞歸形式的快速排序算法

10、int Piv;/軸元素位置if(l owhigh)Piv=Partition(L,l ow,high);QSort(L,l ow,Piv-1);/ 左遞歸QSort(L,Piv+1,high);/ 右遞歸void QuickSort(PList &L)/快速排序int i;QSort(L,1,L.length);cout 快速辯序：；cout比較次數(shù)：compCount;cout交換次數(shù)：shiftCountendlendl;compCount=0;shiftCount=0;int main()int i,k,h,n,m;PList L,alist,blist,clist,dlist;cou

11、t排序模式選擇 endl;couth;if(h=1)/手動輸入模式OneTimeSqCreate(L);alist=blist=clist=dlist=L;BubbleSort(L);InsertSort(alist);SelectSort(blist);QuickSort(clist);cout排序后序列：;for(i=1;i=L.length;i+)cout L.ri.key;else/自動生成模式coutnm;k=1;while(k+=n)coutendl第k-1次排序endl;ManyTimeSqCreate(L,m);alist=blist=clist=dlist=L;BubbleS

12、ort(L);InsertSort(alist);SelectSort(blist);QuickSort(clist);return 0;七、運行測試1、手動輸入遞增序列1 2 3 4 5 6 7 8 9S3C:Usersapple-pcDesktopzhr_test.exe二34H磊晶瞿而耍震睛星麗而切一 123456789冒泡排序二比較次數(shù)門6交換次數(shù)二E直接插入排序二比較次數(shù)蹲 交換次數(shù)簡單選擇排序,比較次數(shù)二6交換次數(shù)快速排序，比較次如6交換我數(shù)川排序后序列；123456789Process exited after 10.11 seconds with return ualue 0請

13、按任意鍵繼續(xù).-.1、手動輸入遞減序列9 8 7 6 5 4 3 2 1C:Usersapple-pcDesktopzhr,test.exe【苴蔽羸嘉易誓原穎一987654321冒泡排序;比較次數(shù)交換次數(shù)江刖 直接插入排序:比較次數(shù)66交換次數(shù)：24 簡單選擇排序:比較次數(shù)=36交換次數(shù)：12 快速排序:比較次數(shù)交換次數(shù):48排序后序列1123456789Process exited after 9 _704 seconds uith return value 0請按任意鍵繼續(xù).3.生成隨機序列8組，每一個測試序列的表長度為100 得到測試結(jié)果如下表所示組數(shù)1234排序算法比較次數(shù)交換次數(shù)比較

14、次數(shù)交換次數(shù)比較次數(shù)交換次數(shù)比較次數(shù)交換次數(shù)冒泡排序49507827495076234950693049507407直接插入排序2609273254127623102702469285簡單選擇排序4950282495028249502854950291快速排序587984660948669930675930組數(shù)5678排序算法比較次數(shù)交換次數(shù)比較次數(shù)交換次數(shù)比較次數(shù)交換次數(shù)比較次數(shù)交換次數(shù)冒泡排序49507467495066544950719449507479直接插入排序2489291221827923982882493285簡單選擇排序4950273495027349502854950273

15、快速排序596924623918630978677954可以得到4種排序算法的平均比較和移動次數(shù)如下表排序算法平均比較次數(shù)關(guān)鍵字平均移動次數(shù)冒泡排序49507216直接插入排序2398282簡單選擇排序4950279快速排序633936可以看出快速排序的平均比較次數(shù)最少，而直接插入排序和簡單選擇排序的平均移動次數(shù)最少，綜合看來對于一般的無序序列，快速排序是這4種算法里面性能最優(yōu)的一種。C:Usersap pie- pcDes ktc ,C:Use rsa pple- pcDeskti二排序模再固擇一 騰懿I熱!:號需你生成5在排序一冒泡排序工比較次數(shù)7%日交換次數(shù)，曲7冒泡排序；比較次教”9函

16、交換次數(shù)直接插入排序:百次數(shù)二班制交揀次數(shù)嚙73 簡單選擇排序;比較次數(shù):皿0交換次數(shù),加2 快速排序上比較次數(shù)需87交換次數(shù)門84直援插入排序工比較欣數(shù); 2489交換吠數(shù)/久 簡單選擇排序:比較次數(shù)二4鷗3交換次數(shù)式73 快速排序;比較次數(shù)活6交換次數(shù):924第a次排序昌泡排序：比較次數(shù)：呼513交換次數(shù)/623第G次排序冒泡排序;比較次數(shù)：49/交換次數(shù)直接插入排序:比較次數(shù)姿ZLH交換欽敵花內(nèi)簡單選擇排序:比較就數(shù)二皿5。交換詼:數(shù)二”3直接插入排序:次敝二弱也交換我數(shù)47G簡單選擇排序:比較次數(shù):陰S B交換次數(shù);2S2快速排序入匕較次數(shù)遇23交換次敬日第7次排序快速排序止匕較次數(shù)；

17、言日交換次敝吟帖第口次排序冒泡排序：比較次數(shù)上曲爾交換次數(shù)：6?3 H直接插入排序:比較次數(shù)=蝠1。交換次數(shù)仍簡單選擇排序:捌次數(shù)：幻5。交損次數(shù):加5冒泡排序讓戢次教M?5日交換次數(shù)eiM直接插入排序工比較次數(shù)地39&交換狀數(shù)二流& 簡單選擇排序工比較次數(shù)=坐錨 交換次數(shù)壯居快速排序;比較次數(shù)溫3H交換次數(shù):M8快速排序=比較懈緒5交換次數(shù)方3口第4次排序冒泡排序;比較次數(shù)交換次數(shù)中如7直接插入排序:比較次數(shù)二交換次數(shù)骷第R次排序冒泡排序;比較校數(shù)乂交摭次數(shù):T4R直接插入排序:比較我數(shù)h4盯 交換就數(shù):WU5簡單選擇排序讓匕較次數(shù)X95。交換次數(shù)盹?3快速排序工比較次麴需?7交換次數(shù)b54簡單選擇排序：朧次數(shù)二師5 g交揀次敝空汽 快速排序；比較次數(shù)/明交換次數(shù)少口自pHdceg exited a