算法分析教(學(xué))案設(shè)計(jì)實(shí)驗(yàn)報(bào)告

1、.*院系：計(jì)算機(jī)科學(xué)學(xué)院專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù).專業(yè)學(xué)習(xí)資料.年級(jí)：課程名稱 ： 算法設(shè)計(jì)與分析基礎(chǔ)班號(hào)：組號(hào)：指導(dǎo)教師 ：年月日學(xué)號(hào)姓名組員實(shí)驗(yàn)名稱算法實(shí)驗(yàn)整體框架的構(gòu)建實(shí)驗(yàn)室.專業(yè)學(xué)習(xí)資料.1.實(shí)驗(yàn)題目算法實(shí)驗(yàn)主菜單的設(shè)計(jì)。2 實(shí)驗(yàn)?zāi)康?熟悉實(shí)驗(yàn)環(huán)境VC 6.0； 復(fù)習(xí) C、 C+ 語(yǔ)言以及數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí)，實(shí)現(xiàn)課程間的平滑過(guò)度；3.實(shí)驗(yàn)要求1）設(shè)計(jì)的主菜單可以是圖形模式的，也可以是控制臺(tái)模式的。以控制臺(tái)為例，主菜單實(shí)大致如下 ：驗(yàn)?zāi)克惴ㄔO(shè)計(jì)與分析 實(shí)驗(yàn)的或1.算法分析基礎(chǔ) Fibonacci序列問(wèn)題要2.分治法在數(shù)值問(wèn)題中的應(yīng)用 最近點(diǎn)對(duì)問(wèn)題求3.減治法在組合問(wèn)題中的應(yīng)用 8 枚硬

2、幣問(wèn)題4. 變治法在排序問(wèn)題中的應(yīng)用 堆排序問(wèn)題5. 動(dòng)態(tài)規(guī)劃法在圖問(wèn)題中的應(yīng)用 全源最短路徑問(wèn)題99. 退出本實(shí)驗(yàn)請(qǐng)輸入您所要執(zhí)行的操作 （ 1 ， 2， 3 ，4， 5， 99 ）：2）點(diǎn)擊操作后進(jìn)入相應(yīng)的實(shí)驗(yàn)項(xiàng)目或是相應(yīng)項(xiàng)目的下一級(jí)菜單；3）可以反復(fù)執(zhí)行，直到退出實(shí)驗(yàn) 。.專業(yè)學(xué)習(xí)資料.程序代碼.void Meun()printf("nttn");printf("ntt算法設(shè)計(jì)與分析 實(shí)驗(yàn) n");printf("nttn");printf("ntt1、算法分析基礎(chǔ) Fibonacci 序列問(wèn)題 n");pr

3、intf("ntt2、分治法在數(shù)值問(wèn)題中的應(yīng)用 矩陣相乘問(wèn)題 n");printf("ntt3、減治法在組合問(wèn)題中的應(yīng)用 枚硬幣問(wèn)題 n");printf("ntt4、變治法在排序問(wèn)題中的應(yīng)用 堆排序問(wèn)題 n");Printf("ntt4、動(dòng)態(tài)規(guī)劃法在圖問(wèn)題中的應(yīng)用 全源最短路徑問(wèn)題n");動(dòng)態(tài)規(guī)劃法在圖問(wèn)題中的應(yīng)用 全源最短路徑問(wèn)題printf("ntt99、退出本實(shí)驗(yàn) n");printf("ntt");printf("ntt請(qǐng)輸入您所要執(zhí)行的操作（ 1， 2，

4、3 ，4，5 ，99 ）： ");void main()int a;while(1)Meun();/ 調(diào)用菜單函數(shù)顯示菜單scanf("%d",&a);switch(a)case 1:printf("nttFibonacci序列問(wèn)題 ttn");fibonacci();break;case 2:printf("ntt 分治法在數(shù)值問(wèn)題中的應(yīng)用 矩陣相乘問(wèn)題 ttn"); matrix();break;case 3:printf("ntt 減治法在組合問(wèn)題中的應(yīng)用 8 枚硬幣問(wèn)題 ttn"); CO

5、INFAKE();break;case 4:.專業(yè)學(xué)習(xí)資料.printf("ntt 變治法在排序問(wèn)題中的應(yīng)用 堆排序問(wèn)題 ttn"); HEAP();break;case 5:printf("ntt 動(dòng)態(tài)規(guī)劃法在圖問(wèn)題中的應(yīng)用 全源最短路徑問(wèn)題 ttn"); break;case 99:printf(" 你選擇退出本實(shí)驗(yàn)n " );exit(0);實(shí)驗(yàn)結(jié)果及分析.專業(yè)學(xué)習(xí)資料.算法分析基礎(chǔ) Fibonacci序列實(shí)驗(yàn)名稱實(shí)驗(yàn)室問(wèn)題.專業(yè)學(xué)習(xí)資料.實(shí)驗(yàn)題目給定一個(gè)非負(fù)整數(shù)n，計(jì)算第 n 個(gè) Fibonacci數(shù)實(shí)驗(yàn)?zāi)康? ）理解遞歸算法

