北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)四題目1

1、北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)四排序?qū)W生姓名：xxx班級(jí):xxx班內(nèi)序號(hào)：xx學(xué) 號(hào)：xxx口 期：2013 年 12 月 20 口1. 實(shí)驗(yàn)要求a. 實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)現(xiàn)k述實(shí)驗(yàn)內(nèi)容，學(xué)習(xí)、實(shí)現(xiàn)、對(duì)比各種排序算法，掌握各種排序算 法的優(yōu)劣，以及各種算法使用的情況。b. 實(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、其他2. 程序分析2.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)示意圖如下：aoala2a3a4a5a6a7a8a9順序數(shù)組存儲(chǔ)結(jié)構(gòu)2.2關(guān)鍵算法分析核心算法思想：

2、1. 利用教材講述的基本算法思想，實(shí)現(xiàn)七種排序算法，統(tǒng)計(jì)其運(yùn)行相關(guān)數(shù)據(jù)。2. 將數(shù)組名當(dāng)做地址傳入函數(shù)，實(shí)現(xiàn)快速調(diào)用和統(tǒng)計(jì)。使得程序代碼可讀性增、結(jié)構(gòu)更加優(yōu)化。關(guān)鍵算法思想描述和實(shí)現(xiàn)：關(guān)鍵算法1:實(shí)現(xiàn)七種算法的基本排序功能。1、插入排序：依次將待排序的序列中的每一個(gè)記錄插入到先前排序好的序列中，直到全部記錄排序完畢。2、希爾排序：先將整個(gè)序列分割成若干個(gè)子列，分別在各個(gè)子列屮運(yùn)用直接插入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。3、冒泡排序：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序記錄為止。4、快速排序：首先選擇一個(gè)基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)

3、，右支則大于基準(zhǔn)，然后對(duì)兩部分重復(fù)上述過程，直至整個(gè)序列排序完成。5、選擇排序：從待排序的記錄序列中選擇關(guān)鍵碼最小(或最大)的記錄并將它與序列中的第一個(gè)記錄交換位置;然后從不包括第一個(gè)位置上的記錄序列中選擇關(guān)鍵碼最小(或最大)的記錄并將它與序列屮的第二個(gè)記錄交換位置;如此重復(fù),直到序列屮只剩下一個(gè)記錄為止。6、堆排序：通過建立大根堆或者小根堆，取山根節(jié)點(diǎn)，反復(fù)調(diào)整堆使之保持大根堆或者小根堆，直至最后序列有序。7、歸并排序：將若干個(gè)有序序列兩兩歸并，直至所有待排序的記錄都在一個(gè)有序序列為止。c+實(shí)現(xiàn)：void insert(int r，int n)/直接插入排序，升序intcompare=0,m

4、ove=0;定義比較和移動(dòng)的系數(shù)并初始化為零，以下相同不再敘述for(int i=2;i<n;i+)將數(shù)組巾的數(shù)一個(gè)一個(gè)放入序列if(ri<ri-l)第一個(gè)位置當(dāng)做哨兵，從第二個(gè)開始，若后面的數(shù)不比前面的數(shù)大則將哨兵入列，較小的數(shù)作為新哨兵ro=ri;intj;for（j=i-l；roj<ruj；j-）若后面的數(shù)比哨兵大，則直接放進(jìn)數(shù)列，網(wǎng);move+;每進(jìn)行一次上移動(dòng)從操作則移動(dòng)加1rj+l=ro;compare+;每判斷一次比較加1cout«n 比較次數(shù)：n«compare«n 移動(dòng)次數(shù)：n«move«endl;void

5、shelllnsert(int r，int n)/希爾排序int compare=0，move=0;for(int d=n/2;d=l ;d=d/2)for(int i=d+l;i<n;i+)if(ri<ri-d)主要思想每次循環(huán)跨越的步子折半依次比較每一個(gè)下標(biāo)等差增忪的數(shù)列判斷，小的值放前而r0=ri;intj;for(j=i-d;j>0&&rf01<rjl;j=j-d)比較沒一個(gè)數(shù)列內(nèi)的元素ru+d=ru;ru+d=ro;move+;compare+;)cout«'比較次數(shù)：'compare«n 移動(dòng)次數(shù)：n

6、71;move«endl;void bubblesort(int rl，int n)/改進(jìn)后的冒泡排序int compare=0,move=0;int pos=n;wh i 1 e( pos! =0)判斷循環(huán)的結(jié)朿條件，下面會(huì)有介紹int bound=pos;pos=0;令pos初始化為0,之后如果沒有進(jìn)入循環(huán)修改其值則跳出while循環(huán)for(int i=l;i<bound-l;i+)bound力每次循環(huán)需要進(jìn)行的次數(shù)，因?yàn)榕藕眯虻脑夭恍枰龠M(jìn)行比較int i=first;int j=end;int pivot=ri;while(i<j)while(i<j)&a

