c歸并排序與堆排序的課程設(shè)計(jì)

1、<p><b>　　《C語(yǔ)言程序設(shè)計(jì)》</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p><b>　　計(jì)算機(jī)學(xué)院</b></p><p>　　2017 年 4月 27 日</p><p><b>　　目錄</b></

2、p><p>　　1歸并排序的設(shè)計(jì)內(nèi)容及要求.........................................3</p><p>　　1.1設(shè)計(jì)內(nèi)容.....................................................3</p><p>　　1.2設(shè)計(jì)任務(wù)及具體要求............................

3、...............3</p><p>　　2 歸并排序概要設(shè)計(jì)................................................4</p><p>　　2.1該系統(tǒng)的功能簡(jiǎn)介.............................................4</p><p>　　2.2 總體程序框圖.........

4、........................................5</p><p>　　3 歸并排序設(shè)計(jì)過程或程序代碼.......................................6</p><p>　　3.1各個(gè)模塊的程序流程圖及介紹...................................6</p><p>　　3.2

5、對(duì)關(guān)鍵代碼加以分析說明.......................................7</p><p>　　4歸并排序程序調(diào)試分析............................................14</p><p>　　5堆排序的基本簡(jiǎn)介................................................15</p&

6、gt;<p>　　5.1 堆排序的框架圖..............................................16</p><p>　　6堆排序的算法描述.................................................19</p><p>　　6.1 堆排序的算法介紹...........................

7、.................23</p><p>　　7堆的原理分析.....................................................23</p><p>　　8小結(jié).............................................................24</p><p>　　9 附程

8、序運(yùn)行結(jié)果圖................................................24</p><p>　　1 設(shè)計(jì)內(nèi)容及要求</p><p><b>　　1.1設(shè)計(jì)內(nèi)容</b></p><p>　　歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個(gè)非常典

9、型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列;即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。</p><p>　　歸并過程的內(nèi)容為:比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1;否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，

10、然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]</p><p>　　1.2設(shè)計(jì)任務(wù)及具體要求</p><p>　　申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；</p&g

11、t;<p>　　設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；</p><p>　　比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；</p><p>　　重復(fù)步驟3直到某一指針達(dá)到序列尾；</p><p>　　將另一序列剩下的所有元素直接復(fù)制到合并序列尾</p><p><b>

12、;　　2 概要設(shè)計(jì)</b></p><p>　　2.1系統(tǒng)的功能簡(jiǎn)介</p><p>　　歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。</p><p>　　如　設(shè)有數(shù)列{6，202，100，301，38，8，1}</p><p>　　初始狀態(tài)： [6] [202] [100] [301]

13、 [38] [8] [1] 比較次數(shù)</p><p>　　i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3</p><p>　　i=2 [ 6 100 202 301 ] [ 1 8 38 ]　4</p><p>　　i=3　[ 1 6 8 38 100 202 301 ] 4</p><p><b>

14、　　總計(jì)：　11次</b></p><p><b>　　算法復(fù)雜度</b></p><p>　　時(shí)間復(fù)雜度為O(nlogn) 這是該算法中最好、最壞和平均的時(shí)間性能。</p><p>　　空間復(fù)雜度為 O(n)</p><p>　　比較操作的次數(shù)介于(nlogn) / 2和nlogn - n + 1。<

15、/p><p>　　賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)</p><p>　　歸并排序比較占用內(nèi)存，但卻效率高且穩(wěn)定的算法。</p><p>　　Pascal中的歸并算法</p><p>　　所謂歸并排序是指將兩個(gè)或兩個(gè)以上有序的數(shù)列（或有序表），合并成一個(gè)仍然有序的數(shù)列（或有序表）。這樣的排序方法經(jīng)常用于多個(gè)有序的

16、數(shù)據(jù)文件歸并成一個(gè)有序的數(shù)據(jù)文件。歸并排序的算法比較簡(jiǎn)單。</p><p>　　2.2.總體程序框圖</p><p>　　3 歸并排序設(shè)計(jì)過程或程序代碼</p><p>　　3.1各個(gè)模塊的程序流程圖及介紹</p><p>　　歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。</p><

17、;p>　　如　設(shè)有數(shù)列{6，202，100，301，38，8，1}</p><p>　　初始狀態(tài)： [6] [202] [100] [301] [38] [8] [1] 比較次數(shù)</p><p>　　i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3</p><p>　　i=2 [ 6 100 202 301 ] [ 1 8 38

18、]　4</p><p>　　i=3　[ 1 6 8 38 100 202 301 ] 4</p><p><b>　　總計(jì)：　11次</b></p><p>　　3.2對(duì)關(guān)鍵代碼加以分析說明</p><p>　　時(shí)間復(fù)雜度為O(nlogn) 這是該算法中最好、最壞和平均的時(shí)間性能。</p><p>