6、和迭代算法的設(shè)計(jì)思想以及遞歸程序的調(diào)式技術(shù)2 ）掌握并應(yīng)用遞歸算法和迭代算法效率的理論分析(前驗(yàn)分析 )和實(shí)際分析 (后驗(yàn)分析 )實(shí)方法；驗(yàn)3 ）理解這樣一個(gè)觀點(diǎn)：不同的算法可以解決相同的問(wèn)題，這些算法的解題思路不目同，復(fù)雜程度不同，效率也不同 ；的或?qū)嶒?yàn)要求要1 ）使用教材2.5 節(jié)中介紹的迭代算法Fib(n), 找出最大的n,使得第 n 個(gè) Fibonacci求數(shù)不超過(guò)計(jì)算機(jī)所能表示的最大整數(shù)，并給出具體的執(zhí)行時(shí)間；2 ）對(duì)于要求1),使用教材2.5 節(jié)中介紹的遞歸算法F(n)進(jìn)行計(jì)算 ,同樣給出具體的執(zhí)行時(shí)間，并同 1)的執(zhí)行時(shí)間進(jìn)行比較；3 ）對(duì)于輸入同樣的非負(fù)整數(shù)n ，比較上述兩種算

7、法基本操作的執(zhí)行次數(shù)；4 ）對(duì) 1)中的迭代算法進(jìn)行改進(jìn)，使得改進(jìn)后的迭代算法其空間復(fù)雜度為(1)；5 ）設(shè)計(jì)可供用戶選擇算法的交互式菜單(放在相應(yīng)的主菜單下)。.專業(yè)學(xué)習(xí)資料.專業(yè)學(xué)習(xí)資料.實(shí)驗(yàn)原理（算法基本思想）1 、遞歸法基本思想遞歸就是定義一個(gè)函數(shù)，讓它自己調(diào)用自己。Fib （int n ）/ 輸入整數(shù) n，輸出第 n 個(gè)斐波那契數(shù)if(n=0)return 0;Else if(n=1)return 1;Else return Fib(n-1)+Fib(n-2)2、迭代法這種方法相對(duì)于遞歸法來(lái)說(shuō)在時(shí)間復(fù)雜度上減小了不少，但代碼相對(duì)就要復(fù)雜些了。Fib （int n ）/ 輸入整數(shù) n，

8、輸出第 n 個(gè)斐波那契數(shù)if(n=0)return 0;Else if(n=1)return 1;ElseF00;F11;for(i=2;i<n-2;i+)F2=f1+f0;/f1 表示當(dāng)前的值F0F1.專業(yè)學(xué)習(xí)資料.F1F2;Return F2;程序代碼int Fib(int i)if(i<2)return i;elsereturn Fib(i-1)+Fib(i-2);void DiGui()int f=0,i=0,t=0;double start,end;start=clock();while(2*t>=0)t=f;f=Fib(i);printf("%d&quo

9、t;,f);i+;printf("n計(jì)算機(jī)最大可表示第%d 個(gè)斐波拉契數(shù) n",i);end=clock();printf(" 運(yùn)行時(shí)間為 %f秒 n",(end-start)/1000);void DieDai()long shu3,count;.專業(yè)學(xué)習(xí)資料.double start,end;start=clock();shu0=0;shu1=1;printf("%ld",shu0);for(count=1;shu1>=shu0;count+)printf("%ld",shu1);shu2=shu1+sh

10、u0;shu0=shu1;shu1=shu2;printf("n計(jì)算機(jī)最大可表示第%d 個(gè)斐波拉契數(shù) n",count);end=clock();printf(" 運(yùn)行時(shí)間為 %f毫秒 n",end-start);void Fibonacci()printf("n迭代算法 ：n");DieDai();printf("n遞歸算法 ：n");DiGui();.專業(yè)學(xué)習(xí)資料.實(shí)驗(yàn)結(jié)果通過(guò)比較兩種方法求Fibonacci 數(shù)列所用的時(shí)間 ，可以發(fā)現(xiàn)迭代法的效率明顯及高于遞歸法 。 同時(shí)也明白了不同的算法可以解決相同的問(wèn)題，

