排序算法可視化

1、 排序算法可視化摘 要：排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。排序的方法有很多，但就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，每一種方法都有各自的優(yōu)缺點(diǎn)，適合在不同的環(huán)境（如記錄的初始排列狀態(tài)等）下使用。本論文主要討論七種排序算法，即直接插入排序，簡單選擇排序，冒泡排序，冒泡排序改進(jìn)算法一，二，快速排序與歸并排序。論文中我們用DirectX創(chuàng)建對象，對象由隨機(jī)生成，無需人工干預(yù)來選擇或者輸入數(shù)據(jù)。比較的指標(biāo)為關(guān)鍵字的比較次數(shù)和關(guān)鍵字的移動次數(shù)。關(guān)鍵詞： 直接插入排序，簡單選擇排序，冒泡排序，冒泡排序改進(jìn)算法快

2、速排序，歸并排序 Sorting algorithm visualizationLI Chen Xing(School of computer and Software engineering XiHua University.,Chengdu 610065 China)Abstract:Sorting is a computer programming is an important operation , and its function is a data element ( or record ) in any sequence , rearranged an ordered

3、 sequence by keyword . There are a lot of sort of way, but its overall performance , it is hard proposed method is considered to be the best , each method has its own advantages and disadvantages , suitable for different environments ( such as the initial alignment state record etc.) use . This pape

4、r focuses on seven kinds of sorting algorithms , namely, direct insertion sort, simply select sort, bubble sort , bubble sort algorithm is an improvement , two , quick sort and merge sort . Paper we create objects with DirectX, the object is generated by random , without human intervention to select

5、 or enter data. Compare the number of key indicators to compare the number of keywords and mobile .Keywords: bubble sort, simple selection sort, quick sort，merge sort,straight insert sort. 1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1.1.基礎(chǔ)知識在計(jì)算機(jī)所描繪的3D世界中，所有的物體模型（如樹木，人物，山巒）都是通過多邊形網(wǎng)格來逼近表示的，這些多邊形可以是三角形，也可以是四邊形。任何物體都可以用三角形網(wǎng)格來逼近表示，三角形網(wǎng)格是構(gòu)建物

6、體模型的基本單元。眾所周知，一個(gè)三角形有三個(gè)頂點(diǎn)，為了能夠通過大量的三角形組成三角形網(wǎng)格來描述物體，首先需要定義好三角形的頂點(diǎn)（Vertex），三個(gè)頂點(diǎn)確定一個(gè)三角形，而頂點(diǎn)除了定義每個(gè)頂點(diǎn)的坐標(biāo)位置以外，還含有顏色等其他屬性。在Direct3D中，頂點(diǎn)的具體表現(xiàn)形式是頂點(diǎn)緩存（Vertex Buffer），頂點(diǎn)緩存保存了頂點(diǎn)數(shù)據(jù)的內(nèi)存空間。靈活頂點(diǎn)格式（Flexible Vertex Format，F(xiàn)VF）來描述三角形網(wǎng)格的每個(gè)頂點(diǎn)。1.2頂點(diǎn)緩存使用設(shè)計(jì)頂點(diǎn)緩存struct stD3DVertex float x, y, z, rhw;/頂點(diǎn)的三維坐標(biāo)值，x，y，z，以及rhw值（包含經(jīng)過

7、坐標(biāo)變換的頂點(diǎn)坐標(biāo)值） unsigned long color;/頂點(diǎn)的顏色值;stD3DVertex objData300;/頂點(diǎn)數(shù)組#define D3DFVF_VERTEX (D3DFVF_XYZRHW | D3DFVF_DIFFUSE)/FVF靈活頂點(diǎn)格式1.2.2 創(chuàng)建頂點(diǎn)緩存創(chuàng)建頂點(diǎn)緩存的代碼合起來就是：LPDIRECT3DVERTEXBUFFER9 g_pVertexBuffer = NULL; /頂點(diǎn)緩沖區(qū)對象/創(chuàng)建頂點(diǎn)緩沖區(qū)if(FAILED(g_D3DDevice->CreateVertexBuffer(sizeof(objData), 0, D3DFVF_VERTE