19、;　　空間復(fù)雜度為 O(n)</p><p>　　比較操作的次數(shù)介于(nlogn) / 2和nlogn - n + 1。</p><p>　　賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)</p><p>　　歸并排序比較占用內(nèi)存，但卻效率高且穩(wěn)定的算法</p><p>　　4歸并排序程序調(diào)試分析</p>

20、<p>　?。?）假設(shè)已經(jīng)有兩個(gè)有序數(shù)列，分別存放在兩個(gè)數(shù)組s，r中；并設(shè)i，j分別為指向數(shù)組的第一個(gè)單元的下標(biāo)；s有n個(gè)元素，r有m個(gè)元素。</p><p>　?。?）再另設(shè)一個(gè)數(shù)組a，k指向該數(shù)組的第一個(gè)單元下標(biāo)。</p><p>　?。?）算法分析（過程）：</p><p>　　procedure merge(s,r,a,i,j,k);

21、 </p><p><b>　　begin</b></p><p><b>　　i1:=i;</b></p><p><b>　　j1:=j;</b></p><p><b>　　k1:=k;</b></p>

22、<p>　　while (i1<n) and (j1<m) do</p><p>　　if s[i1]<=r[j1] then</p><p><b>　　begin</b></p><p>　　a[k]:=s[i1]; </p><p>

23、<b>　　i1:=i1+1;</b></p><p><b>　　k:=k+1;</b></p><p><b>　　End</b></p><p><b>　　else</b></p><p><b>　　begin</b><

24、;/p><p>　　a[k]:=r[j1];</p><p><b>　　j1:=j1+1;</b></p><p><b>　　k:=k+1;</b></p><p><b>　　end;</b></p><p>　　while i1<=n do&l

25、t;/p><p><b>　　begin</b></p><p>　　a[k]:=s[i1];</p><p><b>　　i1:=i1+1;</b></p><p><b>　　k:=k+1;</b></p><p><b>　　end;<

26、/b></p><p>　　while j1<=m d</p><p>　　while j1<=m do</p><p><b>　　begin</b></p><p>　　a[k]:=r[j1];</p><p><b>　　j1:=j1+1;</b>&l

27、t;/p><p><b>　　k:=k+1;</b></p><p><b>　　end;</b></p><p><b>　　end;</b></p><p><b>　　完整的C++源代碼</b></p><p>　　#includ

28、e<iostream.h></p><p>　　void Merge(int r[],int r1[],int s,int m,int t)</p><p><b>　　{</b></p><p>　　int i=s;int j=m+1;int k=s;</p><p>　　while(i<=m&

29、;&j<=t)</p><p><b>　　{</b></p><p>　　if(r<=r[j])r1[k++]=r[i++];</p><p>　　else r1[k++]=r[j++];</p><p><b>　　}</b></p><p><

30、b>　　if(i<=m)</b></p><p>　　while(i<=m) r1[k++]=r[i++];</p><p>　　else while(j<=t)</p><p>　　r1[k++]=r[j++];</p><p>　　for(int l=0;l<8;l++)</p>&

31、lt;p>　　r[l]=r1[l];</p><p><b>　　}</b></p><p>　　void MergeSort(int r[],int r1[],int s,int t)</p><p><b>　　{</b></p><p>　　if(s==t)r1[s]=r[s];<

32、/p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　int m=(s+t)/2;</p><p>　　MergeSort(r,r1,s,m);</p><p>　　MergeSort(r,r1,m+1,t);</p>

33、<p>　　Merge(r1,r,s,m,t);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　int

34、 r[8]={10,3,5,1,9,34,54,565},r1[8];</p><p>　　MergeSort(r,r1,0,7);</p><p>　　for(int q=0;q<8;q++)</p><p>　　cout<<" "<<r[q];</p><p><b>　　}&l

35、t;/b></p><p><b>　　end;</b></p><p>　　歸并排序有兩種實(shí)現(xiàn)方法：自底向上和自頂向下，算法實(shí)現(xiàn)如下：</p><p><b>　　1.自底向上算法</b></p><p>　　#include <stdio.h></p><p

