1、<p><b>　　目錄</b></p><p><b>　　1 前言1</b></p><p><b>　　2工程概況1</b></p><p>　　2.1工程所用時1</p><p>　　2.2項目負(fù)責(zé)人1</p><p>　　2.

2、3項目指導(dǎo)人1</p><p><b>　　3正文1</b></p><p><b>　　3.1冒泡排序2</b></p><p>　　3.1.1冒泡排序基本思想2</p><p>　　3.1.2冒泡法的實現(xiàn)過程2</p><p>　　3.1.3冒泡法的改進(jìn)3&l

3、t;/p><p>　　3.1.4改進(jìn)方法3</p><p>　　3.1.5冒泡法分析3</p><p>　　3.1.5.1算法的最好時間復(fù)雜度3</p><p>　　3.1.5.2算法的最壞時間復(fù)雜度3</p><p>　　3.1.5.3算法的平均時間復(fù)雜度4</p><p>　　3.1.

4、5.4算法穩(wěn)定性4</p><p><b>　　3.2希爾排序4</b></p><p>　　3.2.1希爾排序4</p><p>　　3.2.2希爾排序算法基本思想4</p><p>　　3.2.3希爾排序的實現(xiàn)過程4</p><p>　　3.2.4希爾分析5</p>

5、<p>　　3.2.5時間性能5</p><p>　　3.2.5.1增量序列的選擇5</p><p>　　3.2.5.2好的增量序列的共同特征5</p><p>　　3.2.5.3希爾排序的時間性能5</p><p>　　3.3快速排序算法6</p><p>　　3.3.1快速排序6</p&

6、gt;<p>　　3.3.2快速排序基本思想6</p><p>　　3.3.3快速排序的具體過程6</p><p>　　3.3.4算法設(shè)計6</p><p>　　3.3.5算法分析7</p><p><b>　　4致謝8</b></p><p><b>　　5課程

7、設(shè)計小結(jié)8</b></p><p><b>　　6參考文獻(xiàn)8</b></p><p><b>　　前言</b></p><p>　　隨著計算機產(chǎn)業(yè)的飛速發(fā)展，它已經(jīng)深入到人類生活的各個領(lǐng)域，計算機的應(yīng)用并不局限與科學(xué)計算，更多地用于控制和管理及處理實際問題。與此相應(yīng)，為了編寫出一個好的程序，必須分析待處理的

8、對象的特性以及各處理對象之間存在的關(guān)系。數(shù)據(jù)結(jié)構(gòu)就是在這種背景中形成和發(fā)展的。</p><p>　　“數(shù)據(jù)結(jié)構(gòu)”作為計算機學(xué)科中一門綜合性的專業(yè)基礎(chǔ)課，必須要以理論與實踐相結(jié)合，才能更好學(xué)習(xí)這門學(xué)科，所以我們數(shù)據(jù)結(jié)構(gòu)設(shè)置了課程設(shè)計這項理論與實踐相結(jié)合的學(xué)習(xí)內(nèi)容。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要求同學(xué)獨立完成一個較為完整的應(yīng)用需求分析，在完成設(shè)計課程設(shè)計的過程中，深化對數(shù)據(jù)結(jié)構(gòu)排序算法課程的理解，訓(xùn)練同學(xué)們綜合運用所學(xué)知識處理實

9、際問題的能力，強化面向?qū)ο蟮某绦蛟O(shè)計理念。設(shè)計同學(xué)們的程序設(shè)計水平和調(diào)試水平有大幅度的提高。讓同學(xué)更好了解數(shù)據(jù)結(jié)構(gòu)，更好理解編程思想，是自己的程序得以運行，實現(xiàn)自己的目的，解決實際問題。</p><p><b>　　工程概況</b></p><p><b>　　2.1工程所用時</b></p><p>　　此次工程從12月

10、19日開始，于12月28日結(jié)束，歷時10天時間。</p><p><b>　　2.2項目負(fù)責(zé)人</b></p><p>　　********** 信息工程學(xué)院 計算機科學(xué)與技術(shù)14-1</p><p><b>　　2.3項目指導(dǎo)人</b></p><p>　　********** 信息

11、工程學(xué)院 講師</p><p><b>　　正文</b></p><p>　　我此次課程設(shè)計是關(guān)于排序算法的。其主要目的是排序是掌握三種排序算法，掌握三種排序方法的實現(xiàn)掌握三種排序算法的優(yōu)劣分析及花費時間的計算。設(shè)計內(nèi)容和要求利用C語言編程思想把隨機函數(shù)產(chǎn)生的隨機函數(shù)，利用冒泡法排序，希爾排序算法及快速排序算法進(jìn)行排序，并在C語言上運行，比較這三種排序算法上級所耗費的

