算法排序問題實驗報告

1、排序問題求解實驗報告一、算法得基本思想1、宜接插入排序算法思想直接插入排序得基本思想就是將一個記錄插入到已排好序得序列中，從而得到一個新 得，記錄數(shù)增1得有序序列。直接插入排序算法得偽代碼稱為Insert ionSort.它得參數(shù)就是一個數(shù)組Al、n, 包含了 n 個待排序得數(shù)。用偽代碼表示直接插入排序算法如下：Insertions。rl(A)for i*-2 t o ndo keyA訂 /key表示待插入數(shù) I ns e rt A i i nto t he sorted s cquence A 1、i-1 ji-lwh i 1 ej0 and AjkeydoA|j+ 1 -A jj-j-1A

2、 fj+l *-ke y2、快速排序算法思想快速排序算法得基本思想就是，通過一趟排序?qū)⒋判蛐蛄蟹指畛瑟毩⒌脙刹糠?，其?部分記錄得關(guān)鍵字均比另一部分記錄得關(guān)鍵字小，則可對這兩部分記錄繼續(xù)進行排序，以達 到整個序列有序。假設(shè)待排序序列為數(shù)組A1、n,首先選取第一個數(shù) AO,作為樞軸(p ivou， 然后按照下述原則重新排列其余數(shù):將所有比A 0大得數(shù)都排在它得位置之前，將所有比 AW小得數(shù)都排在它得位置之后，由此以A0最后所在得位置i作為分界線,將數(shù)組 AU、n分成兩個子數(shù)組A 1、i-1與A i+U. n。這個過程稱作一趟快速排序。 通過遞歸調(diào)用快速排序，對子數(shù)組Al、i-1與Ai+1、n排

3、序。一趟快速排序算法得偽代碼稱為Parti tion.它得參數(shù)就是一個數(shù)組A 1、n與 兩個指針low、high,設(shè)樞軸為 P i vol key,則首先從high所指位置起向前搜索，找 到第一個小于pivot key得數(shù)，并將其移到低端,然后從low所指位置起向后搜索，找到第 一個大于pivotkey得數(shù)，并將其移到高端，重復這兩步直至low=higho最后，將樞軸移到 正確得位置上。用偽代碼表示一趟快速排序算法如下：low.Parti t i o n ( A, low. liig h ) A 0 *-Alow/用數(shù)組得第一個記錄做樞軸記錄pri votkey*-Alow樞軸記錄關(guān)鍵字W h

4、 ile 10 w=p r ivot key do h i gh*-high -J A 10 w -A high /將比樞軸記錄小得記錄移到低端W h ile lowh igh& A( I ow =pivo t ke y ) d o low1 o w+ 1 Ah i g h -A 1 owl /將比樞軸記錄大得記錄移到高端A I ow A 0 /樞軸記錄到位 retu r n low /返回樞軸位置二、算法得理論分析1、直接插入排序算法理論分析從空間來瞧，直接插入排序只需要一個數(shù)得輔助空間;從時間來瞧，直接插入排序得基 本操作為:比較兩個關(guān)鍵字得大小與移動記錄。先分析一趟直接插入排序得情況。偽

5、代碼 Insertions ort中while循環(huán)得次數(shù)取決于待插入得數(shù)與前i-l個數(shù)之間得關(guān)系。若 AiA0,則在 while循環(huán)中，待插入數(shù)需與有序數(shù)組 Al、iJ中i-1個數(shù)進行 比較，并將A i-1中i- 1個數(shù)后移。則在整個排序過程(進行n-I趟插入排序中，當待 排序數(shù)組中數(shù)按非遞減有序排列時，則需進行數(shù)間比較次數(shù)達最小值n-L數(shù)不需要移動;反 之，當待排序數(shù)組中數(shù)按非遞增有序排列時，總得比較次數(shù)達最大值(n+2)(n-l ) /2,數(shù)移動 得次數(shù)也達到最大值(n+4 ) (n-l)/2若待排序數(shù)組就是隨機得,即待排序數(shù)組中得數(shù)可能出現(xiàn)得齊種排序得概率相同，則我們可 取上述最小值與最

6、大值得平均值，作為直接插入排序時所需進行數(shù)間得比較次數(shù)與數(shù)得移動次 數(shù)，約為2/4。因此直接插入排序算法，在最佳情況下得時間復雜度就是0(n),在最壞情況下得時間復雜度 為 0(2)。2、 快速排序算法理論分析下面我們來分析快速排序得平均時間性能。假設(shè)T(n)為對n個記錄AU、n 進行快速排序所需時間，則由算法 Qu i ckSori 可見：其中.Tp a ss( n)為對n個記錄進行一趟快速排序P arti t ion(A,l.n)所需得時間，從一 越快速排序算法可見，其與記錄數(shù)n成正比，可以用cn表示(C為某個常數(shù));T(k-l)與Tn-k)分別為對Al、k-1與Ak+1、n中記錄進行快速

7、排序QuickSor t (A. 1 , k-1) 與1至n Z間任何一值得概率柑同，快速排序所需時間得平均值則為Ta V g(n)= k nlnii. n為待排序序列中記錄得個數(shù),k為某個常數(shù)。通常,快速排序被認為就是，在所有同數(shù)量級(O (niogn)得排序方法中，其平均性能Quic k Sorts.如Ln)所需時間。假設(shè)待排序列中記錄就是隨機排列得，則在一趟排序之后, k取 其中 最好。但就是，若初始記錄序列按關(guān)鍵字有序或基本有序時,快速排序?qū)⑼懟癁槠鹋菖判颍鋾r 間復雜度為0 (22)。三、試驗分析1、試驗環(huán)境W I N32 系統(tǒng),VC6、02、程序得執(zhí)行txt1) 由函數(shù)datage

