數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

1、<p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　課程名稱： 數(shù)據(jù)結(jié)構(gòu) </p><p>　　設(shè)計(jì)題目： 排序算法實(shí)現(xiàn)及比較 </p><p>　　系 別： 計(jì)算機(jī)信

2、息工程學(xué)院 </p><p>　　專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　組 別： 第*組 </p><p>　　起止日期: 12 年 5 月 1 日 ~ 12

3、 年 6月 1 日 </p><p>　　指導(dǎo)教師: *** </p><p>　　計(jì)算機(jī)與信息工程學(xué)院二○一二年制</p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p><b>　　目 錄</b></p&g

4、t;<p><b>　　1.引言4</b></p><p><b>　　2.需求分析4</b></p><p><b>　　3.詳細(xì)設(shè)計(jì)4</b></p><p>　　3.1 直接插入排序4</p><p><b>　　3.2折半排序5<

5、/b></p><p>　　3.3 希爾排序6</p><p>　　3.4簡(jiǎn)單選擇排序6</p><p><b>　　3.5堆排序6</b></p><p><b>　　3.6歸并排序7</b></p><p><b>　　3.7冒泡排序9</

6、b></p><p><b>　　4.調(diào)試10</b></p><p>　　5.調(diào)試及檢驗(yàn)11</p><p>　　5.1 直接插入排序11</p><p>　　5.2折半插入排序11</p><p>　　5.3 希爾排序12</p><p>　　5.4簡(jiǎn)單

7、選擇排序12</p><p><b>　　5.5堆排序13</b></p><p>　　5.6歸并排序14</p><p>　　5.7冒泡排序14</p><p>　　6.測(cè)試與比較15</p><p>　　6.1調(diào)試步驟15</p><p><b>

8、　　6.2結(jié)論16</b></p><p>　　7.實(shí)驗(yàn)心得與分析16</p><p><b>　　8.附錄17</b></p><p>　　8.1直接插入排序17</p><p>　　8.2折半插入排序18</p><p>　　8.3希爾排序20</p>&

9、lt;p>　　8.4簡(jiǎn)單選擇排序22</p><p><b>　　8.5堆排序23</b></p><p>　　8.6歸并排序26</p><p>　　8.7冒泡排序29</p><p><b>　　8.8主程序30</b></p><p><b>

10、　　1.引言</b></p><p>　　伴隨著社會(huì)的發(fā)展，數(shù)據(jù)也變得越來(lái)越龐大。如何將龐大的數(shù)據(jù)進(jìn)行很好的排序，使用戶更加方便的查找資料，成了一件越來(lái)越重要的問(wèn)題。對(duì)于程序員來(lái)說(shuō)，這將是一個(gè)挑戰(zhàn)。</p><p>　　經(jīng)常查找資料的朋友都會(huì)知道，面對(duì)海量的資料，如果其查找的資料沒(méi)有進(jìn)行排序，那么其查找資料將會(huì)是一件非常痛苦的事情。針對(duì)這一問(wèn)題，我們自此通過(guò)一個(gè)課程設(shè)計(jì)來(lái)解決它

11、。</p><p>　　理論上排序算法有很多種，不過(guò)本課程設(shè)計(jì)只涉及到七種算法。這七種算法共包括：直接插入排序，折半插入排序，希爾排序，簡(jiǎn)單選擇排序，堆排序，歸并排序，冒泡排序。</p><p>　　本課程設(shè)計(jì)通過(guò)對(duì)這七種算法的運(yùn)行情況進(jìn)行對(duì)比，選擇最優(yōu)秀的算法來(lái)提供給用戶。希望通過(guò)我們的努力能給用戶解決一些問(wèn)題，帶來(lái)一些方便。</p><p><b>　

12、　2.需求分析</b></p><p>　　本課程題目是排序算法的實(shí)現(xiàn)，由于各方面的原因，本課程設(shè)計(jì)一共要設(shè)計(jì)七種排序算法。這七種算法共包括：直接插入排序，折半插入排序，希爾排序，簡(jiǎn)單選擇排序，堆排序，歸并排序，冒泡排序。七種排序各有獨(dú)到之處，因此我們要通過(guò)各種調(diào)試分析來(lái)比較其優(yōu)劣長(zhǎng)短。</p><p>　　為了小組分工的方便，我們特意把子函數(shù)寫(xiě)成Header File文件。這

