內(nèi)部排序?qū)嶒?yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告內(nèi)部排序班級(jí)：13軟工一班學(xué)號(hào)：13131113姓名：呂 蒙學(xué)號(hào)：13131116姓名：錢劍濱學(xué)號(hào)：13131142姓名：孔亞亞學(xué)號(hào)：13131144姓名：邱佃雨1613軟工轉(zhuǎn)本1錢劍濱實(shí)驗(yàn)報(bào)告內(nèi)部排序?qū)嶒?yàn)報(bào)告信息工程 系13 軟工轉(zhuǎn)本1 日期2016年06月07日一、實(shí)驗(yàn)內(nèi)容編寫程序?qū)崿F(xiàn)各種內(nèi)部排序(包括：冒泡排序、插入排序、選擇排序、希爾排序、 快速排序、堆排序、歸并排序、基數(shù)排序)，并運(yùn)用這些排序?qū)σ唤M隨機(jī)生成的數(shù)組進(jìn) 行排序。二、時(shí)間復(fù)雜度1. 冒泡排序(O(n，)若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。 所需的關(guān)鍵字比較次數(shù) C和記錄移動(dòng)次數(shù) M均達(dá)到最小值：

2、Cmin = n-1 , Mm如二0。所以，冒泡排序最好的時(shí)間復(fù)雜度為 0(«) 。若初始文件是反序的，需要進(jìn)行五三趟排序。每趟排序要進(jìn)行n- i次關(guān)鍵字的比較(1 <<1),且每次比較都必須移動(dòng)記錄三次來(lái)達(dá)到交換記錄位置。在這種情況下，比較和移動(dòng)次數(shù)均達(dá)到最大值:加小二業(yè)畀二0(段2瓜”。綜上，因此冒泡Mmx = 3M2 11=°(層)冒泡排序的最壞時(shí)間復(fù)雜度為排序總的平均時(shí)間復(fù)雜度為0(n?) O2. 插入排序(O(nA2)如果目標(biāo)是把n個(gè)元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經(jīng)是升序排列了，在這種情況下，需要進(jìn)行的

3、比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那么此時(shí)需要進(jìn)行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數(shù)加上(n-1 )次。平均來(lái)說插入排序算法的時(shí)間復(fù)雜度為 0(門人2)。因而，插入排序不適合對(duì)于數(shù)據(jù)量比較大的排序應(yīng)用。但是， 如果需要排序的數(shù)據(jù)量很小，例如，量級(jí)小于千，那么插入排序還是一個(gè)不錯(cuò)的選擇。3. 選擇排序(0付八2)選擇排序的交換操作介于0和(n - 1)次之間。選擇排序的比較操作為n (n - 1)/ 2次之間。選擇排序的賦值操作介于0和3 (n - 1 )次之間。比較次數(shù) 0(門人2),比較次數(shù)與關(guān)鍵字的初始狀態(tài)無(wú)關(guān)，總的比較次數(shù)N=(n-1

4、 ) +(n-2) +.+1=n*(n-1 ) /2。交換次數(shù)O(n),最好情況是，已經(jīng)有序，交換 0次；最壞情況交換 n-1次，逆序交換 n/2次。交換次數(shù)比冒泡排序少多了，由于交換所需 CPU時(shí)間比比較所需的 CPU時(shí)間多，n值較小時(shí)，選擇排序比冒泡排序快。4. 希爾排序希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序，當(dāng)剛開始元素很無(wú)序的時(shí)候，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時(shí)間復(fù)雜度會(huì)比。何人2)好一些。5. 快速排序(O(M2)無(wú)論適用哪一種方法來(lái)選擇pivot,由于我們不知道各個(gè)元素間的相對(duì)大小關(guān)系

5、(若知道就已經(jīng)排好序了)，所以我們無(wú)法確定pivot的選擇對(duì)劃分造成的影響。因此對(duì)各種pivot選擇法而言，最壞情況和最好情況都是相同的。我們從直覺上可以判斷出最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含 n-1個(gè)元素和1個(gè)元素的時(shí)候(設(shè)輸入的表有n個(gè)元素)。下面我們暫時(shí)認(rèn)為該猜測(cè)正確，在后文我們?cè)僭敿?xì)證明該猜測(cè)。對(duì)于有n個(gè)元素的表Lp.r,由于函數(shù)Partition的計(jì)算時(shí)間為 0 (n),所以快速 排序在序壞情況下的復(fù)雜性有遞歸式如下：T(1)= 0 (1),T(n)=T(n -1)+T(1)+ 0 (n)(1)用迭代法可以解出上式的解為T(n)= 0 (n2)。這個(gè)最壞情況運(yùn)行時(shí)間與

6、插入排序是一樣的。下面我們來(lái)證明這種每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含n-1個(gè)元素和1個(gè)元素的情況就是最壞情況。設(shè) T(n)是過程Quick_Sort作用于規(guī)模為n的輸入上 的最壞情況的時(shí)間，則 T(n)=max(T(q)+T(n- q)+ 0 ( n),其中 1<q<-i1(2)我們假設(shè)對(duì)于任何k<n,總有T(k) < ck其中c為常數(shù)；顯然當(dāng)k=1時(shí)是成立的。將歸納假設(shè)代入 (2),得到：T(n) < max(cq2+c(n -q)2)+ 0 ( n)=c*max(q2+(n- q)2)+ 0 (n)因?yàn)樵?,n-1上q2+(n-q)2關(guān)于q遞減，所以當(dāng)q=1

7、時(shí)q2+(n-q)2有最大值n2-2(n-1 )。于是有：T(n) Wcn22c(n-1)+ 0 (n) w cn2只要c足夠大，上面的第二個(gè) 小于等于號(hào)就可以成立。于是對(duì)于所有的n都有T(n) <cn>這樣，排序算法的最壞情況運(yùn)行時(shí)間為0 (n2),且最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含n-1個(gè)元素和1個(gè)元素的時(shí)候。時(shí)間復(fù)雜度為 o (n2)。6. 堆排序(O(nlgn)堆排序過程的時(shí)間復(fù)雜度是O(nlgn)。因?yàn)榻ǘ训臅r(shí)間復(fù)雜度是O(n)(調(diào)用一次)；調(diào)整堆的時(shí)間復(fù)雜度是lgn,調(diào)用了 n-1次，所以堆排序的時(shí)間復(fù)雜度是O(nlgn)7. 歸并排序(O(nlgn)時(shí)

8、間復(fù)雜度為O(nlogn)這是該算法中最好、最壞和平均的時(shí)間性能?？臻g復(fù)雜度為O(n)比較操作的次數(shù)介于(nlogn) / 2和nlogn - n + 1 。賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)歸并排序比較占用內(nèi)存，但卻是一種效率高且穩(wěn)定的算法。8. 基數(shù)排序(O(d(n+radix)時(shí)間效率：設(shè)待排序列為 n個(gè)記錄，d個(gè)關(guān)鍵碼，關(guān)鍵碼的取值范圍為 radix,則 進(jìn)行鏈?zhǔn)交鶖?shù)排序白時(shí)間復(fù)雜度為 O(d(n+radix)，其中，一趟分配時(shí)間復(fù)雜度為 O(n), 一趟收集時(shí)間復(fù)雜度為 O(radix),共進(jìn)行d趟分配和收集。 空間效率：需要 2*radix 個(gè)指向

9、隊(duì)列的輔助空間，以及用于靜態(tài)鏈表的n個(gè)指針。三、算法穩(wěn)定性1 .冒泡排序（穩(wěn)定）冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，我想你是不會(huì)再無(wú)聊地把他們倆交換一下的；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把 兩個(gè)相鄰起來(lái)，這時(shí)候也不會(huì)交換， 所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。2 .插入排序（穩(wěn)定）插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上，一次插入一個(gè)元素。 當(dāng)然，剛開始這個(gè)有序的小序列只有 1個(gè)元素，就是第一個(gè)元素。比較是從有序序列的末尾開始， 也就是想要插入的元素

10、和已經(jīng)有序的最大者開始比起，如果比它大則直接插入在其后 面，否則一直往前找直到找到它該插入的位置。如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變， 從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。3 .選擇排序（不穩(wěn)定）選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的，比如給第一個(gè)位置選擇最小的， 在剩余元素里面給第二個(gè)元素選擇第二小的，依次類推，直到第n-1個(gè)元素，第n個(gè)元素不用選擇了，因?yàn)橹皇Ｏ滤粋€(gè)最大的元素了。那么，在一趟選擇，如果一個(gè)元素比當(dāng)前元素小，而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面，那么交換后穩(wěn)定性

11、就被破壞了。比較拗口，舉個(gè)例子，序列 5 8 5 2 9,我們知道第一遍選擇第 1個(gè)元素5 會(huì)和2交換，那么原序列中兩個(gè) 5的相對(duì)前后順序就被破壞了，所以選擇排序是一個(gè) 不穩(wěn)定的排序算法。4 .希爾排序（不穩(wěn)定）由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過程中， 相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以 shell排序是不穩(wěn)定的。5 .快速排序（不穩(wěn)定）快速排序有兩個(gè)方向，左邊的i下標(biāo)一直往右走，當(dāng) ai <= acenter_index,其中center_index是中樞元素的數(shù)組下標(biāo)，一般取為數(shù)組第0個(gè)元素

12、。而右邊的j下標(biāo)一直往左走，當(dāng)aj > acenter_index。如果i和j都走不動(dòng)了,i <= j,交換ai和aj,重復(fù)上面的過程，直到i>j。交換aj和acenter_index,完成一趟快速排序。在中樞元素和 aj交換的時(shí)候，很有可能把前面的元素的穩(wěn)定性打亂，比如序列5 3 3 4 3 8 9 10 11 ,現(xiàn)在中樞元素5和3（第5個(gè)元素，下標(biāo)從1開始計(jì)）交換就會(huì)把元素3的穩(wěn)定性打亂， 所以快速排序是一個(gè)不穩(wěn)定的排序算法，不穩(wěn)定發(fā)生在中樞元素和aj交換的時(shí)刻。6 .堆排序（不穩(wěn)定）堆排序的時(shí)間，主要由建立初始堆和反復(fù)重建堆這兩部分的時(shí)間開銷構(gòu)成，它們均是通過調(diào)用Hea

13、pify實(shí)現(xiàn)的。堆排序的最壞時(shí)間復(fù)雜度為O（nlgn）。堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄數(shù)較少的文件。堆排序是就地排序，輔助空間為0(1),它是不穩(wěn)定的排序方法。7 .歸并排序(穩(wěn)定)歸并排序是一種穩(wěn)定的排序8 .基數(shù)排序(穩(wěn)定)基數(shù)排序是一種穩(wěn)定的排序四、各排序介紹和算法實(shí)現(xiàn)1 .冒泡排序冒泡排序算法的運(yùn)作如下：(從后往前)(1)比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。(2)對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)， 最后的元素應(yīng)該會(huì)是最大的數(shù)。(3)針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

