數(shù)據(jù)結(jié)構(gòu)作業(yè)報(bào)告

1、華南農(nóng)業(yè)大學(xué)信息學(xué)院 設(shè)計(jì)性、綜合性實(shí)驗(yàn) 起止日期:2002 -2003 學(xué)年第一學(xué)期系別01計(jì)算機(jī)班級(jí)01計(jì)算機(jī)（4）班小 組 名實(shí)驗(yàn)題目實(shí)現(xiàn)各種排序算法并分析與比較設(shè)計(jì)性 綜合性分工情況學(xué)號(hào)姓名分工得分2001374424吳曉輝算法思想，程序設(shè)計(jì)，調(diào)試并通過程序，寫報(bào)告自我評(píng)價(jià)本程序完成實(shí)驗(yàn)要求的全部功能直接插入排序、shell排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序、基數(shù)排序，程序代碼符合書寫規(guī)范，實(shí)驗(yàn)報(bào)告敘述清晰完整，有詳盡的分析和總結(jié)。在實(shí)驗(yàn)過程中，積極配合本團(tuán)隊(duì)分工合作的精神，努力學(xué)習(xí)，總算不負(fù)眾望，將程序編好，在此，我更想感謝的是老師的教導(dǎo)，在她的幫助下，我才順利

2、完成了本次的任務(wù)。教師評(píng)語l a-能夠分工合作，體現(xiàn)良好的團(tuán)隊(duì)協(xié)作精神，完成實(shí)驗(yàn)要求的全部功能并運(yùn)行通過，程序代碼符合書寫規(guī)范，實(shí)驗(yàn)報(bào)告敘述清晰完整，有詳盡的分析和總結(jié)。l b-能夠分工合作，體現(xiàn)良好的團(tuán)隊(duì)協(xié)作精神，完成實(shí)驗(yàn)要求的全部功能，程序代碼符合書寫規(guī)范，實(shí)驗(yàn)報(bào)告敘述清晰完整。l c-完成實(shí)驗(yàn)要求的大部分功能，實(shí)驗(yàn)報(bào)告良好。l d-未按時(shí)完成實(shí)驗(yàn)，或者抄襲。 教師簽名： 一、需求分析本程序要求用函數(shù)實(shí)現(xiàn)如下算法：（1） 直接插入排序（2） 希爾排序（3） 冒泡排序（4） 快速排序（5） 選擇排序（6） 堆排序（7） 歸并排序（8） 基數(shù)排序并定量分析各種排序算法在正序、逆序、少量、大量情

3、況下的運(yùn)行效率。1輸入的形式和輸入值的范圍全部待排序的數(shù)據(jù)都是整形數(shù)據(jù),范圍為0 65535，并且為無序數(shù)列。2 輸出的形式輸出排好序的數(shù)列。3 程序所能達(dá)到的功能：本程序可以從磁盤文件讀入數(shù)據(jù)，將其進(jìn)行8種方法排序，程序代碼清晰，結(jié)果輸出簡單。4 測(cè)試數(shù)據(jù)二、概要設(shè)計(jì)程序通過一個(gè)主函數(shù)（main）調(diào)用所有排序方法，大致的函數(shù)調(diào)用關(guān)系如下： 希爾排序直接插入排序選擇排序冒泡排序主函數(shù)堆排序快速排序歸并排序 基數(shù)排序二、 算法表述三、詳細(xì)設(shè)計(jì)說明1直接插入排序假設(shè)待排序的記錄存放在數(shù)組r0.n-1中，排序過程的某一中間時(shí)刻，r被劃分成兩個(gè)子區(qū)間r0i-1和ri.n-1，其中：前一個(gè)子區(qū)間是已排好

4、序的有序區(qū)；后一個(gè)子區(qū)間則是當(dāng)前未排序的部分。直接插入排序的基本操作是將當(dāng)前無序區(qū)的第1個(gè)記錄ri插入到有序區(qū)r0.i-1中適當(dāng)?shù)奈恢茫箁0i變?yōu)樾碌挠行騾^(qū)。2 希爾排序先取定一個(gè)小于n的整數(shù)d作為第一個(gè)增量，把表的全部記錄分成d組，所有距離為d1的倍數(shù)的記錄放在同一組中，在各組內(nèi)進(jìn)行直接插入排序；然后取第二個(gè)增量d2d1，重復(fù)上述的分組和排序，直至增量d1，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂? 冒泡排序通過無序區(qū)中相鄰記錄關(guān)鍵字間的比較和位置的交換，使關(guān)鍵字最小的記錄逐漸向上升。整個(gè)算法是從最下面的記錄開始，對(duì)每兩個(gè)個(gè)相鄰的關(guān)鍵字進(jìn)行比較，且使關(guān)鍵字小的記錄換至關(guān)鍵字較大的位置，