8、X, D3DPOOL_DEFAULT, &g_VertexBuffer, NULL) return false;.頂點(diǎn)緩存使用四步曲之三：訪問頂點(diǎn)緩存for(i = 0;i < 300;i+=4)j = rand()%340 + 60;objDatai.x = 28+(i*2)-3;objDatai+1.x = 28+(i*2)-3;objDatai+2.x = 20+(i*2);objDatai+3.x = 20+(i*2);objDatai.y = j;objDatai+1.y = 400;objDatai+2.y = j;objDatai+3.y = 400;objData

9、i.z = 0.5f;objDatai+1.z = 0.5f;objDatai+2.z = 0.5f;objDatai+3.z = 0.5f;objDatai.rhw = 1.0f;objDatai+1.rhw = 1.0f;objDatai+2.rhw = 1.0f;objDatai+3.rhw = 1.0f;objDatai.color = col;objDatai+1.color = col;objDatai+2.color = col;objDatai+3.color = col; g_pVertexBuffer->Lock( 0, sizeof(vertices), (void

10、*)&pVertices, 0 ) ;/加鎖 memcpy(ptr, objData, sizeof(objData);/頂點(diǎn)數(shù)組內(nèi)容的拷貝 g_pVertexBuffer->Unlock();/解鎖1.2.3圖形的繪制 / 【Direct3D渲染五步曲之二】：開始繪制 g_pd3dDevice->BeginScene(); / 開始繪制/ 【Direct3D渲染五步曲之三】：正式繪制，利用頂點(diǎn)緩存繪制圖形 g_pd3dDevice->SetRenderState(D3DRS_SHADEMODE,D3DSHADE_GOURAUD); g_pd3dDevice->

11、SetStreamSource( 0, g_pVertexBuffer, 0, sizeof(CUSTOMVERTEX) ); g_pd3dDevice->SetFVF( D3DFVF_CUSTOMVERTEX ); g_D3DDevice->DrawPrimitive(D3DPT_TRIANGLESTRIP, 0, 298);/ 【Direct3D渲染五步曲之四】：結(jié)束繪制 g_pd3dDevice->EndScene(); / 結(jié)束繪制 2 三種排序算法2.1直接插入排序（straight insert sort）2.1.1基本原理將一個(gè)記錄插入到已排序好的有序表中，從而

12、得到一個(gè)新，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹?。要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲和判斷數(shù)組邊界之用。2.1.2排序穩(wěn)定性 如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。2.1.3算法的實(shí)現(xiàn)void StraightInsertSort()int i,j,pos,t;init();/從小到大排序Sleep(2000);for(i= 4; i<300; i+=4)if(objDatai.

13、y > objDatai-4.y) /若第i個(gè)元素大于i-1元素，直接插入。小于的話，移動有序表后插入int j= i-4;int x = objDatai.y; /復(fù)制為哨兵，即存儲待排序元素while(x > objDataj.y) /查找在有序表的插入位置objDataj+4.y = objDataj.y;objDataj+6.y = objDataj+2.y;j-=4; /元素后移if(j<0)break;objDataj+4.y = x; /插入到正確位置objDataj+6.y = x;2.1.4時(shí)間復(fù)雜度分析從空間來看，它只需要一個(gè)記錄的輔助空間，從時(shí)間來看，排

14、序的基本操作為：比較兩個(gè)關(guān)鍵字的大小和移動記錄。于當(dāng)待排序列為正序的時(shí)候，所需進(jìn)行關(guān)鍵字間比較的次數(shù)達(dá)最小值n-1，記錄不需移動；反之，當(dāng)為逆序的時(shí)候，總隊(duì)比較次數(shù)為(n+2)*(n+1)/2,記錄移動的次數(shù)也達(dá)到最大值(n+4)*(n-1)/2。若待排記錄是隨機(jī)的，取上述最小值與最大值的平均值，約為n*n/4。所以它的時(shí)間復(fù)雜度為。2.2簡單選擇排序（simple selection sort）2.2.1基本原理在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小（或者最大）的與第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n

15、個(gè)元素（最后一個(gè)數(shù)）比較為止。2.2.2排序穩(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)定性就被破壞了。比較拗口，舉個(gè)例子，序列5 8 5 2 9，我們知道第一遍選擇第1個(gè)元素5會和2交換，那么原序列中兩個(gè)5的相對前后順序就被破壞了，所以選擇排序是一個(gè)不穩(wěn)定的排序算法。2.2.3算法實(shí)現(xiàn)void SelectSort()init();Sle

16、ep(2000);int key, tmp;for(int i = 0; i<=296; i+=4) key = SelectMinKey(objData, 296,i); /選擇最小的元素if(key != i)tmp = objDatai.y; objDatai.y = objDatakey.y;objDatai+2.y =objDatai.y ;objDatakey.y = tmp; /最小元素與第i位置元素互換objDatakey+2.y = objDatakey.y;2.2.4時(shí)間復(fù)雜度分析選擇排序的交換操作介于 0 和 (n - 1） 次之間。選擇排序的比較操作為 n (n

17、- 1） / 2 次之間。選擇排序的賦值操作介于 0 和 3 (n - 1） 次之間。比較次數(shù)，比較次數(shù)與關(guān)鍵字的初始狀態(tài)無關(guān)，總的比較次數(shù)N=(n-1）+(n-2）+.+1=n*(n-1）/2。交換次數(shù)O(n），最好情況是，已經(jīng)有序，交換0次；最壞情況是，逆序，交換n-1次。交換次數(shù)比冒泡排序少多了，由于交換所需CPU時(shí)間比比較所需的CPU時(shí)間多，n值較小時(shí)，選擇排序比冒泡排序快。該算法運(yùn)行時(shí)間與元素的初始排列無關(guān)。不論初始排列如何，該算法都必須執(zhí)行n-1趟，每趟執(zhí)行n-i-1次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡單選擇排序的最好、最壞和平均情況的時(shí)間復(fù)雜度都為。2.3冒泡排序（bub

18、ble sort）2.3.1基本原理在要排序的一組數(shù)中，對當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。排序穩(wěn)定性冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以，如果兩個(gè)元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來，這時(shí)候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。2.3.3 算法實(shí)現(xiàn)void bu

19、bblesort()/從小到大排序int i,j,t;init();Sleep(500); for(i=0;i<=296;i+=4) /依次比較相鄰的兩個(gè)數(shù)的大小 for(j=0;j<=296-i;j+=4)if(objDataj.y<objDataj+4.y)t=objDataj.y;objDataj.y=objDataj+4.y;objDataj+4.y=t;objDataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y; 2.3.4時(shí)間復(fù)雜度分析若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)和記錄移動次數(shù)

20、 均達(dá)到最小值： ，。所以，冒泡排序最好的時(shí)間復(fù)雜度為。若初始文件是反序的，需要進(jìn)行趟排序。每趟排序要進(jìn)行次關(guān)鍵字的比較(1in-1)，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動次數(shù)均達(dá)到最大值：冒泡排序的最壞時(shí)間復(fù)雜度為綜上，因此冒泡排序總的平均時(shí)間復(fù)雜度為。2.4 冒泡排序改進(jìn)算法一2.4.1基本原理設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可。2.4.2 算法實(shí)現(xiàn)void bubblesort_1()/從小到大排序int curPos=

21、292; /初始時(shí),最后位置保持不變int i,j,t;init();Sleep(500);while(curPos>0)int pos=0;/每趟開始時(shí),無記錄交換for(j=0;j<=curPos;j+=4)if(objDataj.y<objDataj+4.y)pos=j;/記錄交換的位置 t=objDataj.y;objDataj.y=objDataj+4.y;objDataj+4.y=t;objDataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y; curPos=pos;/為下一趟排序作準(zhǔn)備2.4.3時(shí)間復(fù)雜度分析同冒泡

22、排序一樣，若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)和記錄移動次數(shù) 均達(dá)到最小值： ，。所以，最好的時(shí)間復(fù)雜度為。若初始文件是反序的，需要進(jìn)行趟排序。每趟排序要進(jìn)行次關(guān)鍵字的比較(1in-1)，且每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動次數(shù)均達(dá)到最大值：最壞時(shí)間復(fù)雜度為綜上，此排序總的平均時(shí)間復(fù)雜度為。2.5冒泡排序改進(jìn)算法二2.5.1基本原理傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個(gè)最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個(gè)最終值(最大者和最小者) , 從而使排序趟數(shù)

23、幾乎減少了一半。算法實(shí)現(xiàn)void bubblesort_2()int i,j,t;int low=0;int high=296;init();while(low<=high) for(j=low;j<=high;j+=4) if(objDataj.y<objDataj+4.y) /正向冒泡,找到最大者t=objDataj.y;objDataj.y=objDataj+4.y;objDataj+4.y=t;objDataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y; high-=4; for ( j=high; j>=low;

24、 j-=4) /反向冒泡,找到最小者 if(objDataj.y<objDataj+4.y)t=objDataj.y;objDataj.y=objDataj+4.y;objDataj+4.y=t;objDataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y; low+=4; 2.5.3時(shí)間復(fù)雜度分析同冒泡排序一樣，若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關(guān)鍵字比較次數(shù)和記錄移動次數(shù) 均達(dá)到最小值： ，。所以，最好的時(shí)間復(fù)雜度為。若初始文件是反序的，需要進(jìn)行趟排序。每趟排序要進(jìn)行次關(guān)鍵字的比較(1in-1)，且

25、每次比較都必須移動記錄三次來達(dá)到交換記錄位置。在這種情況下，比較和移動次數(shù)均達(dá)到最大值：最壞時(shí)間復(fù)雜度為綜上，此排序總的平均時(shí)間復(fù)雜度為。2.6快速排序2.6.1基本原理1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,2）通過一趟排序講待排序的記錄分割成獨(dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。另一部分記錄的 元素值比基準(zhǔn)值大。3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序。2.6.2排序穩(wěn)定性快速排序是一個(gè)不穩(wěn)定的排序方法。2.6.3算法實(shí)現(xiàn)int partition(stD3DVertex objD

26、ata, int low, int high)/從小到大排序/objData0.y=objDatalow.y;int privotKey = objDatalow.y;/基準(zhǔn)元素while(low < high) /從表的兩端交替地向中間掃描while(low < high && objDatahigh.y <= privotKey)high=high-4; /從high 所指位置向前搜索，至多到low+1 位置。將比基準(zhǔn)元素小的交換到低端SWAP(objDatalow.y, objDatahigh.y);objDatahigh+2.y=objDatahigh

27、.y;objDatalow+2.y=objDatalow.y; while(low < high && objDatalow.y>= privotKey )low=low+4;SWAP(objDatalow.y, objDatahigh.y);objDatalow+2.y=objDatalow.y;objDatahigh+2.y=objDatahigh.y;return low;/快速排序void quickSort(stD3DVertex a, int low, int high)if(low < high)int privotLoc = partition

28、(a, low, high); /將表一分為二quickSort(a, low, privotLoc -4);/遞歸對低子表遞歸排序quickSort(a, privotLoc + 4, high);/遞歸對高子表遞歸排序 2.6.4時(shí)間復(fù)雜度分析我們先分析函數(shù)partition的性能，該函數(shù)對于確定的輸入復(fù)雜性是確定的。觀察該函數(shù)，我們發(fā)現(xiàn)，對于有n個(gè)元素的確定輸入Lp.r，該函數(shù)運(yùn)行時(shí)間顯然為（n）。最壞情況無論適用哪一種方法來選擇pivot，由于我們不知道各個(gè)元素間的相對大小關(guān)系（若知道就已經(jīng)排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最

29、壞情況和最好情況都是相同的。我們從直覺上可以判斷出最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含n-1個(gè)元素和1個(gè)元素的時(shí)候（設(shè)輸入的表有n個(gè)元素）。下面我們暫時(shí)認(rèn)為該猜測正確，在后文我們再詳細(xì)證明該猜測。對于有n個(gè)元素的表Lp.r，由于函數(shù)Partition的計(jì)算時(shí)間為（n），所以快速排序在序壞情況下的復(fù)雜性有遞歸式如下：T(1)=(1),T(n)=T(n-1)+T(1)+(n) (1)用迭代法可以解出上式的解為T(n)=（n2）。這個(gè)最壞情況運(yùn)行時(shí)間與插入排序是一樣的。下面我們來證明這種每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含n-1個(gè)元素和1個(gè)元素的情況就是最壞情況。設(shè)T(n）是過程Quick

30、_Sort作用于規(guī)模為n的輸入上的最壞情況的時(shí)間，則T(n)=max(T(q)+T(n-q)+（n)，其中1qn-1 (2)我們假設(shè)對于任何k<n，總有T(k）ck，其中c為常數(shù)；顯然當(dāng)k=1時(shí)是成立的。將歸納假設(shè)代入（2），得到：T(n）max(cq2+c(n-q)2)+（n)=c*max(q2+(n-q)2)+（n)因?yàn)樵?,n-1上q2+(n-q)2關(guān)于q遞減，所以當(dāng)q=1時(shí)q2+(n-q)2有最大值n2-2(n-1）。于是有：T(n）cn2-2c(n-1)+（n）cn2只要c足夠大，上面的第二個(gè)小于等于號就可以成立。于是對于所有的n都有T(n）cn。這樣，排序算法的最壞情況運(yùn)行時(shí)

31、間為（n2），且最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含n-1個(gè)元素和1個(gè)元素的時(shí)候。時(shí)間復(fù)雜度為。最好情況如果每次劃分過程產(chǎn)生的區(qū)間大小都為n/2，則快速排序法運(yùn)行就快得多了。這時(shí)有：T(n)=2T(n/2)+（n),T(1)=（1) (3)解得：T(n)=（nlogn)快速排序法最佳情況下執(zhí)行過程的遞歸樹如下圖所示，圖中l(wèi)gn表示以2位底的對數(shù)，而本文中用logn表示以2位底的對數(shù).由于快速排序法也是基于比較的排序法，其運(yùn)行時(shí)間為（nlogn)，所以如果每次劃分過程產(chǎn)生的區(qū)間大小都為n/2，則運(yùn)行時(shí)間（nlogn）就是最好情況運(yùn)行時(shí)間。但是，是否一定要每次平均劃分才能達(dá)到最好情況呢

32、？要理解這一點(diǎn)就必須理解對稱性是如何在描述運(yùn)行時(shí)間的遞歸式中反映的。我們假設(shè)每次劃分過程都產(chǎn)生9:1的劃分，乍一看該劃分很不對稱。我們可以得到遞歸式：T(n)=T(n/10)+T(9n/10)+（n),T(1)=（1) (4)請注意樹的每一層都有代價(jià)n，直到在深度log10n=（logn）處達(dá)到邊界條件，以后各層代價(jià)至多為n。遞歸于深度log10/9n=（logn）處結(jié)束。這樣，快速排序的總時(shí)間代價(jià)為T(n)=（nlogn），從漸進(jìn)意義上看就和劃分是在中間進(jìn)行的一樣。事實(shí)上，即使是99:1的劃分時(shí)間代價(jià)也為（nlogn）。其原因在于，任何一種按常數(shù)比例進(jìn)行劃分所產(chǎn)生的遞歸樹的深度都為（nlog

33、n），其中每一層的代價(jià)為O(n），因而不管常數(shù)比例是什么，總的運(yùn)行時(shí)間都為（nlogn），只不過其中隱含的常數(shù)因子有所不同。（關(guān)于算法復(fù)雜性的漸進(jìn)階，請參閱算法的復(fù)雜性)平均情況快速排序的平均運(yùn)行時(shí)間為(nlogn)。2.7歸并排序2.7.1基本原理歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。設(shè)rin由兩個(gè)有序子表rim和rm+1n組成，兩個(gè)子表長度分別為n-i +1、n-m。1.j=m+1；k=i；i=i; /置兩個(gè)子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)2.若i>m 或j

34、>n，轉(zhuǎn)4 /其中一個(gè)子表已合并完，比較選取結(jié)束3.選取ri和rj較小的存入輔助數(shù)組rf如果ri<rj，rfk=ri； i+； k+； 轉(zhuǎn)2否則，rfk=rj； j+； k+； 轉(zhuǎn)24.將尚未處理完的子表中元素存入rf如果i<=m，將rim存入rfkn /前一子表非空如果j<=n ,  將rjn 存入rfkn /后一子表非空5.合并結(jié)束。2.7.2算法穩(wěn)定性歸并排序是一種穩(wěn)定的排序方法。2.7.3算法實(shí)現(xiàn)void Merge(stD3DVertex *r,stD3DVertex *rf, int i, int m, int n)int j,k;for(j=m+

35、4,k=i; i<=m && j <=n ; k+=4)if(rj.y > ri.y)rfk.y = rj.y;rfk+2.y = rj.y;j+=4;else rfk.y = ri.y;rfk+2.y = ri.y; i+=4;while(i <= m) rfk.y = ri.y;rfk+2.y = ri.y;k+=4;i+=4;while(j <= n) rfk.y = rj.y;rfk+2.y = rj.y;k+=4;j+=4;void MergeSort(stD3DVertex *r, stD3DVertex *rf, int lenght

36、) init();Sleep(2000);int len = 4;stD3DVertex *q = r ;/*stD3DVertex *tmp ;*/while(len < lenght) int s = len;len = 2* s ;int i = 0;while(i+ len <lenght)Merge(q, rf, i, i+ s-4, i+ len-4 ); /對等長的兩個(gè)子表合并i = i+ len;if(i + s <=lenght)Merge(q, rf, i, i+ s -4, lenght -4); /對不等長的兩個(gè)子表合并 /把rf的值付給qfor(in

37、t m=0;m<lenght;m+=4)qm.y=rfm.y;qm+2.y=qm.y; 2.7.4時(shí)間復(fù)雜度分析一趟歸并排序的操作是，調(diào)用n/2h次merge將sr1.n中前后相鄰且長度為h的有序段進(jìn)行兩兩歸并，得到前后相鄰、長度為2h的有序段，并存放在TR1.n中，整個(gè)歸并排序需進(jìn)行l(wèi)og2n(以2為底)趟?？梢姡瑢?shí)現(xiàn)歸并排序需和待排記錄等數(shù)量的輔助空間，其時(shí)間復(fù)雜度為O(nlogn)。 3運(yùn)行程序截圖 3.1 直接插入排序3.2簡單選擇排序3.3冒泡排序3.4冒泡排序改進(jìn)一3.5冒泡算法改進(jìn)二3.6快速排序3.7歸并排序 4總結(jié)排序算法是是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)排序算法是為了將實(shí)際問題中涉及的對象在計(jì)算機(jī)中進(jìn)行處理。各種排序的穩(wěn)定性，時(shí)間復(fù)雜度和空間復(fù)雜度總結(jié)：類別排序方法時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性平均情況最好情況最壞情況輔助存儲插入排序直接插入O()O(n)O()O(1)穩(wěn)定Shell排序O(n)O()O