14、(4)持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。 代碼：void maopao(int numberNMAX)int temp, i, j, t;yuan(numberN);int numberYMAX;for(t = 0; t < N; t+) numberYt = numberNt;for(i = 0; i < N - 1; i+)for(j = 0; j < N - (i + 1); j+) if(numberYj > numberYj + 1) temp = numberYj;numberYj = numberYj + 1;numbe

15、rYj + 1 = temp;sheng(numberY);2 .插入排序一般來(lái)說，插入排序都采用 in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下:(1)從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序(2)取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描(3)如果該元素(已排序)大于新元素，將該元素移到下一位置(4)重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置(5)將新元素插入到下一位置中(6)重復(fù)步驟25代碼：void charu(int numberNMAX)int i,j,t；int temp;int numberYMAX;yuan(numberN);for(t = 0; t

16、< N; t+)numberYt = numberNt;for(i=1;i<N;i+)temp=numberYi;for(j=i;j>0&&numberYj-1>temp;j-)numberYj=numberYj-1;numberYj=temp;sheng(numberY);3 .選擇排序?qū)Ρ葦?shù)組中前一個(gè)元素跟后一個(gè)元素的大小，如果后面的元素比前面的元素小則用一個(gè)變量k來(lái)記住他的位置，接著第二次比較，前面后一個(gè)元素現(xiàn)變成了 前一個(gè)元素”，繼續(xù)跟他的 后一個(gè)元素”進(jìn)行比較如果后面的元素比他要小則用變量k記住它在數(shù)組中的位置(下標(biāo))，等到循環(huán)結(jié)束的時(shí)候，我們

