北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)四

北京郵電大學(xué)信息與通信工程學(xué)院第1頁(yè)北京郵電大學(xué)電信工程學(xué)院第1頁(yè)2009級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)四——排序?qū)W生姓名：班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：2010/12/171．實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)選擇下面兩個(gè)題目之一，學(xué)習(xí)、實(shí)現(xiàn)、對(duì)比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。實(shí)驗(yàn)內(nèi)容：使用簡(jiǎn)單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：1、插入排序2、希爾排序3、冒泡排序4、快速排序5、簡(jiǎn)單選擇排序6、堆排序7、歸并排序8、基數(shù)排序（選作）9、其他要求：1、測(cè)試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動(dòng)）。3、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）4、對(duì)2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時(shí)間復(fù)雜度編寫測(cè)試main()函數(shù)測(cè)試線性表的正確性。2.程序分析2.1存儲(chǔ)結(jié)構(gòu)使用最簡(jiǎn)單的一維數(shù)組存儲(chǔ)待排序的數(shù)據(jù)。共使用兩個(gè)數(shù)組，一個(gè)用來(lái)存儲(chǔ)原始數(shù)據(jù)，一個(gè)用來(lái)存儲(chǔ)待排序數(shù)據(jù)。每次排序完畢，用原始數(shù)據(jù)更新一次待排序數(shù)據(jù)，保證每一次都對(duì)同一組數(shù)據(jù)排序。（圖略）2.2關(guān)鍵算法分析1.直接插入的改進(jìn)：在一般的直接插入中，關(guān)鍵碼每移動(dòng)一次就需要比較一次。在移動(dòng)的方面，優(yōu)化是比較困難的，因?yàn)閷?duì)靜態(tài)線性表的插入必然要帶來(lái)大量的移動(dòng)。但是，我們可以在比較上進(jìn)行一些優(yōu)化。在查找技術(shù)一張?jiān)鴮W(xué)過(guò)的“折半查找法”，在這里就可以照葫蘆畫瓢地運(yùn)用。一趟排序的偽代碼如下： 1.如果該元素大于處于其左側(cè)相鄰的元素則跳過(guò)該元素； 2.low=0，high=i； 3.循環(huán)直至low==high 3.1mid=(low+high)/2； 3.2如果當(dāng)前元素大于中值high=mid； 3.3否則low=mid+1； 4.當(dāng)前元素賦值給臨時(shí)變量； 5.將有序區(qū)中處于low位置及其右側(cè)的元素右移； 6.臨時(shí)變量置于low位置簡(jiǎn)單說(shuō)一下這里的折半查找與一般查找算法的區(qū)別。這里的查找，尤其是對(duì)無(wú)重復(fù)數(shù)據(jù)和大量數(shù)據(jù)的處理中，更多的時(shí)候是找不到完全相等的項(xiàng)的。所以忽略這種情況，每次查找都進(jìn)行到正常查找算法中查找失敗的情形。由于待選插入位置的數(shù)量為有序區(qū)項(xiàng)數(shù)加一，而在比較前加入的判斷可將插入位置為有序去最末端（既不需移動(dòng)）的情況特殊處理，所以實(shí)際待選插入位置數(shù)量與有序區(qū)項(xiàng)數(shù)相等，可用最終插入空當(dāng)?shù)挠覀?cè)元素下標(biāo)標(biāo)記查找位置?；谶@種思想，我們?cè)O(shè)計(jì)了這樣的算法。插入值小于中值時(shí)，mid作為新的上限；大于中值時(shí)，將mid+1作為新的下限。這樣可以保證待選插入空當(dāng)一直保持在mid左側(cè)，而且當(dāng)low==high時(shí)恰好可以指向最終插入位置。該算法時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度O(1)。2.冒泡排序的改進(jìn)在某趟排序中，如果需要進(jìn)行相鄰的連續(xù)交換，可以像插入排序那樣先集體右移，最后定位原始左側(cè)的數(shù)據(jù)。一趟排序的偽代碼如下：1.對(duì)無(wú)序區(qū)元素ai自左至右循環(huán) 1.1如果該元素小于處于其右側(cè)相鄰的元素則跳過(guò)該元素； 1.2當(dāng)前元素賦值給臨時(shí)變量； 1.3當(dāng)前元素右側(cè)相鄰元素左移； 1.4i++； 1.5循環(huán)直到臨時(shí)變量小于或等于當(dāng)前元素右側(cè)相鄰元素或已達(dá)序列尾部 1.5.1 1.5.2i++ 1.6臨時(shí)變量置于當(dāng)前位置；關(guān)于以上代碼，由于較易理解，這里就不做更多的說(shuō)明了。該算法時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度O(1)。3.快速排序的非遞歸算法及改進(jìn)一般來(lái)說(shuō)，遞歸算法由于傳遞參數(shù)和返回值的因素會(huì)影響效率，而且容易造成系統(tǒng)棧溢出，所以使用非遞歸算法會(huì)較好一些。另外，一趟排序中的軸值是始終不變的，不需要反復(fù)賦值，只需要先存入臨時(shí)變量，確定位置后再寫入即可。相關(guān)偽代碼如下：1.建立兩個(gè)棧，存儲(chǔ)子列頭尾，共用棧頂； 2.序列首尾相應(yīng)入棧； 3.循環(huán)直到棧空 3.1棧頂元素出棧，用i,first接受頭，j,last接收尾； 3.2首項(xiàng)賦值給軸值； 3.3無(wú)條件循環(huán) 3.3.1循環(huán)直至aj 3.3.1 3.3.3ai 3.3.4i++ 3.3.5循環(huán)直至ai 3.3.5.1i++ 3.3.6 3.3.7aj賦值給a 3.3.8j-- 3.4軸值賦值給ai； 3.5若軸值左側(cè)子列存在且大于一個(gè)元素 3.5.1 3.6若軸值右側(cè)子列存在且大于一個(gè)元素 3.6.1該算法時(shí)間復(fù)雜度為O(nlog2n)，空間復(fù)雜度O(1)。2.3其他.關(guān)于輸入除了系統(tǒng)自動(dòng)生成的三種數(shù)列外，程序設(shè)計(jì)了讓用戶手動(dòng)輸入的接口。這里用到了cin的容錯(cuò)機(jī)制，增強(qiáng)了程序的健壯性，并利用該容錯(cuò)機(jī)制接受結(jié)束符控制輸入結(jié)束，并返回輸入長(zhǎng)度。相關(guān)代碼如下：template<typenameT>intInput(T*a,intmaxsize){ intlength=0; while(1) { cin>>a[length]; if(cin.fail())//若輸入流讀入非數(shù)字字符 { cin.clear(); charc; cin>>c; cin.sync(); if(c=='#'&&length>0)//若讀入截止符且輸入有效數(shù)據(jù)非空 break; } else { length++; if(length==maxsize) break; } } returnlength;}3.程序運(yùn)行結(jié)果開(kāi)始數(shù)組初始化開(kāi)始數(shù)組初始化鍵盤讀入按鍵key?產(chǎn)生正序序列產(chǎn)生逆序序列產(chǎn)生隨機(jī)序列鍵盤讀入序列鍵盤讀入按鍵key?使用相應(yīng)算法進(jìn)行排序并統(tǒng)計(jì)時(shí)間打印比較次數(shù)、移動(dòng)次數(shù)及算法時(shí)間打印序列結(jié)束abcdelseia~gh測(cè)試結(jié)果：（規(guī)模n=10000）（注：該結(jié)果為PentiumDualCore1.73GHz上省電模式下測(cè)得的數(shù)據(jù)）正序序列比較次數(shù)移動(dòng)次數(shù)時(shí)間(ms)插入排序999900希爾排序12000500冒泡排序999900快速排序5000499919998704簡(jiǎn)單選擇排序4999500029997875堆排序24457639586816歸并排序13632014000016逆序序列比較次數(shù)移動(dòng)次數(shù)時(shí)間(ms)插入排序13361650014998766希爾排序24344424689115冒泡排序50005000500149981265快速排序5000499924998703簡(jiǎn)單選擇排序4999500029997922堆排序22672035008815歸并排序13632014000016隨機(jī)序列比較次數(shù)移動(dòng)次數(shù)時(shí)間(ms)插入排序12895324934235390希爾排序31010737790215冒泡排序49937479415868791547快速排序1725176524616簡(jiǎn)單選擇排序4999500029997875堆排序23555637297515歸并排序136320140000154.總結(jié)本次實(shí)驗(yàn)中遇到的問(wèn)題主要還是對(duì)循環(huán)條件的控制，由于寫代碼時(shí)幾乎完全沒(méi)有參考書上的代碼