5、使得經(jīng)過一趟冒泡排序后，關(guān)鍵字最小的記錄到達(dá)最上端，接著再在剩下的記錄中找關(guān)鍵字次小的記錄，并把它換至第二個(gè)位置上。依此類推，一直到所有記錄都有序?yàn)橹埂? 快速排序在待排序的n個(gè)記錄中任取一個(gè)記錄（通常取第一個(gè)記錄），把該記錄放入最終位置后，數(shù)據(jù)序列被此記錄分割成兩部分。所有比它大的記錄放置在后一部分，所有比它小的記錄放置在前一部分，并把該記錄排在這兩部分之間，這個(gè)過程稱作一趟快速排序。之后對(duì)所有的兩部分分別重復(fù)上述過程，直至每部分內(nèi)只有一個(gè)記錄為止。簡而言之，每趟使表的第一個(gè)元素入終位，將表一分為二，對(duì)子表按遞歸方式繼續(xù)這種劃分，直至劃分的子表長為1。5 選擇排序基本思想：第i趟排序開始時(shí)，

6、當(dāng)前有序區(qū)和無序區(qū)分別為r0.i-1和rin-1,該趟排序則是從無序區(qū)中選出關(guān)鍵字最小的記錄rk,它與無序區(qū)的第一個(gè)記錄ri交換,使r0i和ri+1n分別變?yōu)樾碌挠行騾^(qū)和無序區(qū)。因?yàn)槊刻伺判蚴褂行騾^(qū)中增加一個(gè)記錄，且有序區(qū)的記錄均不大于無序區(qū)中記錄的關(guān)鍵字，即第i趟排序之后r0i的所有關(guān)鍵字等于ri+1.n-1中的所有關(guān)鍵字,所以進(jìn)行n-1趟之后有r0.n-2的所有關(guān)鍵字小于等于其后所有關(guān)鍵字,也就是說,經(jīng)過n-1趟排序后,整個(gè)表r0.n-1遞增有序.6 堆排序堆排序是在排序過程中，將順序表中存儲(chǔ)的數(shù)據(jù)看成是一棵完全而叉樹，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在聯(lián)系來選擇關(guān)鍵字最小記錄。

7、具體做法是：把待排序的表的關(guān)鍵字存放在數(shù)組r1n之中，將r看成一棵二叉樹，每個(gè)結(jié)點(diǎn)表示一個(gè)記錄，原表的第一個(gè)記錄r1作為二叉樹的根，以下各記錄r2.n依次逐層從左到右順序排序，構(gòu)成一棵完全二叉樹，任意結(jié)點(diǎn)ri的左孩子是r2i+1，右孩子是r2i+2，雙親是ri/2。7 歸并排序歸并排序是多次將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表以兩個(gè)有序表的合并為例：每次從兩個(gè)有序表中取出一個(gè)記錄進(jìn)行關(guān)鍵字的比較，將較小的放入一個(gè)臨時(shí)數(shù)組，最后將各段中余下的部分直接復(fù)制到臨時(shí)數(shù)組。這樣臨時(shí)數(shù)組就是一個(gè)有序表。8基數(shù)排序 以r為基數(shù)的最低位優(yōu)先基數(shù)排序的過程是：假設(shè)線形表由結(jié)點(diǎn)序列a0，a1，a(n-1)

8、構(gòu)成每個(gè)結(jié)點(diǎn)aj的關(guān)鍵字由d元組（）。在排序過程中使用r個(gè)隊(duì)列q0，q1，.qr-1。排序過程如下： 對(duì)i=0，1，.，d-1，依次做一次“分配”收集”（其實(shí)就是一次穩(wěn)定的排序過程）。 分配：開始時(shí)，把q0，q1，qr-1各個(gè)隊(duì)列置成空隊(duì)列，然后依次考察線性表中的每一個(gè)結(jié)點(diǎn)aj（j=0，1，n-1），如果aj的關(guān)鍵字，就把a(bǔ)j放進(jìn)qk隊(duì)列中。收集：把q0，q1，.，qr-1各個(gè)隊(duì)列中的結(jié)點(diǎn)依次首尾相接，得到新的結(jié)點(diǎn)序列，從而組成新的線性表。int asize; 重要數(shù)組，用于存放數(shù)據(jù)int count,show,row; 記錄所需要的信息，如換行等等load() 用于從磁盤讀取數(shù)據(jù)insert