11、這些算法的解分題思路不同 ，復(fù)雜程度不同 ，效率也不同 。析分治法在數(shù)值問(wèn)題中的應(yīng)用實(shí)驗(yàn)名稱實(shí)驗(yàn)室 矩陣相乘問(wèn)題.專業(yè)學(xué)習(xí)資料.實(shí)驗(yàn)題目設(shè) M 1 和 M 2 是兩個(gè) n×n 的矩陣 ，設(shè)計(jì)算法計(jì)算 M 1×M 2 的乘積 。實(shí)驗(yàn)?zāi)康? ）提高應(yīng)用蠻力法設(shè)計(jì)算法的技能；實(shí)2 ）深刻理解并掌握分治法的設(shè)計(jì)思想；驗(yàn)3 ）理解這樣一個(gè)觀點(diǎn)：用蠻力法設(shè)計(jì)的算法，一般來(lái)說(shuō) ，經(jīng)過(guò)適度的努力后，都可目以對(duì)其進(jìn)行改進(jìn)，以提高算法的效率。的實(shí)驗(yàn)要求或1）設(shè)計(jì)并實(shí)現(xiàn)用BF 方法求解矩陣相乘問(wèn)題的算法；要2）設(shè)計(jì)并實(shí)現(xiàn)用DAC 方法求解矩陣相乘問(wèn)題的算法；求3）以上兩種算法的輸入既可以手動(dòng)輸入

12、，也可以自動(dòng)生成 ；4）對(duì)上述兩個(gè)算法進(jìn)行時(shí)間復(fù)雜性分析，并設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)果 ；5）設(shè)計(jì)可供用戶選擇算法的交互式菜單(放在相應(yīng)的主菜單下 )。.專業(yè)學(xué)習(xí)資料.實(shí)驗(yàn)原理（算1）蠻力法求解蠻力法比較簡(jiǎn)單，直接使用矩陣相乘公式計(jì)算矩陣的每行每列的值，很容易就能得出答案2）分治法求解分治法思想法將問(wèn)題實(shí)例劃分為同一問(wèn)題的幾個(gè)較小的實(shí)例。對(duì)這些較小實(shí)例求解，通常使基用遞歸方法，但在問(wèn)題規(guī)模足夠小時(shí)，也會(huì)使用另一種算法。如果有必要，合并這些問(wèn)本思想）題的解 ，以得到原始問(wèn)題的解。求解矩陣相乘的DAC 算法 ，使用了 strassen 算法 。DAC （ A ， B，n ）If n=2使用 7 次乘

13、法的方法求得解ElseDivide （A ） / 把 A 分成 4 塊Divide （B） / 把 B 分成 4 塊調(diào)用 7 次 strassen 算法求得解的4 塊合并這 4 塊得到解并返回.專業(yè)學(xué)習(xí)資料./ 矩陣相乘問(wèn)題void matric(int n,float ANN,float BNN,float CNN)LARGE_INTEGER startTime;LARGE_INTEGER endTime;QueryPerformanceCounter(&startTime);int i,j,k;for(i=0;i<n;i+)for(j=0;j<n;j+)Cij=0;fo

14、r(i=0;i<n;i+)for(j=0;j<n;j+)for(k=0;k<n;k+)Cij+=Aik*Bkj;QueryPerformanceCounter(&endTime);LARGE_INTEGER totalTime;程totalTime.QuadPart = endTime.QuadPart - startTime.QuadPart; printf("%ldn", totalTime.QuadPart);序代碼void MATRIX_MULTIPLY(float AN,float BN,float CN)/ 按通常的矩陣乘法計(jì)算C=AB

15、 的子算法(僅做 2階)int i,j,t;for(i=0;i<2;i+)/ 計(jì)算 A*B->Cfor(j=0;j<2;j+)Cij=0;/ 計(jì)算完一個(gè) Cij ， Cij 應(yīng)重新賦值為零for(t=0;t<2;t+)Cij=Cij+Ait*Btj;void MATRIX_ADD(int n,float XN,float YN,float ZN) /矩陣加法函數(shù) X+Y >Zint i,j;for(i=0;i<n;i+)for(j=0;j<n;j+).專業(yè)學(xué)習(xí)資料.Zij=Xij+Yij;void MATRIX_SUB(int n,float XN,f

16、loat YN,float ZN) /矩陣減法函數(shù) X-Y >Zint i,j;for(i=0;i<n;i+)for(j=0;j<n;j+)Zij=Xij-Yij;void STRASSEN(int n, float AN, float BN, float CN)float A11NN, A12NN, A21NN, A22NN;float B11NN, B12NN, B21NN, B22NN;float C11NN, C12NN, C21NN, C22NN;float m1NN, m2NN,m3NN, m4NN, m5NN, m6NN,m7NN; float AANN, BB