13、樣操作不僅可以使小組分工更加簡(jiǎn)潔明了，還可以方便子函數(shù)的調(diào)用，更可以使寫(xiě)主函數(shù)時(shí)一目了然。</p><p>　　為了運(yùn)行時(shí)的方便，我們將七種排序方法進(jìn)行編號(hào)，其中1為直接插入排序，2為折半插入排序，3為希爾排序，4為簡(jiǎn)單選擇排序，5為堆排序，6為歸并排序，7為冒泡排序。通過(guò)這七種選項(xiàng)，可以讓用戶簡(jiǎn)單明了的去選擇使用哪一種排序方法。</p><p>　　本課程就是通過(guò)對(duì)5組占用內(nèi)存大小不同的

14、數(shù)據(jù)調(diào)試來(lái)測(cè)試這七種算法運(yùn)行的時(shí)間長(zhǎng)短，從中選擇面對(duì)不同大小的文件時(shí)，哪一種算法更為快捷。</p><p>　　軟件環(huán)境本課程設(shè)計(jì)所用操作系統(tǒng)為Windows-XP操作系統(tǒng)，所使用的軟件為Microsoft Visual C++ 6.0；</p><p><b>　　3.詳細(xì)設(shè)計(jì)</b></p><p>　　3.1 直接插入排序</p&g

15、t;<p>　　⑴算法思想：直接插入排序是一種最簡(jiǎn)單的排序方法，它的基本操作是將一個(gè)記錄插入到一個(gè)已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增一的有序表。在自i-1起往前搜索的過(guò)程中，可以同時(shí)后移記錄。整個(gè)排序過(guò)程為進(jìn)行n-1趟插入，即：先將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，然后從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止。</p><p>　?、瞥绦?qū)崿F(xiàn)及核心代