12、時間。</p><p>　　計算機程序設(shè)計中的一種重要操作，他的功能是講一個數(shù)據(jù)元素的任意序列，重新排列成一個按關(guān)鍵字有序的序列。</p><p>　　所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。當(dāng)待排序記錄的關(guān)鍵字都不相同時，排序結(jié)果是惟一的，否則排序結(jié)果不惟一。在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保

13、持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生改變，則稱這種排序方法是不穩(wěn)定的。 要注意的是，排序算法的穩(wěn)定性是針對所有輸入實例而言的。即在所有可能的輸入實例中，只要有一個實例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。 關(guān)于算法的描述是對要解決一個問題或要完成一項任務(wù)所采取的方法和步驟的描述，包括需要什么數(shù)據(jù)采用什么結(jié)構(gòu)、使用什么語句以及如何安排這些語句，在C語言程序上實現(xiàn)所要完成的問題，達(dá)到排序的目的。

14、</p><p><b>　　3.1冒泡排序</b></p><p>　　指依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。由于在排序過程中總是小數(shù)往前放，大數(shù)往后放，相當(dāng)于氣泡往上升，所以稱作冒泡排序。</p><p>　　3.1.1冒泡排序基本思想</p><p>　　在第一趟：首先比較第1個和第2個數(shù)，將小數(shù)放

15、前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。</p><p>　　在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的）。</p><p>　　第二趟結(jié)束，在

16、倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。</p><p>　　3.1.2冒泡法的實現(xiàn)過程</p><p>　　其實，就是一個for循環(huán)，最外面的循環(huán)控制循環(huán)的次數(shù)，需要有n-1次循環(huán)固定為for(i=n-1;i>0;i--)里面的循環(huán)從最大值開始，次數(shù)為n-1-i,固定為for(j=n-1;j>n-1-

17、i;j--)循環(huán)體就是：if（a[j-1]>a[j]）{temp=a[j-1];a[j-1]=a[j];a[j]=temp;}</p><p>　　3.1.3冒泡法的改進(jìn)</p><p>　　冒泡排序法存在的不足及改進(jìn)方法所以需要加以改進(jìn)，使它的不足之處得以改善。</p><p><b>　　3.1.4改進(jìn)方法</b><

18、/p><p>　　在排序過程中，執(zhí)行完最后的排序后，雖然數(shù)據(jù)已全部排序完備，但程序無法判斷是否完成排序，為了解決這一不足，可設(shè)置一個標(biāo)志單元flag，將其設(shè)置為OFF,表示被排序的表示是一個無序的表。在每一排序開始時，檢查此標(biāo)志，若此標(biāo)志為0，則結(jié)束排序；否則進(jìn)行排序； </p><p>　　當(dāng)排序的數(shù)據(jù)比較多時排序的時間會明顯延長。改進(jìn)具體做法是任意選取某一記錄（通常取第一個記錄），比較其關(guān)

19、鍵字與所有記錄的關(guān)鍵字，并將關(guān)鍵字比它小的記錄全部放在它的前面，將比它大的記錄均存放在它的后面，這樣，經(jīng)過一次排序之后，可將所有記錄以該記錄所在的分界點分為兩部分，然后分別對這兩部分進(jìn)行快速排序，直至排序完 </p><p>　　3.1.5冒泡法分析</p><p>　　3.1.5.1算法的最好時間復(fù)雜度</p><p>　　若文件的初始狀態(tài)是正序的，一趟掃描即可完

20、成排序。所需的關(guān)鍵字比較次數(shù)C和記錄移動次數(shù)M均達(dá)到最小值：</p><p><b>　　Cmin=n-1</b></p><p><b>　　Mmin=0。</b></p><p>　　冒泡排序最好的時間復(fù)雜度為O(n)。</p><p>　　3.1.5.2算法的最壞時間復(fù)雜度</p>

21、<p>　　若初始文件是反序的，需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次關(guān)鍵字的比較(1≤i≤n-1)，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動次數(shù)均達(dá)到最大值： Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最壞時間復(fù)雜度為：O(n2)。</p><p>　　3.1.5.3算法的平均時間復(fù)雜度</p>