36、>　　#include <time.h></p><p>　　void Merge(int *a,int low,int mid,int high)</p><p><b>　　{</b></p><p>　　int i = low,j = mid + 1,k = 0;</p><p>　　int *t

37、emp = (int *)malloc((high - low + 1)*sizeof(int));</p><p>　　while(i <= mid && j <= high)</p><p>　　a < a[j] ? (temp[k++] = a[i++]):(temp[k++] = a[j++]);</p><p>

38、　　while(i <= mid)</p><p>　　temp[k++] = a[i++];</p><p>　　while(j <= high)</p><p>　　temp[k++] = a[j++];</p><p>　　memcpy(a + low,temp,(high -low + 1)*sizeof(int));&l

39、t;/p><p>　　free(temp);</p><p><b>　　}</b></p><p>　　void MergeSort(int *a,int n)</p><p><b>　　{</b></p><p>　　int length;</p><p

40、>　　for(length = 1;length < n;length *= 2)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for( i = 0;i + 2*length - 1 <= n - 1;i += 2*length)</

41、p><p>　　Merge(a,i,i+length-1,i+2*length -1);</p><p>　　if(i + 2*length - 1 <= n - 1)//尚有兩個(gè)子文件，其中后一個(gè)長(zhǎng)度小于length</p><p>　　Merge(a,i,i +2* length -1,n - 1);</p><p><b>

42、　　}</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p><p><b>　　int n;</b></p><p><b>　　cin >

43、> n;</b></p><p>　　int *data = new int[n];</p><p>　　if(!data) exit(1);</p><p>　　int k = n;</p><p>　　while(k --)</p><p><b>　　{</b></p

44、><p>　　cin >> data[n-k-1];</p><p><b>　　}</b></p><p>　　clock_t s = clock();</p><p>　　MergeSort(data, n);</p><p>　　clock_t e = clock();</p&

45、gt;<p><b>　　k = n;</b></p><p>　　while(k --){</p><p>　　cout << data[n-k-1] << ' ';</p><p><b>　　}</b></p><p>　　cout <

46、;< endl;</p><p>　　cout << "the algrothem used " << e-s << " miliseconds."<< endl;</p><p>　　delete data;</p><p><b>　　return 0;<

47、;/b></p><p><b>　　}</b></p><p><b>　　2.自頂向下</b></p><p>　　void Merge(int r[],int r1[],int s,int m,int t)</p><p><b>　　{</b></p>

48、<p>　　int i=s;int j=m+1;int k=s;</p><p>　　while(i<=m&&j<=t)</p><p><b>　　{</b></p><p>　　if(r<=r[j])r1[k++]=r[i++];</p><p>　　else r1[k

49、++]=r[j++];</p><p><b>　　}</b></p><p>　　while(i<=m) r1[k++]=r[i++];</p><p>　　while(j<=t)</p><p>　　r1[k++]=r[j++];</p><p>　　for(int l=0;l&l

50、t;8;l++)</p><p>　　r[l]=r1[l];</p><p><b>　　}</b></p><p>　　void MergeSort(int r[],int r1[],int s,int t)</p><p><b>　　{</b></p><p>　　if

51、(s==t)r1[s]=r[s];</p><p><b>　　else{</b></p><p>　　int m=(s+t)/2;</p><p>　　MergeSort(r,r1,s,m);</p><p>　　MergeSort(r,r1,m+1,t);</p><p>　　Merge(r1

52、,r,s,m,t);</p><p><b>　　}</b></p><p><b>　　}    </b></p><p><b>　　排序</b></p><p>　?。ㄋ俣葍H次于快速排序，但較穩(wěn)定）</p><p><b&

53、gt;　　求逆序?qū)?shù)</b></p><p>　　具體思路是，在歸并的過程中計(jì)算每個(gè)小區(qū)間的逆序?qū)?shù)，進(jìn)而計(jì)算出大區(qū)間的逆序?qū)?shù)（也可以用樹狀數(shù)組來求解）</p><p><b>　　5堆排序的基本簡(jiǎn)介</b></p><p>　　堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并

54、同時(shí)滿足堆性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。</p><p>　　?堆積排序(Heapsort)是指利用堆積樹（堆）這種資料結(jié)構(gòu)所設(shè)計(jì)的一種排序算法，可以利用數(shù)組的特點(diǎn)快速定位指定索引的元素。            </p><p>　　5.1 堆排序的程序框圖</p><p>　　