17、NN, MM1NN,MM2NN;int i, j;if (n=2)MATRIX_MULTIPLY(A, B, C);elsefor (i=0; i<n/2; i+)for (j=0; j<n/2; j+)A11ij = Aij;A12ij = Aij+n/2;A21ij = Ai+n/2j;A22ij = Ai+n/2j+n/2;B11ij = Bij;B12ij = Bij+n/2;B21ij = Bi+n/2j;B22ij = Bi+n/2j+n/2;MATRIX_ADD(n/2, A11, A22, AA);MATRIX_ADD(n/2, B11, B22, BB);STRA

18、SSEN(n/2, AA, BB, m1);MATRIX_ADD(n/2, A21, A22, AA);STRASSEN(n/2, AA, B11, m2);MATRIX_SUB(n/2, B12, B22, BB);STRASSEN(n/2, A11, BB, m3);.專業(yè)學(xué)習(xí)資料.MATRIX_SUB(n/2, B21, B11, BB);STRASSEN(n/2, A22, BB, m4);MATRIX_ADD(n/2, A11,A12, AA);STRASSEN(n/2, AA, B22, m5);MATRIX_SUB(n/2, A21, A11, AA);MATRIX_ADD(n/

19、2, B11, B12, BB);STRASSEN(n/2, AA, BB, m6);MATRIX_SUB(n/2, A12, A22, AA);MATRIX_ADD(n/2, B21, B22, BB);STRASSEN(n/2, AA, BB, m7);MATRIX_ADD(n/2, m1, m4, MM1);MATRIX_SUB(n/2, m5, m7, MM2);MATRIX_SUB(n/2, MM1, MM2, C11);MATRIX_ADD(n/2, m3, m5, C12);MATRIX_ADD(n/2, m2, m4, C21);MATRIX_ADD(n/2, m1, m3,

20、MM1);MATRIX_SUB(n/2, m2, m6, MM2);MATRIX_SUB(n/2, MM1, MM2, C22);for (i=0; i<n/2; i+)for (j=0; j<n/2; j+)Cij = C11ij;Cij+n/2 = C12ij;Ci+n/2j = C21ij;Ci+n/2j+n/2 = C22ij; / else finishedvoid SHUru(int n,float ANN,float BNN)int i,j;printf(" 請(qǐng)輸入 A 數(shù)據(jù)：n"); for(i=0;i<n;i+) for(j=0;j<

21、;n;j+)scanf("%f",&Aij);printf(" 請(qǐng)輸入 B數(shù)據(jù)： n");.專業(yè)學(xué)習(xí)資料.for(i=0;i<n;i+)for(j=0;j<n;j+)scanf("%f",&Bij);void SHUIji(int n,float ANN,float BNN)int i,j; for(i=0;i<n;i+) for(j=0;j<n;j+)Aij=(float)(n*rand()/(RAND_MAX+1.0) ;printf(" 數(shù)組 A 中數(shù)據(jù)為 ： n");

22、for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%4f",Aij);printf("n");for(i=0;i<n;i+)for(j=0;j<n;j+)Bij=(float)(n*rand()/(RAND_MAX+1.0) ;printf(" 數(shù)組 B中數(shù)據(jù)為 ： n");for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%4f",Bij);printf("n");void print1(int n,flo

23、at CNN).專業(yè)學(xué)習(xí)資料.int i ,j;printf(" 結(jié)果數(shù)組 C中數(shù)據(jù)為 ：n");for(i=0;i<n;i+)for(j=0;j<n;j+)printf("%4f",Cij);printf("n");void Jz() int n;float ANN,BNN,CNN;int i,j;printf(" 本程序用于計(jì)算M1 ×M2的乘積 n");printf(" 輸入矩陣階數(shù) n:n");scanf("%d",&n);char fl

