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

1、2022級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1. 實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康?學(xué)習(xí)、實(shí)現(xiàn)、比照各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。 實(shí)驗(yàn)內(nèi)容：使用鏈表實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比擬。排序算法：1、插入排序2、冒泡排序3、快速排序4、簡單項(xiàng)選擇擇排序5、其他要求：1、測試數(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ù)雜度編寫測試main函數(shù)測試線性表的正確性2. 程序分析2.1存儲(chǔ)結(jié)構(gòu)雙循環(huán)鏈

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

3、置， 直到所有的元素都 排序完畢。( 4) 快速排序： 取第一個(gè)元素做基準(zhǔn)， 將所有元素分成左右兩局部， 用分治法分別對(duì)兩 邊排序，然后將兩邊分別排序好的兩組元素再按大小順序合并成一個(gè)數(shù)組。用鏈表做只要把數(shù)組換成鏈表就可以了，代碼的思想還是不變的。1) 插入排序：while(p!=front)m=p->data ;x+; / 用于計(jì)比擬次數(shù)的計(jì)數(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+;/ 用于計(jì)移動(dòng)次數(shù)的計(jì)數(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、;/相鄰元素進(jìn)行比擬/元素交換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) 簡單項(xiàng)選擇擇排序：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è)第一個(gè)就是最小元素，那么不用交換m=p->data ;p->data =s->data ;s->data =m;y+=3;p=p->next ;3. 程序運(yùn)行結(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；時(shí)歡2時(shí)穿時(shí)枚 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琵；運(yùn)出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運(yùn)比 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時(shí)S2對(duì)次乂対歡2運(yùn)比2 測5-濟(jì)15_.石15_.鎭甞脣15 的

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