16、碼的注釋：</p><p>　　for (i = 1 ; i < r.length ;++i )</p><p>　　for(j=0;j < i;++j)</p><p>　　if(r.base[i] < r.base[j])</p><p><b>　　{</b></p><p&

17、gt;　　temp = r.base[i]; //保存待插入記錄</p><p>　　for(i= i ;i > j; --i )</p><p>　　r.base[i] = r.base[i-1]; //記錄后移</p><p>　　r.base[j] = temp;

18、 //插入到正確的為位置</p><p><b>　　}</b></p><p>　　r.base[r.length] ='\0';</p><p><b>　　3.2折半排序</b></p><p>　?、潘惴ㄋ枷耄河捎谡郯氩迦肱判虻幕静僮魇窃谝粋€(gè)有序表中進(jìn)行查找和插入

19、，這個(gè)“查找”操作可利用折半查找來(lái)實(shí)現(xiàn)，由此進(jìn)行的插入排序稱之為折半插入排序。折半插入排序所需附加存儲(chǔ)空間和直接插入排序相同，從時(shí)間上比較，這般插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動(dòng)次數(shù) 不變。因此，這般插入排序的時(shí)間復(fù)雜度仍為O（n2）。</p><p>　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：</p><p>　　void zb(FILE *fp)</p><p&

20、gt;　　{ //對(duì)順序表作折半插入排序</p><p>　　for ( i = 1 ; i < r.length ; i++ )</p><p><b>　　{</b></p><p>　　temp=r.base[i];

21、 //將r.base[i]寄存在temp中</p><p><b>　　low=0;</b></p><p>　　high=i-1; </p><p>　　while( low <= high ) //在base[low]到key[high]中折 </p&

22、gt;<p>　　半查找有序插入的位置</p><p><b>　　{ </b></p><p>　　m = (low+high)/2; //折半</p><p>　　if ( temp < r.base[m] )</p><p>　　high = m-1;

23、 //插入低半?yún)^(qū)</p><p><b>　　else</b></p><p>　　low = m+1; //插入高半?yún)^(qū)</p><p><b>　　}</b></p><p>　　for( j=i-1; j>=

24、high+1; --j ) </p><p>　　r.base[j+1]= r.base[j]; //記錄后移 </p><p>　　r.base[high+1]=temp; //插入</p><p><b>　　}</b></p><p&g

25、t;<b>　　3.3 希爾排序</b></p><p>　?、潘惴ㄋ枷耄合葘⒄麄€(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。其中，子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將分隔某個(gè)“增量”的記錄組成一個(gè)子序列。</p><p>　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：</p><

26、p>　　for(k = 0; k < 10 ; k++)</p><p><b>　　{</b></p><p>　　m = 10 - k;</p><p>　　for( i = m ; i < r.length; i ++ )</p><p>　　if(r.base[i] < r.base[i

27、- m]) </p><p><b>　　{</b></p><p>　　temp = r.base[i]; //保存待插記錄 </p><p>　　for(j = i - m ; j >= 0 && temp < r.base[j]; j -= m)</p&

28、gt;<p>　　r.base[ j + m ] = r.base[j]; //記錄后移，查找插入位置 </p><p>　　r.base[ j + m ] = temp; //插入</p><p><b>　　}</b></p><p><b>　　}

29、</b></p><p><b>　　3.4簡(jiǎn)單選擇排序</b></p><p>　?、潘惴ㄋ枷耄涸谝判虻囊唤M數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。</p><p>　?、瞥绦?qū)崿F(xiàn)及核心代碼的注釋：</p><p

30、>　　for ( i = 0 ; i < r.length ; i++ ) </p><p>　　{ //i為排好序的數(shù)的下標(biāo)，依次往后存放排 //好序的數(shù)</p><p>　　temp=r.base[i];

31、 //將待放入排好序的數(shù)的下標(biāo)的數(shù)保存</p><p>　　for( j = i,m = j +1 ; m < r.length ; m++) //找出未排序的數(shù)中最小的數(shù)的循環(huán)；</p><p>　　if(r.base[j] > r.base[m]) </p><p>　　j = m

32、; </p><p>　　r.base[i] = r.base[j]; //把下標(biāo)為j的數(shù)與i數(shù)互換；</p><p>　　r.base[j] = temp; </p><p><b>

33、　　}</b></p><p><b>　　3.5堆排序</b></p><p>　　⑴算法思想：堆排序只需要一個(gè)記錄大小的輔助空間，每個(gè)待排序的記錄僅占有一個(gè)存儲(chǔ)空間。將序列所存儲(chǔ)的元素A[N]看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的元素均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的元素。算法的平均時(shí)間復(fù)雜

34、度為O(N log N)。</p><p>　　⑵程序?qū)崿F(xiàn)及核心代碼的注釋：</p><p>　　void dp(FILE *fp)</p><p><b>　　{</b></p><p>　　for(i = r.length / 2;i >= 1 ; --i) //把r.base[1

35、...r.length]建成大頂堆</p><p>　　HeapAdjust(r.base,i,r.length); </p><p>　　for(i = r.length ;i >= 2 ; --i)</p><p>　　{ </p><p>　　temp

36、 = r.base[1]; </p><p>　　r.base[1] = r.base[i]; </p><p>　　r.base[i] = temp;</p><p>　　HeapAdjust(r.base,1,i-1); //將r.base[1...i-1]重新調(diào)整為大頂堆</p><p&

37、gt;<b>　　}</b></p><p>　　void HeapAdjust(char *r,int k,int m) </p><p><b>　　{ </b></p><p>　　i=k; x=r[i]; j=2*i; //沿key 較大的孩子節(jié)點(diǎn)向下篩選<

38、/p><p>　　while(j<=m) //j為key較大的記錄的下標(biāo)</p><p><b>　　{ </b></p><p>　　if( (j<m) && (r[j]>r[j+1]) )</p><p><b>　　

39、j++;</b></p><p>　　if(x>r[j]) </p><p>　　{ //插入字符比當(dāng)前的大，交換</p><p>　　r[i] =r[j];</p><p><b>　　i = j;</b>

40、</p><p><b>　　j *= 2;</b></p><p><b>　　}</b></p><p>　　else //否則比較停止。</p><p>　　j = m + 1;</p><p><

41、b>　　}</b></p><p>　　r[i] = x; //把字符x插入到該位置，元素插入實(shí)現(xiàn)</p><p><b>　　}</b></p><p><b>　　3.6歸并排序</b></p><p>　　算法思想：

42、先將相鄰的個(gè)數(shù)為1的每?jī)山M數(shù)據(jù)進(jìn)行排序合并；然后對(duì)上次歸并所得到的大小為2的組進(jìn)行相鄰歸并；如此反復(fù)，直到最后并成一組，即排好序的一組數(shù)據(jù)。</p><p>　　⑵程序?qū)崿F(xiàn)及核心代碼的注釋：</p><p>　　void merge(SqList6 r,int h ,int m ,int w ,SqList6 t) </p><p>　　{

43、 //對(duì)相鄰兩組數(shù)據(jù)進(jìn)行組合排序；</p><p>　　int i,j,k;</p><p><b>　　i = h ; </b></p><p>　　j = m + 1; //j為合并

44、的第二組元素的第一個(gè)數(shù)位置</p><p>　　k =h-1； // k為存入t中的數(shù)的位置；</p><p>　　while((i <= m)&&(j <= w)) </p><p>　　{

45、 //依次排列兩組數(shù)據(jù)</p><p><b>　　k++;</b></p><p>　　if(r.base[i] <= r.base[j]) //將第一組數(shù)據(jù)與第二組數(shù)據(jù)分別比較；</p><p>　　t.base[k] = r.ba

46、se[i++];</p><p><b>　　else</b></p><p>　　t.base[k] = r.base[j++];</p><p><b>　　} </b></p><p>　　if(i > m) /

47、/第一組數(shù)據(jù)先排完的情況</p><p>　　while(j <= w) t.base[++k]=r.base[j++];</p><p>　　else </p><p>　　while(i <= m) t.base[++k]=r.base[i++];</p&g

48、t;<p><b>　　}</b></p><p>　　void tgb(int s,int n,SqList6 r,SqList6 t) </p><p>　　{ //對(duì)數(shù)據(jù)進(jìn)行每組s個(gè)數(shù)的歸并排序；</p><p>　

49、　int i=1; //i為要合并兩組元素的第一個(gè)數(shù)位置；</p><p>　　while(i<=(n-2*s+1))</p><p><b>　　{ </b></p><p>　　merge(r,i,i+s-1,i+2*s-1,t);

50、 //i+s-1為要合并的第一組元素的最后一</p><p>　　//數(shù)位置、i+2*s-1 為要合并的兩組元素</p><p>　　//最后一個(gè)數(shù)位置；</p><p><b>　　i=i+2*s;</b></p><p><b>　　}</b></p><p&g

51、t;　　if(i<(n-s+1)) //考慮n不能被s整除，如果余下的數(shù)少于</p><p>　　//2*s 但大于s，也就是余下的數(shù)不能湊成</p><p>　　//兩組，湊一組有余,則把余下的數(shù)進(jìn)行組</p><p>　　//合，并對(duì)其進(jìn)行排序； </p><p>

52、;　　merge(r,i,i+s-1,n,t);</p><p>　　else //如果余下的數(shù)少于s，則余下的數(shù)進(jìn)行組//合，并進(jìn)行排序；</p><p>　　while(i<=n) </p><p>　　t.base[i]=r.base[i++];</p><p>

53、;<b>　　}</b></p><p>　　void gb(FILE *fp) // 歸并主函數(shù)；</p><p><b>　　{ </b></p><p>　　n = r.length;</p><p>　　SqList6 t;<