9、ion() 插入排序shellsort() 希爾排序bubblesort() 冒泡排序quicksort() 快速排序selection() 選擇排序partition(int lb,int ub,int piv,int *pn,int *pm) 快速排序中使用heapsort() 堆排序merge() 歸并排序radixsort() 基數(shù)排序void hpsort1(int x,int n,int *count_n,int *count_m) 基數(shù)排序中使用四、 調(diào)試分析1. 本程序經(jīng)過多次調(diào)試才得以通過執(zhí)行，從插入排序到基數(shù)排序，每一個(gè)都經(jīng)過親自調(diào)試2. 本人覺得本題中最難的是基數(shù)排序，在

10、本程序中，我使用遞歸等方法才做出3. 對(duì)本程序的時(shí)空分析如下各排序的對(duì)比，交換次數(shù)如下表：（以下數(shù)據(jù)為比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)之和）少量數(shù)據(jù)大量數(shù)據(jù)順序數(shù)據(jù)逆序數(shù)據(jù)插入排序20556965希爾排序4712454258冒泡排序56173245110快速排序1572036367選擇排序7214749080堆排序656176839歸并排序19941940基數(shù)排序402002022由上表可知，在忽略輔助空間的情況考慮，無論運(yùn)行少量數(shù)據(jù)和大量數(shù)據(jù)，歸并排序占優(yōu)，而當(dāng)數(shù)據(jù)有序時(shí)，插入排序占優(yōu)，主要因?yàn)閷?shí)現(xiàn)該排序時(shí)的算法用了一個(gè)輔助數(shù)組，大大減少了數(shù)據(jù)的移動(dòng)次數(shù)，數(shù)據(jù)完全逆序時(shí)，堆排序效率最高。a)從平均時(shí)間

11、性能而言，快速排序最佳，其所需時(shí)間最省，但快速排序在最壞情況 下的時(shí)間性能為o(n*n)不如堆排序和歸并排序o(n*logn)。而后兩者相比較的結(jié)果是，在n較大時(shí)， 歸并排序所需的時(shí)間較堆排序省，但它所需的輔助存儲(chǔ)量最多。i. 單排序中以直接排序最簡單，當(dāng)序列的記錄基本有序或較小時(shí)，它是最佳的排序方法。ii. 數(shù)排序的時(shí)間復(fù)雜度較小。因此最適用于n值很大的時(shí)候而關(guān)鍵字較小的序列。若關(guān)鍵字也很大，而序列中的大多數(shù)記錄的最高位關(guān)鍵字均不同，則亦可先按最高位關(guān)鍵字不同將序列分成若干小的子序列，而后進(jìn)行直接插入排序。iii. 從方法的穩(wěn)定性來比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法，所有時(shí)間復(fù)雜度為o（n*n）

12、的簡單排序也是穩(wěn)定的，然而，快速排序，堆排序和希爾排序等時(shí)間性 能 較好的排序方法都是不穩(wěn)定的，一般來說，排序過程中的比較是在相臨的兩個(gè)記錄關(guān)鍵字間進(jìn)行的排序方法都是穩(wěn)定的。由于大多數(shù)情況下排序是按記錄的主關(guān)鍵字進(jìn)行的，則所用的排序方法是否穩(wěn)定無關(guān)緊要。若排序按記錄的次關(guān)鍵字進(jìn)行，則應(yīng)根據(jù)問題所需慎重選擇排序方法及其描敘算法。綜上所敘，在這些排序方法中沒有哪一中是絕對(duì)最優(yōu)的，有的適用于n較大的情況，有的適用于n 較小的情況，因此，在實(shí)用時(shí)需要根據(jù)不同的情況適當(dāng)選用，甚至可以將多種方法綜合起來使用。算法的時(shí)空分析和改進(jìn)設(shè)想五、用戶使用說明程序運(yùn)行后,將進(jìn)入以下主菜單:菜單設(shè)計(jì)為輸入相應(yīng)的數(shù)字進(jìn)行選擇。本人在程序中使用了db10.txt這個(gè)文件，只要這個(gè)文件存在數(shù)據(jù)，就可以進(jìn)行排序，按9可以用來往該文件添加數(shù)據(jù)，18用來排序分別是1， 插入排序2， 希