7、mp;&(rfj>=pivot)右側(cè)掃瞄，大于哨兵的不動(dòng)ro=ri;ri=ri+l；ri+l=ro;pos=i+l;move+;compare+;cout«n 比較次數(shù)："comparecc” 移動(dòng)次數(shù)：n«move«endl;int partion(int r, int first, int end,int a,int b)/次快排頭尾哨兵頭在尾之前，即尚未遍歷數(shù)組a+;ri=rj;小小于哨兵的進(jìn)入哨兵b+;while(i<j)&&(rh<=pivot)進(jìn)行左側(cè)掃描，小于哨兵的寫入數(shù)組i+;a+;rul=rm；

8、否則，進(jìn)入哨兵b+；ri=pivot;哨兵入列return i;void qsort(int r，int i，int j)/運(yùn)用遞歸實(shí)現(xiàn)多次快排int pivotloc=partion(r，i，j，a，b); 依次分割排序區(qū)間qsort(r，i，pivotloc-1);qsort(r，pivotloc+1，j);/簡(jiǎn)單選擇排序void selectsort(int rj，int n)int compare=0，move=0;for(int i=l;i<n;i+)n前比較開始的元素為了判斷目前的元素是否為最小for(int j=i+1 ;j<n;j+)那當(dāng)前元素和之后的元素比較找出最

9、小當(dāng)前最小的元素并貼上標(biāo)記min=j;compare+；如果標(biāo)記被改變，就交換標(biāo)記改變前u位置的元素，否則標(biāo)記的元素即為最小不用改變r(jià)0=ri;ri=rmin;rlmin=ro;move+;)cout«n 比較次數(shù)：n«compare«n 移動(dòng)次數(shù)：n«move«endl;void sift(int r，int k,int m)/小根堆的篩選int i=k,j=2*i;while(j<=m) 循環(huán)結(jié)朿的條件，最后的子節(jié)點(diǎn)大于總結(jié)點(diǎn)if(j<m&&r|j>r|j+1)比較左右孩子的大小，并將j指向較小的孩子j+;

10、if(ri<ru)父節(jié)點(diǎn)比最大的子節(jié)點(diǎn)小則該堆建成，跳出循環(huán)break;else否則把父節(jié)點(diǎn)往下篩ro=ru；rjl=rfil;ri=r0;會(huì) 1=j;j=2*i;void heapsort(int r，int n)for(int i=n/2;i>=l;i)sift(r，i，n);for(int i=l;i<n;i+)序數(shù)列/小根堆排序從最后一個(gè)有字節(jié)點(diǎn)的節(jié)點(diǎn)開始建小根堆依次取出每一個(gè)小跟對(duì)的根節(jié)點(diǎn)，再重新篩，形成有rfol=rn-i+ll;rn-i+l=rl;rl=ro;sift(r，l，n-i);void merge(int r,int rl,int s,int m,in

11、t t,int *c,int *d) r 為要排序的數(shù)組，rl 為緩沖數(shù)組，s為第一個(gè)序列幵始的位賈，m為第一個(gè)序列的結(jié)束的位賈，t為第二個(gè)序列的結(jié)束 位置，c為比較次數(shù)的指針，d為移動(dòng)次數(shù)的指針int j=m+l;int k=s;while(i<=m&&j<=t)循環(huán)條件，兩個(gè)序列都不空if(rlij<ruj)將小數(shù)寫進(jìn)緩沖數(shù)組，小數(shù)對(duì)應(yīng)的序列比較值后一一位rlk+=ri+;(*d)+;elserlk+=rj+；(*d)+;(*c)+;if(i<=m)當(dāng)一個(gè)序列窮盡吋，將另一個(gè)序列抄進(jìn)緩沖數(shù)組while(i<=m)rlk+j=rli+j； (*d

12、)+;while(j<=t)rlk+=ru+；(*d)+;void mergepass(int r,int rl,int n,int h，int *c,int *d)將一個(gè)數(shù)組一次拆分成長(zhǎng)度不同的小數(shù)組再兩兩歸并int i=l;while(i<=n-2*h+1) h為本次小序列的長(zhǎng)度，當(dāng)能拆成兩個(gè)等長(zhǎng)的序列時(shí)，拆出該序列進(jìn)行歸并merge(r,rl,i,i+h-l,i+2*h-l, c, d);i+=2*h; 每次歸并完，序列長(zhǎng)度增加一倍，再次歸并if(i<n-h+l)當(dāng)只能拆出一個(gè)單位長(zhǎng)度的序列和一個(gè)殘缺序列時(shí)，只將第二個(gè)序列歸并到最人長(zhǎng)度nmerge(r,rl,i,i+h

13、-l ,n,c,d);else只能拆出一個(gè)殘序列時(shí)，只把該序列抄進(jìn)緩沖數(shù)組即可for(;i<=n;i+)rli=ri；(*d)+;void mergesort(int rl，int rlfljnt n)int compare=0,move=0;inth=l;起始拆分的序列長(zhǎng)度定義為一，即每個(gè)數(shù)都需要進(jìn)行比較while(h<n)依次展長(zhǎng)序列長(zhǎng)度進(jìn)行歸并mergepass(r,rl,n,h,&compare,&move);h=2*h;for(int i=l;i<=n;i+)將緩沖數(shù)纟li里的有序數(shù)寫進(jìn)原數(shù)姐ri=rli；move+；cout«"