54、;/p><p>　　t.base=(char *) malloc(r.stacksize*sizeof(char)); </p><p>　　//給待排序的數(shù)組t申請(qǐng)內(nèi)存；</p><p>　　while(s<n) //每組元素不斷增加循環(huán)進(jìn)行合并排序；</p><p>

55、;<b>　　{ </b></p><p>　　tgb(s,n,r,t); // s為每組元素的個(gè)數(shù)、n為元素總個(gè)數(shù)、r</p><p>　　//為原數(shù)組，t為待排序的數(shù)組，進(jìn)行歸并排</p><p>　　s*=2; /

56、/序；把元素個(gè)數(shù)相同的兩組合并 并進(jìn)行重新</p><p>　　//定義成新的一組，此組元素個(gè)數(shù)為2*s；</p><p>　　if(s<n){ tgb(s,n,t,r); s *= 2; } </p><p>　　//當(dāng)元素個(gè)數(shù)小于n時(shí)，對(duì)其進(jìn)行合并排序；</p><p>　　else

57、 //當(dāng)元素個(gè)數(shù)大于n時(shí)，對(duì)剩下的數(shù)排序；</p><p><b>　　{ </b></p><p><b>　　i=0;</b></p><p>　　while(i<=n) </p><p><b>　　{</b></p>

58、<p>　　r.base[i]=t.base[i+1];</p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　} </b></p>

59、<p><b>　　}</b></p><p><b>　　3.7冒泡排序</b></p><p>　?、潘惴ㄋ枷耄?、先將一組未排序的數(shù)組的最后一個(gè)數(shù)與倒數(shù)第二個(gè)數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個(gè)數(shù)中較前的位置，然后將比較后的較小的數(shù)與倒數(shù)第三個(gè)進(jìn)行比較，依次比較到第一個(gè)數(shù)，即可得到第一個(gè)數(shù)是所有數(shù)中最小的數(shù)；2、然后再將數(shù)組的最后一

60、個(gè)數(shù)與倒數(shù)第二個(gè)數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個(gè)數(shù)中較前的位置，依次比較到第二個(gè)數(shù)，3、如此循環(huán)到只剩最后兩個(gè)比較，即得到排好序的一組數(shù)。</p><p>　　⑵程序?qū)崿F(xiàn)及核心代碼的注釋：</p><p>　　for( i=0; i < r.length ;i++ ) // i為排好序的數(shù)的下標(biāo)，依次往后存放排好序的數(shù)； </p>&l