24、ag;for(i=0;i<n;i+)for(j=0;j<n;j+)Cij=0;printf("-1手動(dòng)輸入 -n");printf("-2自動(dòng)生成 -n");printf("-3確定-n");while(1)printf(" 請(qǐng)輸入選擇 nn");fflush(stdin);flag=getch();switch(flag) case '1':printf(" 手動(dòng)輸入n");SHUru(n,A,B);printf("n");break;case

25、'2':printf(" 自動(dòng)生成n");SHUIji(n,A,B);printf("n");break;case '3':goto con;default:.專業(yè)學(xué)習(xí)資料.printf(" 按鍵錯(cuò)誤 n");con:printf("-1用 BF方法 -n");printf("-2用 DAC 方法-n");printf("-3結(jié)束 -n");while(1)printf(" 請(qǐng)輸入選擇 nn");fflush(stdin);

26、flag=getch();switch(flag) case '1':matric(n,A,B,C);printf(" 用 BF方法得出的結(jié)果n");print1(n,C);printf("n");break;case '2':STRASSEN(n,A,B,C);printf(" 用DAC 方法得出的結(jié)果n");print1(n,C);printf("n");break;case '3':return;default:printf(" 按鍵錯(cuò)誤 n"

27、;);.專業(yè)學(xué)習(xí)資料.實(shí)驗(yàn)結(jié)果及分析經(jīng)過(guò)這個(gè)實(shí)驗(yàn) ，我明白了蠻力法幾乎可以解決所有的問(wèn)題，但是算法的效率不高。對(duì)蠻力法進(jìn)行改進(jìn) ，經(jīng)過(guò)適當(dāng)?shù)呐?，算法的效率可以得到提高。.專業(yè)學(xué)習(xí)資料.減治法在組合問(wèn)題中的應(yīng)用8枚實(shí)驗(yàn)名稱實(shí)驗(yàn)室硬幣問(wèn)題實(shí)驗(yàn)題目在 8 枚外觀相同的硬幣中，有一枚是假幣，并且已知假幣與真幣的重量不同，但不知道假幣與真幣相比較輕還是較重。可以通過(guò)一架天平來(lái)任意比較兩組硬幣，設(shè)計(jì)一個(gè)高效的算法來(lái)檢測(cè)這枚假幣。實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康哪? ）深刻理解并掌握減治法的設(shè)計(jì)思想并理解它與分治法的區(qū)別；的2 ）提高應(yīng)用減治法設(shè)計(jì)算法的技能?；? ）理解這樣一個(gè)觀點(diǎn)：建立正角的模型對(duì)于問(wèn)題的求解是非常重

28、要的。要求實(shí)驗(yàn)要求1 ）設(shè)計(jì)減治算法實(shí)現(xiàn)8 枚硬幣問(wèn)題 ；2 ）設(shè)計(jì)實(shí)驗(yàn)程序，考察用減治技術(shù)設(shè)計(jì)的算法是否高效；3 ）擴(kuò)展算法 ，使之能處理n 枚硬幣中有一枚假幣的問(wèn)題。.專業(yè)學(xué)習(xí)資料.實(shí)驗(yàn)原理（算法基本思想）.減治法主要有三種變種減去一個(gè)常量減去一個(gè)常量因子減可變規(guī)模與分治法的區(qū)別：分治法把實(shí)例分為幾部分分別求解減治法把實(shí)例的規(guī)模減為一個(gè)更小的實(shí)例求解A（ n ） / 輸入硬幣個(gè)數(shù)n，要求必須有假幣且已知假幣只有1 個(gè)（假設(shè)更重 ）if n=1, 這枚就是假幣Else if n=2 ，較重的那枚是假幣Else把 n 個(gè)硬幣分為 3 份， 2 份相等 ，另一份與這 2 份的相差個(gè)數(shù)盡可能小稱

