排序算法可視化

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

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ù)結構設計1.1.基礎知識在計算機所描繪的3D世界中，所有的物體模型（如樹木，人物，山巒）都是通過多邊形網(wǎng)格來逼近表示的，這些多邊形可以是三角形，也可以是四邊形。任何物體都可以用三角形網(wǎng)格來逼近表示，三角形網(wǎng)格是構建物

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

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

8、X, D3DPOOL_DEFAULT, &g_VertexBuffer, NULL) return false;.頂點緩存使用四步曲之三：訪問頂點緩存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);/頂點數(shù)組內(nèi)容的拷貝 g_pVertexBuffer->Unlock();/解鎖1.2.3圖形的繪制 / 【Direct3D渲染五步曲之二】：開始繪制 g_pd3dDevice->BeginScene(); / 開始繪制/ 【Direct3D渲染五步曲之三】：正式繪制，利用頂點緩存繪制圖形 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渲染五步曲之四】：結束繪制 g_pd3dDevice->EndScene(); / 結束繪制 2 三種排序算法2.1直接插入排序（straight insert sort）2.1.1基本原理將一個記錄插入到已排序好的有序表中，從而

12、得到一個新，記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。要點：設立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。2.1.2排序穩(wěn)定性 如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。2.1.3算法的實現(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個元素大于i-1元素，直接插入。小于的話，移動有序表后插入int j= i-4;int x = objDatai.y; /復制為哨兵，即存儲待排序元素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時間復雜度分析從空間來看，它只需要一個記錄的輔助空間，從時間來看，排

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

15、個元素（最后一個數(shù)）比較為止。2.2.2排序穩(wěn)定性選擇排序是給每個位置選擇當前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。那么，在一趟選擇，如果一個元素比當前元素小，而該小的元素又出現(xiàn)在一個和當前元素相等的元素后面，那么交換后穩(wěn)定性就被破壞了。比較拗口，舉個例子，序列5 8 5 2 9，我們知道第一遍選擇第1個元素5會和2交換，那么原序列中兩個5的相對前后順序就被破壞了，所以選擇排序是一個不穩(wěn)定的排序算法。2.2.3算法實現(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時間復雜度分析選擇排序的交換操作介于 0 和 (n - 1） 次之間。選擇排序的比較操作為 n (n

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

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

19、bblesort()/從小到大排序int i,j,t;init();Sleep(500); for(i=0;i<=296;i+=4) /依次比較相鄰的兩個數(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時間復雜度分析若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數(shù)和記錄移動次數(shù)

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

21、292; /初始時,最后位置保持不變int i,j,t;init();Sleep(500);while(curPos>0)int pos=0;/每趟開始時,無記錄交換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;/為下一趟排序作準備2.4.3時間復雜度分析同冒泡

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

23、幾乎減少了一半。算法實現(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時間復雜度分析同冒泡排序一樣，若文件的初始狀態(tài)是正序的，一趟掃描即可完成排序。所需的關鍵字比較次數(shù)和記錄移動次數(shù) 均達到最小值： ，。所以，最好的時間復雜度為。若初始文件是反序的，需要進行趟排序。每趟排序要進行次關鍵字的比較(1in-1)，且

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

26、ata, int low, int high)/從小到大排序/objData0.y=objDatalow.y;int privotKey = objDatalow.y;/基準元素while(low < high) /從表的兩端交替地向中間掃描while(low < high && objDatahigh.y <= privotKey)high=high-4; /從high 所指位置向前搜索，至多到low+1 位置。將比基準元素小的交換到低端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ù)partition的性能，該函數(shù)對于確定的輸入復雜性是確定的。觀察該函數(shù)，我們發(fā)現(xiàn)，對于有n個元素的確定輸入Lp.r，該函數(shù)運行時間顯然為（n）。最壞情況無論適用哪一種方法來選擇pivot，由于我們不知道各個元素間的相對大小關系（若知道就已經(jīng)排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最

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

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

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

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

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

34、>n，轉4 /其中一個子表已合并完，比較選取結束3.選取ri和rj較小的存入輔助數(shù)組rf如果ri<rj，rfk=ri； i+； k+； 轉2否則，rfk=rj； j+； k+； 轉24.將尚未處理完的子表中元素存入rf如果i<=m，將rim存入rfkn /前一子表非空如果j<=n ,  將rjn 存入rfkn /后一子表非空5.合并結束。2.7.2算法穩(wěn)定性歸并排序是一種穩(wěn)定的排序方法。2.7.3算法實現(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 ); /對等長的兩個子表合并i = i+ len;if(i + s <=lenght)Merge(q, rf, i, i+ s -4, lenght -4); /對不等長的兩個子表合并 /把rf的值付給qfor(in

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