22、;<p>　　冒泡算法的平均時間復(fù)雜度為：O(n2)。 雖然冒泡排序不一定要進(jìn)行n-1趟，但由于它的記錄移動次數(shù)較多，故平均時間性能比直接插入排序要差得多。 3.1.5.4算法穩(wěn)定性</p><p>　　冒泡排序是就地排序，且它是穩(wěn)定的。 </p><p><b>　　3.2希爾排序</b></p><p><b>

23、;　　3.2.1希爾排序</b></p><p>　　它是插入排序的一種。是針對直接插入排序算法的改進(jìn)。該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。</p><p>　　3.2.2希爾排序算法基本思想 </p><p>　　先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數(shù)的記錄放在同一個組中

24、。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個增量d2<d1重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序為止。 </p><p>　　3.2.3希爾排序的實現(xiàn)過程 </p><p>　　不設(shè)監(jiān)視哨的算法描述 </p><p>　　void ShellPass(Seq

25、List R，int d) </p><p>　　{//希爾排序中的一趟排序，d為當(dāng)前增量 </p><p>　　for(i=d+1;i<=n；i++) //將R[d+1．．n]分別插入各組當(dāng)前的有序區(qū) </p><p>　　if(R[ i ].key<R[i-d].key){ </p><p>　　R[0]=R[i];j=i-d

26、； //R[0]只是暫存單元，不是哨兵 </p><p>　　do {//查找R的插入位置 </p><p>　　R[j+d]=R[j]； //后移記錄 </p><p>　　j=j-d； //查找前一記錄 </p><p>　　}while(j>0&&R[0].key<R[j].key)； </p>

27、<p>　　R[j+d]=R[0]； //插入R到正確的位置上 </p><p>　　} //endif </p><p><b>　　3.2.4希爾分析</b></p><p>　　希爾排序是按照不同步長對元素進(jìn)行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以插入排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排

28、序?qū)τ谟行虻男蛄行屎芨摺Ｋ?，希爾排序的時間復(fù)雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。</p><p>　　不需要大量的輔助空間，和歸并排序一樣容易實現(xiàn)。希爾排序是基于插入排序的一種算法， 在此算法基礎(chǔ)之上增加了一個新的特性，提高了

29、效率。希爾排序的時間復(fù)雜度為 O(N*(logN)2)， 沒有快速排序算法快 O(N*(logN))，因此中等大小規(guī)模表現(xiàn)良好，對規(guī)模非常大的數(shù)據(jù)排序不是 最優(yōu)選擇。但是比O(N2）復(fù)雜度的算法快得多。并且希爾排序非常容易實現(xiàn)，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時快速排序在最壞 的情況下執(zhí)行的效率會非常差。 專家門提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不

30、夠快， 再改成快速排序這樣更高級的排序算法. 本質(zhì)上講，希爾排序算法的一種改進(jìn)，減少了其復(fù)制的次數(shù)，速度要快很多。 原因是，當(dāng)N值很大時數(shù)據(jù)項每一趟排序需要的個數(shù)很少，但數(shù)據(jù)項的距離很長。 當(dāng)N值減小時每一趟需要和動的數(shù)據(jù)增多，此時已經(jīng)接近于它們排序后的最終位置。 正是這兩種情況的結(jié)合才使希爾排序效率比插入排序高很多。 </p><p><b>　　3.2.5時間性能</b></p&g

31、t;<p>　　3.2.5.1增量序列的選擇 </p><p>　　Shell排序的執(zhí)行時間依賴于增量序列。 </p><p>　　3.2.5.2好的增量序列的共同特征 </p><p>　?、?最后一個增量必須為1； </p><p>　?、?應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。 </p>&

32、lt;p>　　有人通過大量的實驗，給出了目前較好的結(jié)果：當(dāng)n較大時，比較和移動的次數(shù)約在nl.25到1.6n1.25之間。 </p><p>　　3.2.5.3希爾排序的時間性能</p><p>　　希爾排序的時間性能優(yōu)于直接插入排序的時間性能 ，希爾排序的時間性能優(yōu)于直接插入排序的原因： </p><p>　?、佼?dāng)文件初態(tài)基本有序時直接插入排序所需的比較和移

33、動次數(shù)均較少。 </p><p>　?、诋?dāng)n值較小時，n和n2的差別也較小，即直接插入排序的最好時間復(fù)雜度O(n)和最壞時間復(fù)雜度0(n2)差別不大。 </p><p>　?、墼谙柵判蜷_始時增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過序，使文件較接近于有序狀態(tài)，所以新的一趟排序

