山大《數(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語(yǔ)言實(shí)現(xiàn)這些排序算法。2）了解各種常用排序算法的性能（時(shí)間復(fù)雜性、空間復(fù)雜性、算法穩(wěn)定性、算法簡(jiǎn)單性等）。三 實(shí)驗(yàn)原理1插入排序插入排序有直接插入排序、折半插入排序和希爾排序等方法。直接插入排序類(lèi)似于線性表中有序表的插入：它由n-1趟排序組成，第i趟排序是向第1到i-1個(gè)有序記錄之間插入一個(gè)新記錄，使插入后的記錄序列仍為有序。在并向有序表中插入記錄時(shí)，如果通過(guò)“折半查找”來(lái)確定插入位置，這就是折半插入排序。希爾排序使用一個(gè)序列h1, h2, , ht，叫做增量序列（Increment Sequence）。

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

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

4、稱(chēng)為歸并（Merge）。若歸并的有序表有兩個(gè)，叫做二路歸并。對(duì)有序表反復(fù)利用歸并過(guò)程進(jìn)行排序的方法稱(chēng)為歸并排序（Merging Sort）。利用二路歸并操作的排序稱(chēng)為二路歸并排序。二路歸并排序的過(guò)程是：（1）把無(wú)序表中的每一個(gè)元素都看作是一個(gè)有序表，則有n個(gè)有序子表；（2）把n個(gè)有序子表按相鄰位置分成若干對(duì)（若n為奇數(shù)，則最后一個(gè)子表單獨(dú)作為一組），每對(duì)中的兩個(gè)子表進(jìn)行歸并，歸并后子表數(shù)減少一半；（3）反復(fù)進(jìn)行這一過(guò)程，直到歸并為一個(gè)有序表為止。四 實(shí)驗(yàn)設(shè)備、儀器、工具與資料 微機(jī)、VC五 實(shí)驗(yàn)內(nèi)容根據(jù)鍵盤(pán)輸入的數(shù)據(jù)建立一個(gè)待排序表，利用C語(yǔ)言設(shè)計(jì)一個(gè)主程序完成下列排序運(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頁(yè)中的算法7-17-10，為完成實(shí)驗(yàn)任務(wù)做好準(zhǔn)備。（2）實(shí)驗(yàn)步驟1）問(wèn)題分析。充分地分析和理解此實(shí)驗(yàn)任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫(xiě)出每個(gè)子程序（過(guò)程或函數(shù)）的規(guī)格說(shuō)明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計(jì)。3）詳細(xì)設(shè)計(jì)。詳細(xì)設(shè)計(jì)的目的是對(duì)子程序（過(guò)程或函數(shù)）的進(jìn)一步求精。用 IF 、WHILE和賦值語(yǔ)句等，以及自然語(yǔ)言寫(xiě)出算法的框架。利用自然語(yǔ)言的目的是避免陷入細(xì)節(jié)。4）編碼。在詳細(xì)設(shè)計(jì)的基礎(chǔ)上，對(duì)詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精，用C語(yǔ)言表示出來(lái)。5）在VC環(huán)境下調(diào)試程序。七 實(shí)驗(yàn)報(bào)告要求實(shí)驗(yàn)報(bào)告包含程序開(kāi)發(fā)過(guò)程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說(shuō)明：?jiǎn)栴}描述，求解的問(wèn)題是什么。2）概要設(shè)計(jì)：本程序所用的數(shù)據(jù)類(lèi)型定義；主程序流程；程序模塊及相互關(guān)系。3）詳細(xì)設(shè)計(jì)：采用C語(yǔ)言定義的數(shù)據(jù)