用鏈表實現(xiàn)排序

1、2022級數(shù)據(jù)結(jié)構(gòu)實驗報告1. 實驗要求實驗?zāi)康?學(xué)習(xí)、實現(xiàn)、比照各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。 實驗內(nèi)容：使用鏈表實現(xiàn)下面各種排序算法，并進行比擬。排序算法：1、插入排序2、冒泡排序3、快速排序4、簡單項選擇擇排序5、其他要求：1、測試數(shù)據(jù)分成三類：正序、逆序、隨機數(shù)據(jù)2、對于這三類數(shù)據(jù)，比擬上述排序算法中關(guān)鍵字的比擬次數(shù)和移動次數(shù)其中關(guān)鍵字 交換計為3次移動。3、對于這三類數(shù)據(jù)，比擬上述排序算法中不同算法的執(zhí)行時間，精確到微秒選作4、對2和3的結(jié)果進行分析，驗證上述各種算法的時間復(fù)雜度編寫測試main函數(shù)測試線性表的正確性2. 程序分析2.1存儲結(jié)構(gòu)雙循環(huán)鏈

2、表:2.2關(guān)鍵算法分析1.算法設(shè)計思想：1冒泡排序：將數(shù)組 a0,1,?, n-1看做是垂直排列的，每個元素值看做該氣泡的重量，因為輕重量的氣泡不能在重重量之下，所以從最后一個氣泡開始和其前面一個比擬，假設(shè)下面的輕那么交換，如此反復(fù)直到所有輕氣泡都在上面，重的都在下面為止。2選擇排序：第一次循環(huán)從0的位置開始找所有元素中最小，與0位置元素交換？第i 次循環(huán)從 i-1 的位置開始往后找此時最小元素與i-1 元素交換，直到所有的都循環(huán)完。( 3) 插入排序： 像揭牌一樣， 設(shè)第一個元素是排好序的， 第二個元素和第一個元素比擬 找到它的位置?第 i 個元素和之前排好的 i-1 個元素比擬找到自己的位

3、置， 直到所有的元素都 排序完畢。( 4) 快速排序： 取第一個元素做基準(zhǔn)， 將所有元素分成左右兩局部， 用分治法分別對兩 邊排序，然后將兩邊分別排序好的兩組元素再按大小順序合并成一個數(shù)組。用鏈表做只要把數(shù)組換成鏈表就可以了，代碼的思想還是不變的。1) 插入排序：while(p!=front)m=p->data ;x+; / 用于計比擬次數(shù)的計數(shù)器if(m < p->prior->data )s=p->prior;while(s!=front&&s->data >m)s->next ->data =s->data ;

4、s=s->prior ; x+;y+;/ 用于計移動次數(shù)的計數(shù)器s->next ->data =m;y+; p=p->next ;2) 冒泡排序：while(p!=front)s=p;/s 表示本次排序無序元素的范圍p=front; r=front->next ; while(r!=s)x+;if(r->data >r->next ->data ) m=r->data ; r->data =r->next ->data ; r->next ->data =m; p=r;y+=3;r=r->next

5、;/相鄰元素進行比擬/元素交換3) 一趟快速排序：int pivot=p->data ;/選取基準(zhǔn)元素while(p!=q) while(p!=q)&&(q->data >=pivot) /右側(cè)掃描，查找小于軸值的元素(*x)+;q=q->prior ;p->data =q->data ;(*y)+;while(p!=q)&&(p->data <=pivot)/左側(cè)掃描，查找大于軸值的元素(*x)+; p=p->next ;q->data =p->data ;(*y)+;p->data =p

6、ivot;return p; / 返回軸值所在的位置4) 簡單項選擇擇排序：while(p!=front->prior )s=p;/假設(shè) s 所指元素是最小的r=s->next ;while(r!=front)/ 查找最小值的位置x+;if(r->data <s->data )s=r;r=r->next ;if(s!=p)/假設(shè)第一個就是最小元素，那么不用交換m=p->data ;p->data =s->data ;s->data =m;y+=3;p=p->next ;3. 程序運行結(jié)果1Q0*9b9610刁1MU£5