55、6 堆排序的算法描述</p><p><b>　　折疊C語(yǔ)言描述</b></p><p>　　// array是待調(diào)整的堆數(shù)組，i是待調(diào)整的數(shù)組元素的位置，nlength是數(shù)組的長(zhǎng)度</p><p>　　void HeapAdjust(int array[],int i,int nLength)//本函數(shù)功能是：根據(jù)數(shù)組array構(gòu)建大根堆&

56、lt;/p><p>　　{　int nChild;</p><p>　　int nTemp;</p><p>　　for (nTemp = array; 2 * i + 1 < nLength; i = nChild)</p><p>　　{　// 子結(jié)點(diǎn)的位置=2*（父結(jié)點(diǎn)位置）+ 1</p><p>　　nChi

57、ld = 2 * i + 1;</p><p>　　// 得到子結(jié)點(diǎn)中較大的結(jié)點(diǎn)</p><p>　　if (nChild < nLength - 1 && array[nChild + 1] > array[nChild])</p><p><b>　　++nChild;</b></p><p&

58、gt;　　// 如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父結(jié)點(diǎn)</p><p>　　if (nTemp < array[nChild])</p><p>　　{　array= array[nChild];}</p><p>　　else　// 否則退出循環(huán)</p><p>　　{　break;}// 最后把需要調(diào)整

59、的元素值放到合適的位置</p><p>　　array[nChild]= nTemp;}</p><p>　　堆排序算法（C++描述）</p><p>　　#define MAX 100//數(shù)據(jù)元素的最大個(gè)數(shù)</p><p>　　typedef struct</p><p><b>　　{</b>

60、</p><p>　　int r[MAX];</p><p>　　int length;</p><p>　　}SqList;//定義一個(gè)線性表用于存放數(shù)據(jù)元素</p><p>　　void HeapAdjust(SqList &L,int s,int m)</p><p>　　{//已知L.r[s...m]中

61、記錄除L.r[s]外均滿足堆的定義，本函數(shù)用于使L.r[s...m]成為一個(gè)大頂堆</p><p><b>　　int j;</b></p><p>　　int e=L.r[s];</p><p>　　for(j=2*s;j<=m;j*=2)</p><p><b>　　{</b></p

62、><p>　　if(j<M&&L.R[J]<L.R[J+1]) ++j;</p><p>　　if(e>=L.r[j]) break;</p><p>　　L.r[s]=L.r[j];</p><p><b>　　s=j;</b></p><p><b>　

63、　}</b></p><p><b>　　L.r[s]=e;</b></p><p><b>　　}</b></p><p>　　void HeapSort(SqList &L)</p><p>　　{//對(duì)順序表L進(jìn)行堆排序</p><p><b&

64、gt;　　int i,e;</b></p><p>　　for(i=L.length/2;i>0;i--)</p><p>　　HeapAdjust(L,i,L.length);</p><p>　　for(i=L.length;i>1;i--)</p><p>　　{//將大頂堆的頂記錄和最后一個(gè)記錄相互交換<

65、/p><p><b>　　e=L.r[1];</b></p><p>　　L.r[1]=L.r;</p><p><b>　　L.r=e;</b></p><p>　　6.1 堆排序的算法介紹</p><p>　　因?yàn)闃?gòu)造初始堆必須使用到調(diào)整堆的操作，先討論Heapify的實(shí)現(xiàn)，

66、再討論如何構(gòu)造初始堆（即BuildHeap的實(shí)現(xiàn)）Heapify函數(shù)思想方法</p><p>　　每趟排序開始前R[l..i]是以R[1]為根的堆，在R[1]與R交換后，新的無序區(qū)R[1..i-1]中只有R[1]的值發(fā)生了變化，故除R[1]可能違反堆性質(zhì)外，其余任何結(jié)點(diǎn)為根的子樹均是堆。因此，當(dāng)被調(diào)整區(qū)間是R[low..high]時(shí)，只須調(diào)整以R[low]為根的樹即可。</p><p>&