61、t;p><b>　　{ </b></p><p>　　for( j = r.length-2;j >= i;j -- ) //從后往前依次兩兩比較，較小的被調(diào)換到前面 ；</p><p>　　if(r.base[j+1] < r.base[j]) //比較相鄰兩個(gè)數(shù)，如果后面的小于前面的

62、，向下執(zhí)行；</p><p><b>　　{ </b></p><p>　　temp = r.base[j+1]; //將后面的較小的數(shù)保存起來(lái)；</p><p>　　r.base[j+1] = r.base[j]; //將前面的較大的數(shù)放在后面較小的數(shù)的位置；</p><

63、;p>　　r.base[j] = temp; //將較小的數(shù)放在前面的較大的數(shù)的位置；</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　4.調(diào)試</b></p><p>　　檢測(cè)

64、主函數(shù)是否能夠穩(wěn)定運(yùn)行(如圖4-1)：</p><p><b>　　圖4-1</b></p><p><b>　　5.調(diào)試及檢驗(yàn)</b></p><p>　　5.1 直接插入排序</p><p>　　輸入字符并保存（如圖5-1.1）：</p><p>　　調(diào)用算法【1】處理

65、文件（如圖5-1.2）：</p><p>　　處理結(jié)果（如圖5-1.3）：</p><p>　　圖5-1.1 圖5-1.2</p><p><b>　　圖5-1.3</b></p><p><b>　　5.2折半插入排序</b

66、></p><p>　　輸入字符并保存（如圖5-2.1）：</p><p>　　調(diào)用算法【2】處理文件（如圖5-2.2）：</p><p>　　處理結(jié)果（如圖5-2.3）：</p><p>　　圖5-2.1 圖5-2.2圖5-2.3</p>&

67、lt;p><b>　　5.3 希爾排序</b></p><p>　　輸入字符并保存（如圖5-3.1）：</p><p>　　調(diào)用算法【3】處理文件（如圖5-3.2）：</p><p>　　處理結(jié)果（如圖5-3.3）：</p><p>　　圖5-3.1

68、 圖5-3.2</p><p><b>　　圖5-3.3</b></p><p><b>　　5.4簡(jiǎn)單選擇排序</b></p><p>　　輸入字符并保存（如圖5-4.1）：</p><p>　　調(diào)用算法【4】處理文件（如圖5-4.2）：</p><p>　　

69、處理結(jié)果（如圖5-4.3）：</p><p>　　圖5-4.1 圖5-4.2</p><p><b>　　圖5-4.3</b></p><p><b>　　5.5堆排序</b></p><p>　　輸入字符并保存（如圖5

70、-5.1）：</p><p>　　調(diào)用算法【5】處理文件（如圖5-5.2）：</p><p>　　處理結(jié)果（如圖5-5.3）：</p><p>　　圖5-5.1 圖5-5.2</p><p><b>　　圖5-5.3</b></p>

71、;<p><b>　　5.6歸并排序</b></p><p>　　輸入字符并保存（如圖5-6.1）：</p><p>　　調(diào)用算法【6】處理文件（如圖5-6.2）：</p><p>　　處理結(jié)果（如圖5-6.3）：</p><p>　　圖5-6.1

72、 圖5-6.2</p><p><b>　　圖5-6.3</b></p><p><b>　　5.7冒泡排序</b></p><p>　　輸入字符并保存（如圖5-7.1）：</p><p>　　調(diào)用算法【7】處理文件（如圖5-7.2）：</p><p>　

73、　處理結(jié)果（如圖5-7.3）：</p><p>　　圖5-7.1 圖5-7.2</p><p><b>　　圖5-7.3</b></p><p><b>　　6.測(cè)試與比較</b></p><p><b>　　

74、6.1調(diào)試步驟</b></p><p>　　⑴在kcsj文本文件中隨機(jī)輸入一串字符串，然后保存下來(lái)并且復(fù)制備份在桌面上。運(yùn)行程序，調(diào)用不算法去處理文件。用秒表計(jì)算從開(kāi)始到結(jié)束所用的時(shí)間，并記錄下來(lái)。</p><p>　?、茖⑽募A中的kcsj文本文件刪除，將桌面上的備份文件考入文件夾來(lái)代替原文件，以保障被操作數(shù)據(jù)的一致性。</p><p>　?、怯猛瑯拥?/p>

75、方法依次測(cè)試七種算法所用的時(shí)間，并記錄下來(lái)。</p><p>　?、仍賹?shù)據(jù)依次改變?yōu)檎加脙?nèi)存大小為50KB 、100KB、200KB、512KB、1024KB的數(shù)字串，重復(fù)以上的操作。</p><p>　?、蓪⒂涗浀臄?shù)據(jù)（如表6-1）。</p><p>　　表6-1 同一文件不同算法處理的時(shí)間表</p><p><b>　　--：