17、應(yīng)該找到了最小的那個(gè)數(shù)的下標(biāo)了，然 后進(jìn)行判斷，如果這個(gè)元素的下標(biāo)不是第一個(gè)元素的下標(biāo)，就讓第一個(gè)元素跟他交換一下值，這樣就找到整個(gè)數(shù)組中最小的數(shù)了。然后找到數(shù)組中第二小的數(shù)，讓他跟數(shù)組中第二個(gè)元素交換一下值，以此類推。代碼：void xuanze(int numberNMAX) int temp, i, j, t, min;int numberYMAX; yuan(numberN);for(t = 0; t < N; t+) numberYt = numberNt;for(i = 0; i < N - 1; i+) min = i;for(j = i + 1; j < N;

18、 j+) if(numberYmin > numberYj) min = j; temp = numberYi;numberYi = numberYmin; numberYmin = temp;sheng(numberY);4 .希爾排序先取一個(gè)小于n的整數(shù)di作為第一個(gè)增量，把文彳的全部記錄分成di個(gè)組。所有距離為di的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取 第二個(gè)增量d2Vdi重復(fù)上述的分組和排序，直至所取的增量dt=1(dt<dt- l< <d2<d1),即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂４a：void xier(int n

19、umberNMAX) int d, i, j, t, temp;int numberYMAX;yuan(numberN);for(t = 0; t < N; t+) numberYt = numberNt;for(d = N/2;d >= i;d = d/2)for(i = d; i < N;i+)temp = numberYi;for(j = i - d;(j >= 0) && (numberYj > temp);j = j-d) numberYj + d = numberYj; | numberYj + d = temp;sheng(numbe

20、rY);5 .快速排序設(shè)要排序的數(shù)組是 A0AN-1,首先任意選取一個(gè)數(shù)據(jù)(通常選用數(shù)組的第一個(gè)數(shù))作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法， 也就是說，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。一趟快速排序的算法是：(1)設(shè)置兩個(gè)變量i、j,排序開始的時(shí)候：i=0 , j=N-1 ;(2)以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給 key,即key=A0;(3)從j開始向前搜索，即由后開始向前搜索(j-),找到第一個(gè)小于key的值A(chǔ)j,將Aj和Ai互換;(4)從i開始向后搜索，即由前開