34、過程也較快。 </p><p>　　因此，希爾排序在效率上較直接插人排序有較大的改進(jìn)。 </p><p><b>　　3.3快速排序算法</b></p><p><b>　　3.3.1快速排序</b></p><p>　　快速排序是對冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出

35、。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。</p><p>　　3.3.2快速排序基本思想</p><p>　　快速排序采用了一種分治的策略，通常稱其為分治法。其基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題

36、相似的子問題。遞歸地解決這些子問題，然后將這些子問題的解組合為原問題的解。3.3.3快速排序的具體過程</p><p>　　第一步，在待實現(xiàn)序的n個記錄中任取一個記錄，以該記錄的排序碼為準(zhǔn)，將所有記錄分成兩組，第1組各記錄的排序碼都小于等于該排序碼，第2組各記錄的排序碼都大于該排序碼，并把該記錄排在這兩組中間。第二步，采用同樣的方法，對左邊的組和右邊的組進(jìn)行排序，直到所有記錄都排到相應(yīng)的位置為止。</p

37、><p><b>　　3.3.4算法設(shè)計</b></p><p>　　下面的過程實現(xiàn)了快速排序：</p><p>　　為排序一個完整的數(shù)組A,最初的調(diào)用是</p><p><b>　　對數(shù)組進(jìn)行劃分。</b></p><p><b>　　3.3.5算法分析</b&

38、gt;</p><p>　　快速排序的運行時間與劃分是否對稱有關(guān)，而后者有與選擇了哪一個元素劃分有關(guān)。在最壞情況下，劃分過程產(chǎn)生的兩個區(qū)域分別包含個元素和1個元素。假設(shè)每一步都出現(xiàn)這種不對稱的劃分，因為劃分時間代價為，又因為，故算法的運行時間可遞歸地表達(dá)為：</p><p>　　為求這個遞歸式的解，注意到，對上失進(jìn)行迭代有：</p><p>　　因此，在最壞情況下，

39、快速排序算法的時間為。</p><p>　　最佳情況下，劃分過程產(chǎn)生的兩個區(qū)域大小都為。這時，有：</p><p><b>　　其解為</b></p><p>　　經(jīng)過分析，快速排序的平均代價與最佳情況下相似，只是系數(shù)不同而已。因此，可以說快速排序算法的時間復(fù)雜度為。</p><p><b>　　致謝</

40、b></p><p>　　此次課設(shè)，我非常感謝老師在我們程序設(shè)計的過程中辛勤的指導(dǎo)和不倦的教誨，感謝同學(xué)的熱心幫助！</p><p><b>　　課程設(shè)計小結(jié)</b></p><p>　　學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特征，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時間分析和空間分析的技術(shù)。另一方

41、面，本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。 在學(xué)習(xí)中，先要學(xué)習(xí)程序設(shè)計課程的目的掌握設(shè)計程序的思路，學(xué)習(xí)會用計算機語言編寫程序，以實現(xiàn)所需要處理的任務(wù)。要正確處理算法與語法的關(guān)系，算法是程序的核心、是靈魂，語法是外殼、是工具。不應(yīng)把學(xué)習(xí)重點全放在語法規(guī)則上，語法是重要的，不掌握語法規(guī)則就無法編寫出正確的程序。一定要把重點放在解題的思路上，通過思考，和大量的閱讀，來構(gòu)

42、造一個完整的程序。請記住：重要的是學(xué)會編程，而不是背語法。程序設(shè)計是為了鍛煉我們的實際動手能力，在一定程度上，又增加了我們的各方面的知識，特別是一些聯(lián)系實際的課程設(shè)計，它的完成需要自己平時積累的大量知識、并且需要勤于思考的能力和無限的激情。本次課設(shè)主要是學(xué)習(xí)程序設(shè)計的方法，進(jìn)行程序設(shè)計的基本訓(xùn)練，大多數(shù)的學(xué)生應(yīng)該把精力放在最基本，最常用的內(nèi)容上，學(xué)好基本功。</p><p><b>　　參考文獻(xiàn)<

43、;/b></p><p>　　【1】數(shù)據(jù)結(jié)構(gòu)（C語言版） 嚴(yán)蔚敏 ， 吳偉民 2011年5月 清華大學(xué)出版社</p><p>　　【2】計算機時代 吳紅芝， 郭麥成， 吳浩 2010 第6期 </p><p>　　【3】數(shù)據(jù)結(jié)構(gòu)算法與分析 (C語言版) 魏寶剛，陳越,，王申康 第1版 浙江大學(xué)出版社&