數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)8排序

實(shí)驗(yàn)八排序一、實(shí)驗(yàn)?zāi)康?.熟悉掌握教材中所介紹的幾種排序方法。2.學(xué)會(huì)分析各種內(nèi)排序算法的性能。二、實(shí)驗(yàn)內(nèi)容隨機(jī)產(chǎn)生20位整數(shù)輸入序列，編寫程序，按下列排序方法將序列從小到大排序并輸出。冒泡排序快速排序紀(jì)錄每種方法比較次數(shù)和移動(dòng)次數(shù)三、實(shí)驗(yàn)步驟1、冒泡排序冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。重復(fù)以上過程，仍從第一對數(shù)開始比較。如此下去，直至最終完成排序。 2、快速排序基本思想快速排序（Quicksort）是對冒泡排序的一種改進(jìn)。由C.A.R.Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。實(shí)現(xiàn)方法設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。一趟快速排序的算法是：1）設(shè)置兩個(gè)變量I、J，排序開始的時(shí)候：I=1，J=N-1；2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X=A[0]；3）從J開始向前搜索，即由后開始向前搜索（J=J-1），找到第一個(gè)小于X的值，讓該值與X交換；4）從I開始向后搜索，即由前開始向后搜索（I=I+1），找到第一個(gè)大于X的值，讓該值與X交換；5）重復(fù)第3、4步，直到I=J；算法說明首先為了避免產(chǎn)生的隨機(jī)數(shù)過大，我們限定了了隨機(jī)數(shù)為1-100之間，其次我們分別運(yùn)用函數(shù)產(chǎn)生隨機(jī)數(shù)兩次，第一次為使用冒泡排序，第二次為使用快速排序。測試結(jié)果分析與探討在設(shè)計(jì)中除了注意冒泡排序和快速排序的原理外，還需要注意函數(shù)間的套用中出現(xiàn)的形參和實(shí)參的類型統(tǒng)一，以及交換兩個(gè)數(shù)值時(shí)候，中介參數(shù)的使用。附錄：源代碼源代碼列在附錄中，要求程序風(fēng)格清晰易理解，有充分的注釋。有意義的注釋行不少于30%。#include"stdio.h"#include"time.h"#include"stdlib.h"#include"iostream"usingnamespacestd;voidQuickSort(intp[],intstart,intend){if(start>=end){return;}inti=0,j=0,tmp=0;i=start;j=end-1;do{while(p[i]<p[end]){i++;}while(p[j]>=p[end]){j--;}if(i<j){tmp=p[i];p[i]=p[j];p[j]=tmp;}else{tmp=p[i];p[i]=p[end];p[end]=tmp;}}while(i<j);QuickSort(p,start,i-1);QuickSort(p,i+1,end);}voidPrintArrary(intdata[],intsize){for(inti=0;i<size;++i){cout<<data[i]<<"";}cout<<endl;}voidmain(){ inta[20],i,j,t,flag; intargc[20]; srand((unsigned)time(0)); for(i=0;i<20;i++) a[i]=rand()%100; cout<<"隨機(jī)產(chǎn)生20個(gè)100以內(nèi)的整數(shù)"<<endl; for(i=0;i<20;i++) cout<<a[i]<<""; for(i=0;i<19;i++)/*改進(jìn)型冒泡法排序*/ { flag=0; for(j=0;j<20-i-1;j++) if(a[j]>a[j+1]) { t=a[j];/*交換a[i]和a[j]*/ a[j]=a[j+1]; a[j+1]=t; flag=1; } if(flag==0)break; } cout<<endl; cout<<"將這20個(gè)整數(shù)按照冒泡排序進(jìn)行升序排列"<<endl; for(i=0;i<20;i++) cout<<a[i]<<""; cout<<endl; for(i=0;i<20;i++) argc[i]=rand()%100; cout<<"再次隨機(jī)產(chǎn)生20個(gè)100以內(nèi)的整數(shù)"<<endl; Pr