21、始向后搜索(i+),找到第一個(gè)大于 key的Ai,將Ai和Aj互換;(5)重復(fù)第3、4步，直到i=j; (3,4步中，沒找到符合條件的值，即 3中Aj不小于 key,4中Ai不大于key的時(shí)候改變j、i的值，使得j=j-1 , i=i+1 ,直至找到為止。 找到符合條件的值，進(jìn)行交換的時(shí)候i, j指針位置不變。另外，i=j這一過程一定正文?是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束)。代碼：int partions(int numberYMAX,int low,int high)int prvotkey=numberYlow;while (low<high)while (low<hig

22、h&&numberYhigh>=prvotkey)-high;numberYlow=numberYhigh;while (low<high&&numberYlow<=prvotkey) +low;numberYhigh=numberYlow; numberYlow=prvotkey;return low;void quicksort(int numberYMAX,int low,int high) int prvotloc;if(low<high) prvotloc=partions(numberY,low,high);/ 將第一次排序的

23、結(jié)果作為樞軸quicksort(numberY,low,prvotloc-1);/遞歸調(diào)用排序由 low 至1J prvotloc-1quicksort(numberY,prvotloc+1,high);/遞歸調(diào)用排序由 prvotloc+1 至U highvoid kuaisu(int numberNMAX)int i;int numberYMAX;yuan(numberN);for(i = 0; i < N; i+)numberYi = numberNi;quicksort(numberY, 0, N-1); sheng(numberY);6.堆排序大根堆排序算法的基本操作:(1)建

24、堆，建堆是不斷調(diào)整堆的過程，從 len/2處開始調(diào)整，一直到第一個(gè)節(jié)點(diǎn)，此處len是堆中元素的個(gè)數(shù)。建堆的過程是線性的過程，從 len/2到0處一直調(diào)用調(diào)整堆 的過程，相當(dāng)于o(h1)+o(h2)+o(hlen/2) 其中h表示節(jié)點(diǎn)的深度，len/2表示節(jié)點(diǎn)的個(gè) 數(shù)，這是一個(gè)求和的過程，結(jié)果是線性的O(n)。(2)調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會(huì)用到，而且在堆排序過程中也會(huì)用到。利用的思想是比較節(jié)點(diǎn)i和它的孩子節(jié)點(diǎn)left(i),right(i),選出三者最大(或者最小)者，如果最 大(小)值不是節(jié)點(diǎn)i而是它的一個(gè)孩子節(jié)點(diǎn)，那邊交互節(jié)點(diǎn)i和該節(jié)點(diǎn)，然后再調(diào)用調(diào)整堆過程，這是一個(gè)遞歸的過程。 調(diào)