67、lt;b>　　"篩選法"調(diào)整堆</b></p><p>　　R[low]的左、右子樹（若存在）均已是堆，這兩棵子樹的根R[2low]和R[2low+1]分別是各自子樹中關(guān)鍵字最大的結(jié)點(diǎn)。若R[low].key不小于這兩個(gè)孩子結(jié)點(diǎn)的關(guān)鍵字，則R[low]未違反堆[性質(zhì)，以R[low]為根的樹已是堆，無須調(diào)整；否則必須將R[low]和它的兩個(gè)孩子結(jié)點(diǎn)中關(guān)鍵字較大者進(jìn)行交換，即R[

68、low]與R[large](R[large].key=max(R[2low].key，R[2low+1].key））交換。交換后又可能使結(jié)點(diǎn)R[large]違反堆性質(zhì)，同樣由于該結(jié)點(diǎn)的兩棵子樹（若存在）仍然是堆，故可重復(fù)上述的調(diào)整過程，對(duì)以R[large]為根的樹進(jìn)行調(diào)整。此過程直至當(dāng)前被調(diào)整的結(jié)點(diǎn)已滿足性質(zhì)，或者該結(jié)點(diǎn)已是葉子為止。上述過程就象過篩子一樣，把較小的關(guān)鍵字逐層篩下去，而將較大的關(guān)鍵字逐層選上來。因此，有人將此方法稱為&q

69、uot;篩選法"。</p><p><b>　　7 堆的原理分析</b></p><p><b>　　起源</b></p><p>　　1991年計(jì)算機(jī)先驅(qū)獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同發(fā)明了著名的堆

70、排序算法（ Heap Sort )</p><p><b>　　“堆”定義</b></p><p>　　n個(gè)關(guān)鍵字序列Kl，K2，…，Kn稱為（Heap），當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡(jiǎn)稱為堆性質(zhì)）：</p><p>　　(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），當(dāng)然，這是小根堆，大根堆則換成>=號(hào)。/

71、/k(i）相當(dāng)于二叉樹的非葉結(jié)點(diǎn)，K(2i）則是左孩子，k(2i+1）是右孩子</p><p>　　若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：</p><p>　　樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左右孩子（若存在）結(jié)點(diǎn)的關(guān)鍵字。</p><p>　　【例】關(guān)鍵字序列（10，15，56，25

72、，30，70）和（70，56，30，25，15，10）分別滿足堆性質(zhì)（1）和（2），故它們均是堆，其對(duì)應(yīng)的完全二叉樹分別如小根堆示例和大根堆示例所示。</p><p>　　大根堆和小根堆：根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆，又稱最小堆。根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆，又稱最大堆。注意：①堆中任一子樹亦是堆。②以上討論的堆實(shí)際上是二叉堆（Bi

73、nary Heap），類似地可定義k叉堆。</p><p><b>　　堆的高度</b></p><p>　　堆可以被看成是一棵樹，結(jié)點(diǎn)在堆中的高度可以被定義為從本結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長(zhǎng)簡(jiǎn)單下降路徑上邊的數(shù)目；定義堆的高度為樹根的高度。我們將看到，堆結(jié)構(gòu)上的一些基本操作的運(yùn)行時(shí)間至多是與樹的高度成正比，為O（lgn）。</p><p><b

74、>　　堆排序</b></p><p>　　堆排序利用了大根堆（或小根堆）堆頂記錄的關(guān)鍵字最大（或最小）這一特征，使得在當(dāng)前無序區(qū)中選取最大（或最?。╆P(guān)鍵字的記錄變得簡(jiǎn)單。</p><p>　?。?）用大根堆排序的基本思想</p><p>　?、?先將初始文件R[1..n]建成一個(gè)大根堆，此堆為初始的無序區(qū)</p><p>　

75、　② 再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key</p><p>　?、塾捎诮粨Q后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，由此得到新的無序區(qū)R[1..

76、n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。</p><p><b>　　……</b></p><p>　　直到無序區(qū)只有一個(gè)元素為止。</p><p>　?。?）大根堆排序算法的基本操作：</p><p>　?、?初始化

77、操作：將R[1..n]構(gòu)造為初始堆；</p><p>　?、?每一趟排序的基本操作：將當(dāng)前無序區(qū)的堆頂記錄R[1]和該區(qū)間的最后一個(gè)記錄交換，然后將新的無序區(qū)調(diào)整為堆（亦稱重建堆）。</p><p><b>　　注意：</b></p><p>　?、僦恍枳鰊-1趟排序，選出較大的n-1個(gè)關(guān)鍵字即可以使得文件遞增有序。</p>&l

78、t;p>　?、谟眯「雅判蚺c利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時(shí)刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為止</p><p><b>　　特點(diǎn)</b></p><p>　　堆排序（HeapSort）是一樹形選擇排序。堆排序的特點(diǎn)是：在排序過程中，將R[l..n]看成是一棵完全

79、二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系（參見二叉樹的順序存儲(chǔ)結(jié)構(gòu)），在當(dāng)前無序區(qū)中選擇關(guān)鍵字最大（或最?。┑挠涗?lt;/p><p>　　堆排序與直接選擇排序的區(qū)別</p><p>　　直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實(shí)上，后面的n-2次比較中，

80、有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時(shí)未保留這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作。</p><p>　　堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。</p><p><b>　　算法分析</b></p><p>　　堆排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開銷構(gòu)成，它們均是通

81、過調(diào)用Heapify實(shí)現(xiàn)的。</p><p>　　堆排序的最壞時(shí)間復(fù)雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。</p><p>　　由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。</p><p>　　堆排序是就地排序，輔助空間為O(1），</p><p>　　它是不穩(wěn)定的排序方法。</p>&

82、lt;p><b>　　8小結(jié)</b></p><p>　　隨著我國(guó)成功加入WTO及信息化浪潮的日益臨近，企業(yè)、單位等一些部門在激烈的市場(chǎng)競(jìng)爭(zhēng)環(huán)境下求得生存，就必須有效地利用人才、時(shí)間、信息結(jié)合的優(yōu)勢(shì)。因此，如何使企業(yè)、單位等部門及時(shí)掌握本企業(yè)、單位等人才的各種信息、第一時(shí)間處理好隨時(shí)變化的工資管理問題，建立一套符合企業(yè)、單位實(shí)際的工資管理系統(tǒng)就顯得尤為重要。</p>&l

83、t;p>　　在本課程設(shè)計(jì)的設(shè)計(jì)過程中，我剛開始感覺到有點(diǎn)頭痛。要通過一學(xué)期C語(yǔ)言的學(xué)習(xí)后將所學(xué)知識(shí)運(yùn)用起來有點(diǎn)困難，但回過頭來再去看教課書，對(duì)于這些知識(shí)點(diǎn)有關(guān)的背景，概念和解決方案更進(jìn)一步的理解，感覺也不是很難。</p><p>　　另外我還體會(huì)了從事C語(yǔ)言課程設(shè)計(jì)工作需要特別謹(jǐn)慎認(rèn)真地態(tài)度和作風(fēng)，一點(diǎn)都不能馬虎。每個(gè)細(xì)微的細(xì)節(jié)都必須十分注意，如果不認(rèn)真思考，就會(huì)出現(xiàn)或大或小的錯(cuò)誤。如果把早期的錯(cuò)誤隱藏下來

84、，對(duì)后面的工作影響就會(huì)很大，甚至有時(shí)會(huì)推倒很多前面做的工作。有時(shí)候，我自己覺得我寫的程序非常正確，但是就是編譯通不過，在查找錯(cuò)誤的過程中，面臨著否認(rèn)自己的過程，非常的痛苦，而且由于自己的經(jīng)驗(yàn)及各方面的能力的不足，所以進(jìn)展的速度非常的緩慢，往往幾天的時(shí)間沒有一點(diǎn)進(jìn)展。這時(shí)候，我一般是先自己通過書本，手冊(cè)和資料找解決辦法，實(shí)在沒轍才向老師同學(xué)請(qǐng)教。</p><p>　　在開始編寫程序的時(shí)候，我看到別人的程序功能非常的

85、詳細(xì)，而且界面非常漂亮，總是希望自己的程序也非常的完善，但是，發(fā)現(xiàn)編一個(gè)好的程序不是一蹴而就的事情，需要長(zhǎng)時(shí)間的積累和經(jīng)驗(yàn)。</p><p>　　在反反復(fù)復(fù)的學(xué)習(xí)中，我終于作出一個(gè)簡(jiǎn)單的程序，雖然這個(gè)程序的功能非常簡(jiǎn)單，而且在實(shí)際運(yùn)用中還有些不足，因?yàn)榕判虻乃惴ǚ浅ＸS富，我涉及到的僅僅是排序算法的一部分簡(jiǎn)單內(nèi)容，離實(shí)際的算法需求肯定還有差距。</p><p>　　由于我的知識(shí)淺薄，經(jīng)驗(yàn)不足

86、及閱歷頗淺，在該算法的設(shè)計(jì)方面還有很多不足，比如功能過少，界面不醒目等問題，我會(huì)在以后的學(xué)習(xí)過程中，根據(jù)具體要求不斷的修改、完善，爭(zhēng)取使算法慢慢趨于完美。</p><p><b>　　9附程序運(yùn)行結(jié)果圖</b></p><p><b>　　歸并排序運(yùn)行結(jié)果圖</b></p><p><b>　　堆排序運(yùn)行結(jié)果圖&