14、比較次數(shù)：n«compare«u 移動(dòng)次數(shù)：”move«endl;關(guān)鍵算法2:獲取當(dāng)前系統(tǒng)吋間，精確到微秒，分別在代碼運(yùn)行前后調(diào)用記錄前后吋間，再相減即n得到代碼運(yùn)行時(shí)間。此處調(diào)用函數(shù)queryperformancecoimtero用于得到高精度計(jì)時(shí)器的值。時(shí)間復(fù)雜度與空間復(fù)雜度：理論分析可以得出各種排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度，如下表所示：排序方法平均情況最好情況最壞情況輔助空間直接插入排序o(z?2)om0("2)0(1)希爾排序o(nlog2”)o(，?2)0(/，3)0 (/?2)0(1)起泡排序o(n2)oo(n2)0(1)快速排序o(&#

15、171;log2")<9(wlogy?)0("2)0 (log2«)o(ft)簡(jiǎn)單選擇排序ogr)0(n2)ou2)0(1)堆排序0(rtl0g2/)0 («log2«)0 (/2log2n)0(1)歸并排序o(«iog2")<9(wlogy?)o(/zlog2h)om3.程序運(yùn)彳t結(jié)果順序數(shù)組排序和統(tǒng)計(jì)結(jié)束實(shí)際測(cè)試和分析:實(shí)際運(yùn)行結(jié)果如下:d:paixudebugpaixu.ex-1845嗥亂序序列為：數(shù)列為：1357890246 原逆序序列為：數(shù)列為：9876543210 原順序列為：數(shù)列為：01234567

16、89 亂序列直接插入排序：比較次數(shù)：9移動(dòng)次數(shù): 數(shù)列為：0123456789該過程用的時(shí)間為：u8.407us顛序列直接插入排序：比較次數(shù)：9移動(dòng)次數(shù): 數(shù)列為：0123456789 該過程用的時(shí)間為：157.349us反序列直接插入排序：比較次數(shù)：9移動(dòng)次數(shù): 數(shù)列為：0123456789 該過程用的時(shí)間為：196.219us亂序希爾排序：比較次數(shù)：22移動(dòng)次數(shù)：0 數(shù)列為：0123456789 該過程用的時(shí)間為：26. 5046us順序希爾排序：比較次數(shù)：22移動(dòng)次數(shù)：0 數(shù)列為：0123456789 該過程用的時(shí)間為：26.177us反序希爾排序：比較次數(shù)：22移動(dòng)次數(shù)：0 數(shù)列為：0

17、123456789 孩過程用的時(shí)間為：26.44l7us亂序冒泡排序：比較次數(shù)：9移動(dòng)次數(shù)：0 數(shù)列為：0123456789 該過程用的時(shí)間為：35. 2522ns順序冒泡排序：比較次數(shù)：9移動(dòng)次數(shù)：0 數(shù)列為：0123456789 該過程用的時(shí)間為：29.6293ns反序冒泡排序：比較次數(shù)：9移動(dòng)次數(shù)：0 數(shù)列為：0123456789 該過程用的時(shí)間為：32. 7943us亂序快速排序：數(shù)列為：0 1 2 3 4 5 6 7 8 9 該過程用的時(shí)間為：17. 5697ns |比轉(zhuǎn)次數(shù)：0移動(dòng)次數(shù)：0d:paixudebugpaixu.exe亂序快速排序：數(shù)列為：0 12 3 4 5 6 7

18、8 9 1亥過程用的時(shí)間為：17. 5697us 比較次數(shù)：0移動(dòng)次數(shù)：0術(shù)序快速排序：數(shù)列為：0123456789 該過程用的時(shí)間為：17.4226ns 比較次數(shù)：0移動(dòng)次數(shù)：0反序快速排序：數(shù)列為：0 1 2 3 4 5 6 7 8 9 核過程用的時(shí)間為：19.0852us 比較次數(shù)：0移動(dòng)次數(shù)：0簡(jiǎn)單選擇排序亂序列：比較次數(shù)：45移動(dòng)次數(shù)：0數(shù)列為：0123456789後過程用的時(shí)間為：36.4681us簡(jiǎn)單選擇排序順序列：比較次數(shù)：45移動(dòng)次數(shù)：0數(shù)列為：0123456789諒過程用的時(shí)間為：32.9639us筒單選擇排序逆序列：比較次數(shù)：45移動(dòng)次數(shù)：0數(shù)列為：0123456789該過程用的時(shí)間為：34.8507us亂序堆排序：數(shù)列為：9 8 7 6 5 4 3 2 1 0孩過程用的時(shí)間為：