76、表示時(shí)間過(guò)長(zhǎng)</b></p><p><b>　　6.2結(jié)論</b></p><p>　　通過(guò)實(shí)驗(yàn)結(jié)果的比較與分析我們發(fā)現(xiàn)：直接插入排序、冒泡排序、簡(jiǎn)單選擇排序及折半插入排序是低效率的排序方式；所以我們實(shí)際編程重要盡可能的避免他們的出現(xiàn)；我們應(yīng)該用較先進(jìn)的歸并排序及堆排序。</p><p><b>　　7.實(shí)驗(yàn)心得與分析&

77、lt;/b></p><p>　　通過(guò)本次課程設(shè)計(jì)，我們小組的每個(gè)成員都學(xué)到了很多東西。首先要說(shuō)的是我們的編程能力，在這一次的課程設(shè)計(jì)中我們的編程能力均得到了一定程度的提升。并且通過(guò)這次課程設(shè)計(jì)，我們更加熟悉了如何使用Header File文件。本次課程設(shè)計(jì)，讓我們對(duì)于直接插入排序，折半插入排序，希爾排序，簡(jiǎn)單選擇排序，堆排序，歸并排序，冒泡排序等七種排序算法的思想有了進(jìn)一步的認(rèn)識(shí)，同時(shí)對(duì)七種算法的應(yīng)用有了

78、更進(jìn)一步的掌握。通過(guò)這次課程設(shè)計(jì)，我們對(duì)于解決實(shí)際問(wèn)題的能力有了進(jìn)一步提高。最重要的是，這次課程設(shè)計(jì)大大的訓(xùn)練了我們的小組團(tuán)隊(duì)協(xié)作能力。通過(guò)這次課程設(shè)計(jì)我們小組各成員的團(tuán)隊(duì)協(xié)作能力都有了很大的提升。這種團(tuán)隊(duì)協(xié)作能力對(duì)于我們學(xué)編程的來(lái)說(shuō)是極其重要的，同時(shí)也是必不可少的。</p><p>　　當(dāng)然，我們寫(xiě)程序的時(shí)候遇到了很多困難。而且在程序調(diào)試過(guò)程中出現(xiàn)了很多錯(cuò)誤與警告，不過(guò)在隊(duì)員及老師的幫助下均得到了解決。當(dāng)程序可

79、以運(yùn)行后，程序的運(yùn)行過(guò)程中同樣也也出現(xiàn)了很多錯(cuò)誤，甚至出現(xiàn)了不兼容的情況。不過(guò)，后來(lái)在隊(duì)員及老師的幫助下也均得到了解決。然而，我們的程序還有一點(diǎn)瑕疵讓我們感到美中不足。那就是在歸并算法運(yùn)行過(guò)程中，當(dāng)輸入為9個(gè)字符時(shí)，排序結(jié)果會(huì)出現(xiàn)偶然誤差。經(jīng)過(guò)分析，我們認(rèn)為這點(diǎn)是系統(tǒng)的問(wèn)題。不過(guò)，這仍然是一點(diǎn)讓我們感到遺憾的地方。</p><p><b>　　8.附錄</b></p><

80、p><b>　　8.1直接插入排序</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define Q 1000</p><p>　　typedef struct {</p><

81、;p>　　char *base ; </p><p>　　int stacksize ; </p><p>　　int length;</p><p>　　}SqList1; </p><p>　　void zj(FILE *fp)</p><p><b>　　{</b></p&g

82、t;<p>　　SqList1 r;</p><p><b>　　int i,j;</b></p><p>　　char temp,*p;</p><p>　　r.base=(char *) malloc(Q*sizeof(char));</p><p>　　r.stacksize = Q;</p&g

83、t;<p>　　r.length = 0;</p><p>　　while(!feof(fp))</p><p><b>　　{</b></p><p>　　fscanf(fp,"%c",r.base); </p><p><b>　　r.base++;</b>

84、</p><p>　　r.length++;</p><p>　　if(r.length == r.stacksize )</p><p><b>　　{</b></p><p>　　r.base= r.base - r.length;</p><p>　　r.base=(char *) rea

85、lloc(r.base,(r.stacksize + Q) * sizeof(char));</p><p>　　if(!r.base)</p><p><b>　　{</b></p><p>　　printf("ERROR");</p><p>　　return ; </p>&l

86、t;p><b>　　}</b></p><p>　　r.base = r.base + r.stacksize;</p><p>　　r.stacksize += Q;</p><p><b>　　} </b></p><p><b>　　}</b></p>

87、<p>　　r.length --;</p><p>　　r.base --;</p><p>　　r.base= r.base - r.length;</p><p>　　for (i = 1 ; i < r.length ;++i )</p><p>　　for(j=0;j < i;++j)</p>

88、<p>　　if(r.base[i] < r.base[j])</p><p><b>　　{</b></p><p>　　temp = r.base[i];</p><p>　　for(i= i ;i > j; --i )</p><p>　　r.base[i] = r.base[i-1]

89、;</p><p>　　r.base[j] = temp;</p><p><b>　　}</b></p><p>　　r.base[r.length] ='\0';</p><p>　　rewind(fp);</p><p>　　fprintf(fp,"%s"

90、,r.base);</p><p>　　fclose(fp);</p><p>　　free(r.base);</p><p><b>　　}</b></p><p><b>　　8.2折半插入排序</b></p><p>　　#include<stdio.h>&