25、整堆的過程時(shí)間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作，因?yàn)槭茄刂疃确较蜻M(jìn)行調(diào)整的。(3)堆排序：堆排序是利用上面的兩個(gè)過程來(lái)進(jìn)行的。首先是根據(jù)元素構(gòu)建堆。然后將堆的根節(jié)點(diǎn)取出(一般是與最后一個(gè)節(jié)點(diǎn)進(jìn)行交換)，將前面len-1個(gè)節(jié)點(diǎn)繼續(xù)進(jìn)行堆調(diào)整的過程，然后再將根節(jié)點(diǎn)取出，這樣一直到所有節(jié)點(diǎn)都取出。代碼：/ array是待調(diào)整的堆數(shù)組, 本函數(shù)功能是：根據(jù)數(shù)組 代碼：/ array是待調(diào)整的堆數(shù)組, 本函數(shù)功能是：根據(jù)數(shù)組 代碼：i是待調(diào)整的數(shù)組元素的位置, array構(gòu)建大根堆nlength是數(shù)組的長(zhǎng)度i是待調(diào)整的數(shù)組元素的位置，nlength是數(shù)組的長(zhǎng)度array構(gòu)建大根堆void Hea

26、pAdjust(int array口，int i, int nLength) int nChild;int nTemp;for (nTemp = arrayi; 2 * i + 1 < nLength; i = nChild) /子結(jié)點(diǎn)的位置=2* (父結(jié)點(diǎn)位置)+ 1nChild = 2 * i + 1;/得到子結(jié)點(diǎn)中較大的結(jié)點(diǎn)if ( nChild < nLength-1 && arraynChild + 1 > arraynChild) +nChild;/如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父 結(jié)點(diǎn)if (nTemp <

27、arraynChild)arrayi = arraynChild;arraynChild= nTemp; else/否則退出循環(huán)break;/堆排序算法void dui(int numberNMAX)int tmp, t, i;int numberYMAX;yuan(numberN);for(t = 0; t < N; t+) numberYt = numberNt;/調(diào)整序列的前半部分元素，調(diào)整完之后第一個(gè)元素是序列的最大的元素/length/2-1是第一個(gè)非葉節(jié)點(diǎn)，此處"/"為整除for (i = floor(N -1)/ 2 ; i >= 0; -i) H

28、eapAdjust(numberY, i, N);/從最后一個(gè)元素開始對(duì)序列進(jìn)行調(diào)整，不斷的縮小調(diào)整的范圍直到第一個(gè)元素for (i = N - 1; i > 0; -i)/把第一個(gè)元素和當(dāng)前的最后一個(gè)元素交換，/保證當(dāng)前的最后一個(gè)位置的元素都是在現(xiàn)在的這個(gè)序列之中最大的/ Swap(&array0, &arrayi);tmp = numberYi;numberYi = numberY0;numberY0 = tmp;/不斷縮小調(diào)整heap的范圍，每一次調(diào)整完畢保證第一個(gè)元素是當(dāng)前序列的 最大值HeapAdjust(numberY, 0, i); sheng(number

29、Y);7.歸并排序歸并操作的工作原理如下：(1)申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列(2)設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置(3)比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到 下一位置(4)重復(fù)步驟(3)直到某一指針超出序列尾(5)將另一序列剩下的所有元素直接復(fù)制到合并序列尾代碼：歸并操作void Merge(int sourceArr, int targetArr, int startindex, int midIndex, int endindex)int i, j, k；for(i = midindex+1,

30、j = startindex; startindex <= midIndex && i <= endindex; j+) if(sourceArrstartindex < sourceArri)targetArrj = sourceArrstartindex+; else targetArrj = sourceArri+;if(startindex <= midindex)for(k = 0; k <= midindex-startindex; k+)targetArrj+k = sourceArrstartindex+k;if(i <= e

31、ndindex)for(k = 0; k <= endindex- i; k+) targetArrj+k = sourceArri+k;內(nèi)部使用遞歸，空間復(fù)雜度為n+lognvoid MergeSort(int sourceArr口，int targetArr口，int startindex, int endindex)int midIndex;int tempArrMAX; 此處大小依需求更改 if(startIndex = endindex)targetArrstartIndex = sourceArrstartIndex;elsemidIndex = (startindex + endIndex)/2;MergeSort(sourceArr, tempArr, startindex, midIndex);Me