8、netare ()生成200 00個在區(qū)間1. 100 0 00上得隨機整數(shù)，并將隨機整數(shù) 保存到數(shù)組numl，接著調(diào)用函數(shù)WriteF i le ()將這些數(shù)輸出到外部文件da ta. 中。接著e F2) 調(diào)用函數(shù)ReadFi leOA data, txt中讀取數(shù)據(jù)，并將其保存到數(shù)組num 1(中。 對數(shù)組numl進行直接插入排序,并計算與記錄其運行時間。最后，調(diào)用函數(shù)Wri t ile()將直接插入排序得結(jié)果寫入resultsIS. txt.井記錄運行時間為Time I S。3) 調(diào)用函數(shù)Re a dFil e ()從d ata、t xt中讀取數(shù)據(jù)，并將其保存到數(shù)組num2 沖。EljCr

9、eate 20000 randomnumbers from 1 to 100000接著對數(shù)組num 2進行快速排序，并i|算與記錄苴運行時間。最后，調(diào)用函數(shù)W r it e File() 將快速排序得結(jié)果寫入resultsQS.并記錄運行時間為TimeQSo3、試驗數(shù)據(jù)當 N=2 0 000 時：InsertionSort Start The Time-comsuptionin Insertionsort i$ 0.325900 seconds!Quicksort StartThe Time-comsuptionP廠ess any key to continuein Quicksortis 0

10、0300000 seconds：當 N=300 0 0 時:1 to 100000Create 38QGG random numbers fromInsertionSort Start The Time-comsuption in InsertionSort is 0,719000 seconds?Quicksort Start The Time-comsupt ion in Quicksort is 0,00500660 seconds： P廠ess any key to continue當N= 400 00 時:3Create 馬QQQQ randomnumbers from 1 to 1

11、QOOOGInsertionsort Start The Time-comsuptionin InsertiomSort is 1.39706 seconds?Quicksort StartThe Time-comsuptionPress any key to continuein Quicksort is 000S0000Q seconds：當N= 5 0000 時:Create 5G00Q random numbers from 1 to 1GG00QInsertionSort Start .The Time-comsuption in InsertionSort is 2.13969 s

12、econds?Quicksort Start The Tinte-comsuption in Quicksort is 0.0100006 seconds： Press any key to continue當N=6 000 0 時:9Create 6GO0O random numbers from 1 to lOQQOOInertionSort Start .The Time-comsuption in InsertionSort is 3.O50GO seconds?Quicksort Start The Timecorft$uptiort in Quicksort is O.OI2090

13、8 seconds： Press any key to continue當 N=7 0000 時:Create 70008 randomnumber from 1 to lOOOGOInsertionSort Start The Time-comsuptionin Quicksort is 0.G1lOOOQ second令;in InsertionSort is 57109 seconds?Quicksort StartThe Time-comsuptionP廠ess any key to continue當 N=8 0 000 時:Create 80080 random numbers f

14、rom 1 to 1OQ0GGInsertionSort Start 0 050、0080、0 10、01 20、oil0、0 13做出折線統(tǒng)訃圖快速排序和插入排序時間比較插入排 序快速排 序四、試驗心得通過本次試臉首先對在C+下得文件操作有了一迫得深入認識，對于快速排序與插入排序 得時間有了相當淸晰且一目了然得認識,并且從原理上明白了快速排序得快得原因，對各種排 序算法得優(yōu)劣性有了全局得認識！五、實驗代碼#1 n C lude include ft i n c 1 u d e #include V f streani#inc I ude u s ing nam e spac e s t d;

15、con s t int NumS = 80000:VO i d d a t aseneta re( i ni num jnt n);/產(chǎn)生隨機數(shù)，保存到數(shù)組 num void Write num , c h a r namc, int n); / /輸出數(shù)組 n um 到 data、i x t 文件 void Read num ,c h ar namc) J /讀取名為nam e文件中得數(shù)據(jù)，保存到數(shù)組num void QuickSor t (i nt arr . in t n)： /將數(shù)組 ar r 中數(shù)據(jù)快速排序void In s e rtionSo rt(int arr E),i n t