91、lt;/p><p>　　#include<stdlib.h></p><p>　　#define Q 1000</p><p>　　typedef struct {</p><p>　　char *base ; </p><p>　　int stacksize ;</p><p>　

92、　int length;</p><p>　　}SqList2; </p><p>　　void zb(FILE *fp)</p><p><b>　　{</b></p><p>　　SqList2 r;</p><p>　　int i,j ,m, low, high;</p>&

93、lt;p>　　char temp;</p><p>　　r.base=(char *) malloc(1000*sizeof(char));</p><p>　　r.stacksize = 1000;</p><p>　　r.length = 0;</p><p>　　while(!feof(fp))</p><p&

94、gt;<b>　　{</b></p><p>　　fscanf(fp,"%c",r.base);</p><p><b>　　r.base++;</b></p><p>　　r.length++;</p><p>　　if(r.length == r.stacksize )&l

95、t;/p><p><b>　　{</b></p><p>　　r.base= r.base - r.length;</p><p>　　r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));</p><p>　　if(!r.base)</p&g

96、t;<p><b>　　{</b></p><p>　　printf("ERROR");</p><p>　　return ; </p><p><b>　　}</b></p><p>　　r.base = r.base + r.stacksize;</p

97、><p>　　r.stacksize += Q;</p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　r.length --;</p><p>　　r.base --;</p><p>　　r.base=

98、 r.base - r.length;</p><p>　　for ( i = 1 ; i < r.length ; i++ )</p><p><b>　　{</b></p><p>　　temp=r.base[i]; </p><p><b>　　low=0;</b></p&

99、gt;<p><b>　　high=i-1;</b></p><p>　　while( low <= high )</p><p><b>　　{ </b></p><p>　　m = (low+high)/2; </p><p>　　if ( temp < r.b

100、ase[m] )</p><p>　　high = m-1; </p><p><b>　　else</b></p><p>　　low = m+1; </p><p><b>　　}</b></p><p>　　for( j=i-1; j>=high+1; --j )

101、</p><p>　　r.base[j+1]= r.base[j]; </p><p>　　r.base[high+1]=temp; </p><p><b>　　}</b></p><p>　　r.base[r.length] ='\0';</p><p>　　rewind(fp

102、);</p><p>　　fprintf(fp,"%s",r.base);</p><p>　　fclose(fp);</p><p>　　free(r.base);</p><p><b>　　}</b></p><p><b>　　8.3希爾排序</b>

103、;</p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define Q 1000</p><p>　　typedef struct {</p><p>　　char *base ; </p>&

104、lt;p>　　int stacksize ;</p><p>　　int length;</p><p>　　}SqList3; </p><p>　　void xe(FILE *fp)</p><p><b>　　{</b></p><p>　　SqList3 r;</p>

105、<p>　　int i,j,k,m;</p><p>　　char temp;</p><p>　　r.length = 0;</p><p>　　r.base=(char *) malloc(1000*sizeof(char));</p><p>　　r.stacksize = 1000;</p><p&g

106、t;　　while(!feof(fp))</p><p><b>　　{</b></p><p>　　fscanf(fp,"%c",r.base);</p><p><b>　　r.base++;</b></p><p>　　r.length++;</p><

107、p>　　if(r.length == r.stacksize )</p><p><b>　　{</b></p><p>　　r.base= r.base - r.length;</p><p>　　r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));<

108、/p><p>　　if(!r.base)</p><p><b>　　{</b></p><p>　　printf("ERROR");</p><p>　　return ; </p><p><b>　　}</b></p><p>

109、　　r.base = r.base + r.stacksize;</p><p>　　r.stacksize += Q;</p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　r.length --;</p><p>　　r.

110、base --;</p><p>　　r.base= r.base - r.length;</p><p>　　for(k = 0; k < 10 ; k++)</p><p><b>　　{</b></p><p>　　m = 10 - k;</p><p>　　for( i = m ;

111、i < r.length; i ++ )</p><p>　　if(r.base[i] < r.base[i - m]) </p><p><b>　　{</b></p><p>　　temp = r.base[i]; </p><p>　　for(j =

112、i - m ; j >= 0 && temp < r.base[j]; j -= m)</p><p>　　r.base[ j + m ] = r.base[j]; </p><p>　　r.base[ j + m ] = temp;</p><p><b>　　}</b></p>&

113、lt;p><b>　　} </b></p><p>　　rewind(fp);</p><p>　　fprintf(fp,"%s",r.base);</p><p>　　fclose(fp);</p><p>　　free(r.base);</p><p><b&g

114、t;　　}</b></p><p><b>　　8.4簡(jiǎn)單選擇排序</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define Q 1000</p><p>　　

