山大《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)07排序

1、實(shí)驗(yàn)七 排序一 實(shí)驗(yàn)任務(wù)常用排序算法的實(shí)現(xiàn)。二 實(shí)驗(yàn)?zāi)康?）掌握常用排序方法的思想，并用C語言實(shí)現(xiàn)這些排序算法。2）了解各種常用排序算法的性能（時間復(fù)雜性、空間復(fù)雜性、算法穩(wěn)定性、算法簡單性等）。三 實(shí)驗(yàn)原理1插入排序插入排序有直接插入排序、折半插入排序和希爾排序等方法。直接插入排序類似于線性表中有序表的插入：它由n-1趟排序組成，第i趟排序是向第1到i-1個有序記錄之間插入一個新記錄，使插入后的記錄序列仍為有序。在并向有序表中插入記錄時，如果通過“折半查找”來確定插入位置，這就是折半插入排序。希爾排序使用一個序列h1, h2, , ht，叫做增量序列（Increment Sequence）。

2、在使用增量hk的一趟排序之后，對于每一個記錄i有PiPi+hk，即所有相隔hk的記錄都被排序。此時稱該序列是hk-排序（hk-sorted）的。2快速交換排序它的基本思想是，按一定的規(guī)則選擇某個控制記錄作為樞軸（Pivot），首先通過交換各個記錄間的位置將它放置在它應(yīng)該在的位置，使它之前的記錄的關(guān)鍵字都比它的關(guān)鍵字小，它之后的記錄的關(guān)鍵字都比它的關(guān)鍵字大。對它前后的記錄各自形成的子序列，再按同樣的規(guī)則處理，直到所有記錄都被安置在相應(yīng)的位置上。3選擇排序選擇排序（Selection Sort）的基本思想是：在對n個記錄進(jìn)行的多趟排序過程中，第i趟排序是在n-i+1個記錄中選擇關(guān)鍵字最小的記錄作為

3、有序序列中的第i個記錄，其中，i=1, 2, , n-1。選擇排序主要包括簡單選擇排序和堆排序。簡單選擇排序（Simple Selection Sort）是一種簡單的排序方法。它每次從待排序的記錄序列中（范圍從i到n）選擇出關(guān)鍵字最小的記錄，把該記錄與序列中的第i個記錄交換位置。堆是一個序列，其中每個記錄包含一個關(guān)鍵字，序列中的位置k處的關(guān)鍵字，至少大于位置2k和2k+1處（假設(shè)這些位置存在于序列中）的關(guān)鍵字。堆排序的過程分為兩個步驟。首先，必須重新組合列表中的記錄項(xiàng)，使它們滿足堆的要求。第二，重復(fù)移去堆的頂層，并提升另一個記錄項(xiàng)頂替他的位置。4歸并排序把兩個或多個有序表合并成一個有序表的過程

4、稱為歸并（Merge）。若歸并的有序表有兩個，叫做二路歸并。對有序表反復(fù)利用歸并過程進(jìn)行排序的方法稱為歸并排序（Merging Sort）。利用二路歸并操作的排序稱為二路歸并排序。二路歸并排序的過程是：（1）把無序表中的每一個元素都看作是一個有序表，則有n個有序子表；（2）把n個有序子表按相鄰位置分成若干對（若n為奇數(shù)，則最后一個子表單獨(dú)作為一組），每對中的兩個子表進(jìn)行歸并，歸并后子表數(shù)減少一半；（3）反復(fù)進(jìn)行這一過程，直到歸并為一個有序表為止。四 實(shí)驗(yàn)設(shè)備、儀器、工具與資料 微機(jī)、VC五 實(shí)驗(yàn)內(nèi)容根據(jù)鍵盤輸入的數(shù)據(jù)建立一個待排序表，利用C語言設(shè)計一個主程序完成下列排序運(yùn)算：1）插入排序（直接

5、插入排序、折半插入排序和Shell排序）2）交換排序（快速排序）3）選擇排序（堆排序）4）歸并排序5）結(jié)束程序運(yùn)行六 實(shí)驗(yàn)步驟（1）實(shí)驗(yàn)預(yù)習(xí)1）預(yù)習(xí)本實(shí)驗(yàn)原理中的各種排序方法的思想。2）分析掌握教材212226頁中的算法7-17-10，為完成實(shí)驗(yàn)任務(wù)做好準(zhǔn)備。（2）實(shí)驗(yàn)步驟1）問題分析。充分地分析和理解此實(shí)驗(yàn)任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。3）詳細(xì)設(shè)計。詳細(xì)設(shè)計的目的是對子程序（過程或函數(shù)）的進(jìn)一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細(xì)節(jié)。4）編碼。在詳細(xì)設(shè)計的基礎(chǔ)上，對詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精，用C語言表示出來。5）在VC環(huán)境下調(diào)試程序。七 實(shí)驗(yàn)報告要求實(shí)驗(yàn)報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互關(guān)系。3）詳細(xì)設(shè)計：采用C語言定義的數(shù)據(jù)