實驗四-排序-實驗報告1/2數(shù)據(jù)結構實驗報告實驗名稱:實驗四排序學生姓名：班級:班內序號:學號：日期:2012年12月21日實驗要求題目2使用鏈表實現(xiàn)下面各種排序算法,并進行比較。排序算法:1、插入排序2、冒泡排序３、快速排序4、簡單選擇排序５、其他要求：1、測試數(shù)據(jù)分成三類:正序、逆序、隨機數(shù)據(jù)。2、對于這三類數(shù)據(jù)，比較上述排序算法中關鍵字的比較次數(shù)和移動次數(shù)（其中關鍵字交換計為3次移動）。實驗四-排序-實驗報告全文共19頁，當前為第1頁。3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時間,精確到微秒(選作）。實驗四-排序-實驗報告全文共19頁，當前為第1頁。4、對２和3的結果進行分析，驗證上述各種算法的時間復雜度。編寫測試maiｎ（）函數(shù)測試線性表的正確性.2、程序分析2．1存儲結構說明：本程序排序序列的存儲由鏈表來完成.其存儲結構如下圖所示。（1)單鏈表存儲結構:結點地址：1000HA［２］結點地址：1000H１080H……頭指針地址：1020HA［0]頭指針地址：1020H１0C０H……地址：1080HA［3］地址：1080HNＵLL……地址：10C0HA[1]地址：10C0H100０H……(2）結點結構sｔructNode實驗四-排序-實驗報告全文共19頁，當前為第2頁。{實驗四-排序-實驗報告全文共19頁，當前為第2頁。?ｉntdata;?Noｄｅ＊nexｔ;｝;示意圖：intdataNode*next intdataNode*next2。2關鍵算法分析一:關鍵算法（一）直接插入排序ｖｏiｄLinkSｏrt:：InｓｅrtSoｒt()直接插入排序是插入排序中最簡單的排序方法，其基本思想是：依次將待排序序列中的每一個記錄插入到一個已排好的序列中,直到全部記錄都排好序。（1）算法自然語言1.將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū),初始時有序區(qū)為待排序記錄序列中的第一個記錄，無序區(qū)包括所有剩余待排序的記錄;2.將無須去的第一個記錄插入到有序區(qū)的合適位置中,從而使無序區(qū)減少一個記錄，有序區(qū)增加一個記錄;3。重復執(zhí)行２,直到無序區(qū)中沒有記錄為止。（2)源代碼voiｄＬinkSort::IｎseｒｔSort() ?//從第二個元素開始,尋找前面那個比它大的{實驗四-排序-實驗報告全文共19頁，當前為第3頁。?Node*P=froｎt-＞next； ?／/要插入的節(jié)點的前驅實驗四-排序-實驗報告全文共19頁，當前為第3頁。?while(P—>nexｔ) {? Nodｅ＊S＝fｒont；??//用來比較的節(jié)點的前驅 ?whｉlｅ(1）? {???ＣoｍｐaｒｅＣount++; ??ｉｆ(Ｐ—〉next->daｔa〈Ｓ—〉nｅxt－>daｔa) ?／／P的后繼比S的后繼小則插入 ?｛?? ?iｎsert（P，S); ｂreak; ? } ??S=S—>nｅｘt； ??ｉf(S==P） ? ? ?//若一趟比較結束，且不需要插入? ?{? ?P=Ｐ－〉nｅｘt；實驗四-排序-實驗報告全文共19頁，當前為第4頁。 ?? breａk;}實驗四-排序-實驗報告全文共19頁，當前為第4頁。??｝?｝｝（3)時間和空間復雜度最好情況下，待排序序列為正序，時間復雜度為O（ｎ)。最壞情況下，待排序序列為逆序,時間復雜度為O（n２）。直接插入排序只需要一個記錄的輔助空間,用來作為待插入記錄的暫存單元和查找記錄的插入位置過程中的“哨兵”。直接插入排序是一種穩(wěn)定的排序方法.直接插入排序算法簡單容易實現(xiàn)，當序列中的記錄基本有序或帶排序記錄較少時，他是最佳的排序方法。但當待排序的記錄個數(shù)較多時,大量的比較和移動操作使直接插入排序算法的效率減低。rr1≤r2≤……≤ri-1riri+1……rn有序區(qū)無序區(qū)直接插入排序的基本思想插入到合適位置直接插入排序過程直接插入排序過程初始鍵值序列［12］1592063124第一趟排序結果［1215］92063124第二趟排序結果［91215］2063124第三趟排序結果［9121520］63124第四趟排序結果［69121520］3124第五趟排序結果［6912152031］24第六趟排序結果［691215202431］實驗四-排序-實驗報告全文共19頁，當前為第5頁。實驗四-排序-實驗報告全文共19頁，當前為第5頁。(二）冒泡排序vｏidLｉnkSort::ＢｕｂｂleSort（）冒泡排序是交換排序中最簡單的排序方法,其基本思想是：兩兩比較相鄰記錄的關鍵碼，如果反序則交換，直到沒有反序的記錄為止。本程序采用改進的冒泡程序。(１）算法自然語言1。將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū),初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄.2.對無序區(qū)從前向后依次將相鄰記錄的關鍵碼進行比較，若反序則交換,從而使得關鍵碼小的記錄向前移,關鍵碼大的記錄向后移(像水中的氣泡，體積大的先浮上來）。3。將最后一次交換的位置pos,做為下一趟無序區(qū)的末尾.４。重復執(zhí)行2和3，直到無序區(qū)中沒有反序的記錄。(2）源代碼voidLｉnｋSort:：BｕbblｅSort(）｛?Ｎode*P＝fｒont—〉next； 實驗四-排序-實驗報告全文共19頁，當前為第6頁。?while（P－＞ｎext)?//第一趟排序并查找無序范圍實驗四-排序-實驗報告全文共19頁，當前為第6頁。 ｛? CompａreＣｏunt＋+；? if（P－〉dａt(yī)a>P—>neｘt－〉datａ）?? sｗap（Ｐ，P－〉ｎeｘt）;? Ｐ=P－>next； }?Nｏde＊poｓ=P； Ｐ=fｒonｔ-〉nexｔ； whilｅ(poｓ！=front－〉ｎexｔ)?{??Node*bｏund=pos； ?ｐoｓ=ｆront－>next； wｈｉle（P－＞ｎext?。剑鈕unｄ）??｛? CoｍｐarｅCｏunt++;? if(P－>datａ>Ｐ—>next—〉dａｔａ）實驗四-排序-實驗報告全文共19頁，當前為第7頁。???｛實驗四-排序-實驗報告全文共19頁，當前為第7頁。 ? ?ｓwａｐ(P，P—＞nexｔ）;?? pｏs＝P－＞next;?? }? Ｐ=P－＞ｎeｘt； ?? ?} P=front－＞next; }｝（3）時間和空間復雜度在最好情況下，待排序記錄序列為正序,算法只執(zhí)行了一趟，進行了n－1次關鍵碼的比較，不需要移動記錄,時間復雜度為Ｏ（n)；在最壞情況下,待排序記錄序列為反序，時間復雜度為O（ｎ2)，空間復雜度為Ｏ(１). 冒泡排序是一種穩(wěn)定的排序方法.rrjrj+1ri+1≤……≤rn-1≤rn無序區(qū)有序區(qū)1≤j≤i-1已經位于最終位置起泡排序的基本思想反序則交換初始鍵值序列初始鍵值序列［5013559727384965］第一趟排序結果［13505527384965］97第二趟排序結果［1350273849］556597第三趟排序結果［13273849］50556597第四趟排序結果1327384950556597冒泡排序過程實驗四-排序-實驗報告全文共19頁，當前為第8頁。實驗四-排序-實驗報告全文共19頁，當前為第8頁。（三）快速排序voidLｉnｋＳｏrt：:Ｑｓorｔ（）(1）算法自然語言1.首先選一個軸值(即比較的基準），將待排序記錄分割成獨立的兩部分，左側記錄的關鍵碼均小于或等于軸值，右側記錄的關鍵碼均大于或等于軸值。２．然后分別對這兩部分重復上述過程，直到整個序列有序。3。整個快速排序的過程遞歸進行。(2）源代碼ｖoiｄLinkSort::Ｑsort()｛ Nｏｄe*End=froｎt;?while（Ｅnd-＞ｎext） ｛??Eｎd=End－>nｅxｔ； ｝ Paｒtion(fronｔ，Enｄ);}ｖoidLinkSort：:Paｒｔion（Noｄｅ＊Stａrt,Nodｅ＊End)實驗四-排序-實驗報告全文共19頁，當前為第9頁。{實驗四-排序-實驗報告全文共19頁，當前為第9頁。?if（Start—〉ｎexｔ=＝Enｄ｜｜Staｒt==Ｅnｄ）?? /／遞歸返回??ｒeｔｕｒn；?Nodｅ＊Mｉd＝Ｓtart;??／／基準值前驅?Nｏde＊P=Mid－＞neｘt;?while(P!＝Eｎd&&P！=End-＞ｎexｔ） ｛ ＣompareCount++；? if(Miｄ->nexｔ-〉dａt(yī)ａ＞P-〉nexｔ－>ｄaｔａ）?/／元素值小于軸點值,則將該元素插在軸點之前 ?{? ?ｉf（P—＞ｎext＝=Enｄ)?? //若該元素為Eｎd，則將其前驅設為End ? End＝P; ??insert（P，Mid）; ?Mid=Mｉｄ->nexｔ；? }? elseＰ=Ｐ—>nｅｘt; }實驗四-排序-實驗報告全文共19頁，當前為第10頁。?Partｉon(Start，Mid）;?／/遞歸處理基準值左側鏈表實驗四-排序-實驗報告全文共19頁，當前為第10頁。 Parｔion(Ｍｉｄ-〉next，Ｅｎd）;?/／遞歸處理基準值右側鏈表｝(3）時間和空間復雜度在最好的情況下,時間復雜度為O(ｎlog2ｎ）。在最壞的情況下,時間復雜度為O（ｎ2)。 快速排序是一種不穩(wěn)定的排序方法.[[r1……ri-1]ri[ri+1……rn]均≤ri軸值均≥ri位于最終位置快速排序的基本思想圖解(四）簡單選擇排序基本思想為：第i趟排序通過n-ｉ次關鍵碼的比較,在n—i＋１(１≤i≤n—1）各記錄中選取關鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。（1)算法自然語言１．將整個記錄序列劃分為有序區(qū)和無序區(qū),初始狀態(tài)有序區(qū)為空，無序區(qū)含有待排序的所有記錄。2.在無序區(qū)中選取關鍵碼最小的記錄,將它與無序區(qū)中的第一個記錄交換，使得有序區(qū)擴展了一個記錄,而無序區(qū)減少了一個記錄。3。不斷重復2，直到無序區(qū)之剩下一個記錄為止。實驗四-排序-實驗報告全文共19頁，當前為第11頁。(2)源代碼實驗四-排序-實驗報告全文共19頁，當前為第11頁。voｉdLiｎkSｏrt：:ＳeｌectSorｔ(）｛?Noｄｅ＊S＝fｒoｎt； wｈilｅ(S—＞next—〉nｅxt）?｛??Ｎoｄe*P=Ｓ; ?Ｎodｅ*Min＝Ｐ; wｈｉle（Ｐ—〉next)／/查找最小記錄的位置??｛ ??ＣｏｍpａrｅCount＋+； ?if(P—〉nexｔ—>ｄatａ〈Min-＞nexｔ－>data)? ??Min＝Ｐ; ? P＝P-〉next；??｝??inｓeｒt（Miｎ，S)； S=S—＞ｎext；?}}實驗四-排序-實驗報告全文共19頁，當前為第12頁。實驗四-排序-實驗報告全文共19頁，當前為第12頁。(３）時間和空間復雜度簡單選擇排序最好、最壞和平均的時間復雜度為O(n2）。簡單選擇排序是一種不穩(wěn)定的排序方法.初始鍵值序列初始鍵值序列［49276597761338］第一趟排序結果13［276597764938］第二趟排序結果1327［6597764938］第三趟排序結果132738［97764965］第四趟排序結果13273849［769765］第五趟排序結果1327384965［9776］第六趟排序結果13273849657697簡單選擇排序的過程示例（五）輸出比較結果函數(shù)（含計算函數(shù)體執(zhí)行時間代碼)(1）算法自然語言１、依次調用直接插入排序、冒泡排序、快速排序、簡單選擇排序的函數(shù)體，進行序列的排序，并輸出相應的比較次數(shù)、移動次數(shù)。2、獲取當前系統(tǒng)時間。在調用函數(shù)之前設定一個調用代碼前的時間，在調用函數(shù)之后再次設定一個調用代碼后的時間，兩個時間相減就是代碼運行時間。說明:運用QuerｙPerformanceＦreｑｕｅｎcy（)可獲取計時器頻率；QuｅｒyPerformaｎceCounter(）用于得到高精度計時器的值。實驗四-排序-實驗報告全文共19頁，當前為第13頁。實驗四-排序-實驗報告全文共19頁，當前為第13頁。(2）源代碼ｖoidprｉntＲｅsulｔ（ＬｉnkSort＆a，LｉnｋＳorｔ＆ｂ，LiｎｋSort&c，ＬinｋSorｔ＆ｄ){ _ＬARGE_INTEGERtｉｍe_ｓtａrt;//開始時間＿ＬARGE_IＮTEGERｔime_ｏｖｅｒ；/／結束時間ｄｏublｅｄqＦrｅq；//計時器頻率LＡＲＧE_ＩNTＥGERf;//計時器頻率QueryＰerfoｒmａnceＦｒeqｕｅnｃy(&f）；dqFreq=(dｏuble）f。QuaｄＰarｔ;ａ．print(）；dｏubｌeTimeＣoｕnt;?CoｍpａreCoｕnt=0;MoveCouｎｔ=0；TiｍeCｏunｔ=0； QuｅryＰerformanｃeCｏunteｒ（&time＿start）;／／記錄起始時間?a．ＩｎserｔＳort();?QueｒｙPeｒｆoｒmancｅCｏunteｒ（＆time_ｏｖer);//記錄結束時間 TimeCount＝((tｉｍe_oveｒ.ＱｕaｄＰａrt－time_stａrt.ＱuａｄＰaｒt）／dqFreq）*100000０；實驗四-排序-實驗報告全文共19頁，當前為第14頁。 cｏut〈<”排序結果：＂；a.print（）;實驗四-排序-實驗報告全文共19頁，當前為第14頁。 couｔ<＜＂1。插入。比較次數(shù):”〈〈setw(3）＜<CompareＣoｕnｔ〈<＂;移動次數(shù)：”<<sｅｔw（3）〈<MoveＣoｕnt〈<＂；時間："＜<TｉｍeCoｕnｔ<〈"uｓ"<<eｎdl； ＣompareCount=0;MovｅCount=０；ＴiｍｅCouｎｔ＝0； ＱuｅｒyＰerfｏrmancｅCounｔer（&time＿starｔ）;／/記錄起始時間?b．BuｂbleSｏrt()； QｕeryPerfoｒmancｅCoｕnter（＆tｉｍe_oｖeｒ)；/／記錄結束時間?TiｍeCｏｕnｔ＝（（time_ovｅr.ＱuadPart-ｔｉme＿starｔ。QuaｄPaｒt)/dqFreｑ）*1０00000； ｃｏｕt〈〈"2．冒泡.比較次數(shù)：”<＜seｔw（３)<〈ＣｏmpａｒeＣｏuｎt<〈";移動次數(shù)：＂<<sｅtw(3)<<MoveCounｔ<〈”；時間："〈〈TｉmeCount<〈＂uｓ"<〈enｄｌ; CompaｒeＣoｕnt=０;MoveＣount＝0；ＴｉｍeＣｏunｔ=０; ＱueryＰerformanｃeCoｕｎｔer（&time_ｓtart);／/記錄起始時間?c.Ｑsort(）；?QueryPｅｒformanceCoｕntｅｒ（&time＿over）；//記錄結束時間實驗四-排序-實驗報告全文共19頁，當前為第15頁。?ＴimeCount=(（ｔimｅ_oveｒ。ＱuaｄPaｒt-tｉme_start。QuadPart)/dqFreq)*10０0000;實驗四-排序-實驗報告全文共19頁，當前為第15頁。 cout<〈＂3?？焖佟１容^次數(shù)：＂<〈setw（３）〈〈CｏmpareCount＜〈＂；移動次數(shù)："＜<sｅtw(３）〈<MovｅCoｕnｔ〈<＂；時間:”＜<ＴｉｍeＣoｕnt〈<＂us"<<enｄｌ;?CoｍpareCｏuｎt=0；MovｅＣount=0；TimeCount=0; QueryPerｆｏrmaｎｃｅCounｔｅr(＆ｔime_staｒｔ）；//記錄起始時間?d．SelectSoｒt（）；?QueryPerｆormancｅCｏuｎtｅr(&time＿ｏvｅr）；//記錄結束時間?TiｍeCouｎt＝（（ｔime_ovｅｒ.QuaｄParｔ-time＿stａrt。QuadＰaｒt)/dqFrｅq)＊１０00000；?ｃoｕｔ＜〈”4。選擇。比較次數(shù)：”<＜setw(３)<<CｏmｐareCｏuｎt＜<”;移動次數(shù)：”〈<setw（3)〈<MｏveCount＜〈”；時間：＂〈<ＴimeCouｎt〈<”ｕｓ＂<＜eｎdl;｝(３)時間和空間復雜度時間復雜度Ｏ（1)（因為不包含循環(huán)體）。實驗四-排序-實驗報告全文共19頁，當前為第16頁。2。3其他實驗四-排序-實驗報告全文共19頁，當前為第16頁。排序方法平均情況最好情況最壞情況輔助空間直接插入排序Ｏ(ｎ2)O（n)O(n2）O（1)希爾排序O(nlｏg2n)～Ｏ(n２）O（ｎ1。3）O（n２)O（１)起泡排序O(n2）O(n)Ｏ（n2）Ｏ(1）快速排序O(nlog２ｎ)O(nlｏg2n）Ｏ（n２）O（log2n)~O（n）簡單選擇排序O（ｎ2）O(ｎ２）Ｏ(n2）O(1）堆排序O(nｌｏg2n)O(ｎlog2n）O（nloｇ2n）O（1）歸并排序O(ｎｌog2n）Ｏ（nlog２n）Ｏ（nlog２n）O（n）3、程序運行結果（1）程序流程圖開始開始輸入數(shù)據(jù)輸入數(shù)據(jù)順序數(shù)組