115、typedef struct {</p><p>　　char *base ; </p><p>　　int stacksize ;</p><p>　　int length;</p><p>　　}SqList4; </p><p>　　void jd(FILE *fp)</p><p>

116、<b>　　{</b></p><p>　　SqList4 r;</p><p>　　int i,j ,m;</p><p>　　char temp;</p><p>　　r.base=(char *) malloc(1000*sizeof(char));</p><p>　　r.stacksiz

117、e = 1000;</p><p>　　r.length = 0;</p><p>　　while(!feof(fp))</p><p><b>　　{</b></p><p>　　fscanf(fp,"%c",r.base);</p><p><b>　　r.bas

118、e++;</b></p><p>　　r.length++;</p><p>　　if(r.length == r.stacksize )</p><p><b>　　{</b></p><p>　　r.base= r.base - r.length;</p><p>　　r.bas

119、e=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));</p><p>　　if(!r.base)</p><p><b>　　{</b></p><p>　　printf("ERROR");</p><p>　　return ;

120、</p><p><b>　　}</b></p><p>　　r.base = r.base + r.stacksize;</p><p>　　r.stacksize += Q;</p><p><b>　　} </b></p><p><b>　　}</b

121、></p><p>　　r.length --;</p><p>　　r.base --;</p><p>　　r.base= r.base - r.length;</p><p>　　for ( i = 0 ; i < r.length ; i++ )</p><p><b>　　{&l

122、t;/b></p><p>　　temp=r.base[i]; </p><p>　　for( j = i,m = j +1 ; m < r.length ; m++)</p><p>　　if(r.base[j] > r.base[m])</p><p><b>　　j = m;</b><

123、;/p><p>　　r.base[i] = r.base[j];</p><p>　　r.base[j] = temp;</p><p><b>　　}</b></p><p>　　r.base[r.length] ='\0';</p><p>　　rewind(fp);</p&

124、gt;<p>　　fprintf(fp,"%s",r.base);</p><p>　　fclose(fp);</p><p>　　free(r.base);</p><p><b>　　}</b></p><p><b>　　8.5堆排序</b></p>

125、;<p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define Q 1000</p><p>　　typedef struct {</p><p>　　char *base ; </p><p>　　

126、int stacksize ; </p><p>　　int length;</p><p>　　}SqList5; </p><p>　　void HeapAdjust(char *r,int s,int m);</p><p>　　void dp(FILE *fp)</p><p><b>　　{&l

127、t;/b></p><p>　　SqList5 r;</p><p><b>　　int i,j;</b></p><p>　　char temp,*k;</p><p>　　r.length = 0;</p><p>　　r.base=(char *) malloc(1000*sizeof

128、(char));</p><p>　　r.stacksize = 1000;</p><p>　　r.base += 1;</p><p>　　while(!feof(fp))</p><p><b>　　{</b></p><p>　　fscanf(fp,"%c",r.bas

129、e);</p><p><b>　　r.base++;</b></p><p>　　r.length++;</p><p>　　if(r.length == (r.stacksize - 1) )</p><p><b>　　{</b></p><p>　　r.base=

130、r.base - r.length - 1;</p><p>　　r.base=(char *) realloc(r.base,(r.stacksize + Q) * sizeof(char));</p><p>　　if(!r.base)</p><p><b>　　{</b></p><p>　　printf(&qu

131、ot;ERROR");</p><p>　　return ; </p><p><b>　　}</b></p><p>　　r.base = r.base + r.stacksize;</p><p>　　r.stacksize += Q;</p><p><b>　　}

132、 </b></p><p><b>　　}</b></p><p>　　r.length --;</p><p>　　r.base --;</p><p>　　r.base= r.base - r.length - 1;</p><p>　　for(i = r.length / 2;i

133、 >= 1 ; --i)</p><p>　　HeapAdjust(r.base,i,r.length);</p><p>　　for(i = r.length ;i >= 2 ; --i)</p><p><b>　　{</b></p><p>　　temp = r.base[1];</p>

134、<p>　　r.base[1] = r.base[i];</p><p>　　r.base[i] = temp;</p><p>　　HeapAdjust(r.base,1,i-1);</p><p><b>　　}</b></p><p>　　k = (char *) malloc((r.length+1)*