29、2 份個(gè)數(shù)相等的If 這 2 份重量相等 ，假幣在第3 堆中 ，對(duì)第 3 堆使用該算法Else 在較重的那堆中，對(duì)該堆硬幣使用該算法.專業(yè)學(xué)習(xí)資料.程序代碼./ 假幣問(wèn)題void FakeCoin_1(int coin,int n,int l,int h)int i,ps,sum1,sum2;if(n=2)printf(" 不能判斷真假 。.");elseif(l=h)printf(" 第%d 枚硬幣是假的 ，它的重量是 %d。 ",l,coinl);elseif(h-l=1)if(l>1)if(coinl=coin1)printf("

30、第%d 枚硬幣是假的 ，它的重量是 %d 。 ",h,coinh);elseprintf(" 第%d 枚硬幣是假的 ，它的重量是 %d。 ",l,coinl);elseif(h<n)if(coinh=coinn)printf(" 第 %d枚硬幣是假的 ，它的重量是 %d 。",l,coinl);elseprintf(" 第 %d枚硬幣是假的 ，它的重量是 %d 。",h,coinh);elseif(l<h)ps=(h-l+1)/3;sum1=0;sum2=0;for(i=1;i<=ps;i+)sum1+=c

31、oinl+i-1;sum2+=coinh-i+1;if(sum1=sum2)FakeCoin_1(coin,n,l+ps,h-ps);elseif(sum1=coinl+ps*ps)FakeCoin_1(coin,n,h-ps+1,h);.專業(yè)學(xué)習(xí)資料.elseFakeCoin_1(coin,n,l,l+ps-1);void FakeCoin()int i=1,n, coin100;printf(" 請(qǐng)輸入硬幣的個(gè)數(shù): ");scanf("%d",&n);printf(" 請(qǐng)輸入硬幣的重量:n");for(i=1;i<=

32、n;i+)scanf("%d",&coini);FakeCoin_1(coin,n,1,n);實(shí)驗(yàn)結(jié)果及分析通過(guò)這個(gè)實(shí)驗(yàn)，理解并掌握了減治法的設(shè)計(jì)思想并理解了它與分治法的區(qū)別。在寫這個(gè)算法前 ，一定要建立正確的求解模型。.專業(yè)學(xué)習(xí)資料.變治法在排序問(wèn)題中的應(yīng)用 堆排實(shí)驗(yàn)名稱實(shí)驗(yàn)室序問(wèn)題實(shí)驗(yàn)?zāi)康幕蛞髮?shí)驗(yàn)題目用基于變治法的堆排序算法對(duì)任意一組給定的數(shù)據(jù)進(jìn)行排序?qū)嶒?yàn)?zāi)康?）深刻理解并掌握變治法的設(shè)計(jì)思想；2）掌握堆的概念以及如何用變治法把任意給定的一組數(shù)據(jù)改變成堆；3）提高應(yīng)用變治法設(shè)計(jì)算法的技能。實(shí)驗(yàn)要求1）設(shè)計(jì)與實(shí)現(xiàn)堆排序算法；2）待排序的數(shù)據(jù)可以手工輸入(通常規(guī)模

33、比較小， 10 個(gè)數(shù)據(jù)左右 ）， 用以檢測(cè)程序的正確性 ；也可以計(jì)算機(jī)隨機(jī)生成（通常規(guī)模比較大， 1500 3000 個(gè)數(shù)據(jù)左右 ）， 用以檢驗(yàn)(用計(jì)數(shù)法 )堆排序算法的時(shí)間效率。.專業(yè)學(xué)習(xí)資料.實(shí)堆排序利用了大根堆(或小根堆 )堆頂記錄的關(guān)鍵字最大(或最小 )這一特征 ，使得在當(dāng)前驗(yàn)無(wú)序區(qū)中選取最大(或最小 )關(guān)鍵字的記錄變得簡(jiǎn)單。原(1)用大根堆排序的基本思想理（ 2 ）大根堆排序算法的基本操作（算法基本思特點(diǎn) :堆排序 (HeapSort) 是一樹形選擇排序。堆排序的特點(diǎn)是：在排序過(guò)程中 ，將 Rl.n看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系

34、(參見(jiàn)二叉樹的順序存儲(chǔ)結(jié)構(gòu))，在當(dāng)前無(wú)序區(qū)中選擇關(guān)鍵字最大(或最小 )的記錄堆排序的最壞時(shí)間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。想）它是 不穩(wěn)定 的排序方法。.專業(yè)學(xué)習(xí)資料.程序代碼./ 堆排序void Dui_1(int h,int n) int heap,i,k,v,j;for(i=(n/2);i>0;i-) k=i;v=hk;heap=0;while(heap=0)&&(2*k<=n) j=2*k; if(j<n) if(hj<hj+1) j=j+1;if(v>hj)heap=1;else hk=hj;k=j;hk=v;void Dui() int aM,i,n,m,t,choice;printf(" 輸入要排序的個(gè)數(shù)n： ");scanf("%d",&n);while(1)printf("n 1.自動(dòng)生成2.手動(dòng)輸入3.結(jié)束 n");scanf("%d",&choice);switch(choice)case 1:for(i=1;i<=n;i+)ai=rand();printf(" 產(chǎn)生的隨機(jī)數(shù)為:");fo