7、 2 : 2 = 2 G 2LT y 9 2 22 s2 ai2 «tf 5 :tr8 904I 52s53JI 8 35 s 326寸?。?ITT VKz.6®w _2 » t».2S7文 k c % h's L - T - G- 、-u 丄-£=<1 ;:b ，舊擻 據(jù)3；時歡2時穿時枚 LE戈.i-£K.ihHK4 t 4 -23lllytil I 1 - - -7 1 7_9 -« S 918 6079 S3& " 10 8 1 B ««1U9.84M1691001

8、001S1S0>罔J琵；運出2比-i =測34ssfftAfts結(jié)JW2A人雪也專速序單善DLl43徘冒 r= 決徒517y6 蚤 £ -務(wù)5 - 亂變£位假設(shè)£位: t73單9.41單典41單話 4 毀4 IE LL 43-3 女 3 3 聯(lián)t)摟-zT 靈2電丸2 3 : 耳2 晉聘冷橐£位I -E- 4 A 4 4舍 5 4 I ? I I ? I 5xll- 4 5? 7 2 7? 4 9 - ! 92 fi 改6 i 3 fc 62 5_= S 9 £111裁円1數(shù)73丿數(shù)73驚732 2 2 22專斤 丘黑E位4 豹"

9、;4 4 4rir 5 43 sxt 5 -«if 5 :fv 5 4 56 位 * £ 位 1 t、57r 6 .1 : 6 4單544單-15氣單9fl叫間數(shù)4 卜 ' 4-( 4寸夂43 ：' 3 QW32273一霍1Y靂11賤11漆11 tEhk運比 I 0人人垢也專速序單7位2位；位3( 5& 4 5 ynF 4 b-3- 1 5 可戈 :s 2 3 耳 1 £n 9 Jy 9 t 6V 8 0 95 4 54 5 firH 2 -®5i717v7 謫?5時S2對次乂対歡2運比2 測5-濟15_.石15_.鎭甞脣15 的

10、丄運比H運比.-運比I 列辭隹果仔底果笛臬麗果 排7 進選經(jīng) 機2入入腐泡序單舌由程序結(jié)果可以驗證：1各種排序算法的比擬次數(shù)和移動次數(shù)滿足它們時間復(fù)雜度的最好、最壞和平均情況，它們的性能如下：排序方法平均情況最好情況最壞情況插入排序0(n2)0(n)0(n2)冒泡排序0(n2)0(n)0(n2)快速排序O(nl og2 n)O(nlog 2n)0(n2)簡單項選擇擇排序0(n2)0(n2)0(n2)2 正序、逆序和隨機序列的結(jié)果都是快速排序比其他三種用的時間長，其他三種用的時 間相差不大。我認(rèn)為快速排序慢的原因一方面是它的比擬次數(shù)確實比其他三種的要多，另-方面由于它用到了遞歸，并且也調(diào)用了別的函數(shù)Partion函數(shù)，在調(diào)用函數(shù)時進出棧耗去了一些時間，使程序用時增加。4總結(jié)排序過程通常要進行以下兩種根本操作1關(guān)鍵碼之間的比擬 2移動;記錄從一個位置移動到另一個位置。所以在待排序的個數(shù)一定的情況下，算法的執(zhí)行時間主要消耗在關(guān)鍵碼之間的比擬和記錄的移動上，因此高效率的算法應(yīng)該盡可能少的關(guān)鍵碼比擬次數(shù)和記錄的移動 次數(shù)。評價排序算法的另一個主要指標(biāo)是執(zhí)行算法所需要的輔助存儲空間通過這次試驗我更好的體會到排序的各種方法以及其比擬所需的時間，對于不同的排序選擇可以更好的應(yīng)用。 對