16、 n);/將數(shù)組 arr 沖數(shù)據(jù)宜接插入排序 int mai n () 4 n t *num=(int *)m a lloc(siz e o f (in t )*N u mS)：int *numl= (int *)malloc(sizeo f (int)*NuniS):4 nt *num2=( i n t *)ma 1 I oc(si zeof(in t )*NumS); bclockst a rLt i me ken d Jim e 1, s lart_t i m e 2, e nd_tim e 2;double timeQS= 0 , t i meIS=0；oco u t*C r e a

17、te N u inS ran d om numbe rs f r om 1 to 10 0 000 en d 1 ；a t a g e net a rc(inimNumS) ; / /產(chǎn)生隨機數(shù)，保存到數(shù)組numWriicjdata、txt, NumS)； 輸出數(shù)組到 da t a、1x(文件coiU、p recisi o n( 6 ); 設(shè)置浮點數(shù)得顯示精度c 0 u仁 s e tf(i 0 s_b a s e :showpo i nt); /輸出末尾得/直接插入排序得分析Rea d d ala、ixt”)；/讀取dat a. txt中得數(shù)據(jù)，保存到數(shù)組num 1coutn Inse r t

18、 i onS ortS t a r t 八、n;s t art_time I = c loc k () ; /開始計時Ins e rtion Sort(numkNumS)： /M接插入排序數(shù)組numl中得數(shù)據(jù)en d jime 1 = c lock (); / /結(jié)束計時t i meIS=(d o uble)(end_ t imel siartj i ni e 1)/C LOCK S_P E R_SEC;i n In s e r ti o nSor t is * t ime 1 SvvNuniS ) ：/排序后得數(shù)據(jù)輸出到resuIlQStxt e s u 1 isIS .txtc OU t

19、The Tim e-su ption seconds !nn:/輸出運行時間 xWri t e, results IS、t xt。輸出運行時間t i me I S到rof s t r earn o c out:g c OIK、op e n ( rc s uhsIS、txt j o s:a p p);(ocou t、good()/打開 r esul t s 1 S、txt8 0 coutnTlie Time-suplio n i n Ins e riionSort i sI S secon d s nlocou t、c io s e ()：elser esullsISx tx t ! n”;M

20、0 ut nCan not open 0 exi t (1); 異常退出讀取data, txt中得數(shù)據(jù)，保存到數(shù)組num2 Start 、八八 n”：快速排序得分析 RcadJdata、t xt)；0 c OU t VV”Qui c kS 0r tsta r t_lime2=clock (); 開始汁時oQu i ckSort (nu m2, NuniS)； /快速排序數(shù)組num中得數(shù)據(jù)en d Jime2=clock()： / / 結(jié)束訃時time QS=(double)(endJime 2 - s lart_tim e 2 )/CLOCKS_P E R_SEC;0 c oui Tlie T

21、ime-suption i n QuickS orl is vvtimcQSvv” see o n ds:n; /輸出 運行時間Wri t e/TcsullsQS、txt . NumS); 排序后得數(shù)據(jù)輸出到 rcsullQS、txtb / / 輸出運行時間 t i meQS 到 resu I t sQS. tx t pocoiU. openCtesuhsQ S、t x t,ios: a pp);i f (ocout g 0 0 d()/打開 rcsultsIS、txtdOcoutVV“nThcTimcs up ti o n in Qu i c kSo r t is vV t i meQS s

22、eco n dsn:0 c out、clos e ();elseco u tnCan not open r esullsQ S、t xt!n ; exit(l) ; /異常退出re turn 0;VO i d dat a g e n etarefin t *numj n t n )M nt 1；srand (u n signed i me (0) ; / / srand()種子發(fā)生器函數(shù)，還有 rand()隨機 數(shù)生成器函數(shù)for i =0： in;i+)/產(chǎn)生個到之間得隨機數(shù)0num(訂 =rand 0%9999+1:Printf Cn)；將數(shù)組中得數(shù)據(jù)輸出到文件void Writ e *n

23、unichar name An t n) g f streamocoul：oc ouix 0 pen (na mejos:irunc); i nt i= 0 ;if ( ocou t、f a i 1()exit 1 )： 打開文件失敗，退出 fo r(：in： i +)xKoulvvnum ivv”；。if (i+l)%40=0 I I i =n - I ) /每輸出 40 個數(shù),換一行3 oc ouin;ocout c loseO：將文件中得數(shù)據(jù)輸入到數(shù)組VO i d R e ad *numxha r n am e ) b s tring s trL i ne：i n t 1=0:char a ch L in e 300;0 c 0 nsi cha r * p c hTo k :4 f s t ream i c i n ;icin、open (name, i os:in) ; /打開名為 name 得文件 whil e (i c i n X go od()“ini i = 0：wh i le ( g e t lineCicin.sirLi n e)osl r L i nc、 copy(achL i ne.str Line、 s ize(). 0 );aachLi n e sirLin e、si z e(