【2019年整理】排序算法可视化

1、排序算法可视化摘要：排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。排序的方法有很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境(如记录的初始排列状态等)下使用。本论文主要讨论七种排序算法，即直接插入排序，简单选择排序，冒泡排序，冒泡排序改进算法一，二，快速排序与归并排序。论文中我们用DirectX创建对象，对象由随机生成，无需人工干预来选择或者输入数据。比较的指标为关键字的比较次数和关键字的移动次数。关键词：直接插入排序，简单选择排序，冒泡排序，冒泡排序改进算法快速排序

2、，归并排序SortingalgorithmvisualizationLIChenXing(SchoolofcomputerandSoftwareengineeringXiHuaUniversity.,Chengdu610065China)Abstract:Sortingisacomputerprogrammingisanimportantoperation,anditsfunctionisadataelement(orrecord)inanysequence,rearrangedanorderedsequencebykeyword.Therearealotofsortofway,butitso

3、verallperformance,itishardproposedmethodisconsideredtobethebest,eachmethodhasitsownadvantagesanddisadvantages,suitablefordifferentenvironments(suchastheinitialalignmentstaterecordetc.)use.Thispaperfocusesonsevenkindsofsortingalgorithms,namely,directinsertionsort,simplyselectsort,bubblesort,bubblesor

4、talgorithmisanimprovement,two,quicksortandmergesort.PaperwecreateobjectswithDirectX,theobjectisgeneratedbyrandom,withouthumaninterventiontoselectorenterdata.Comparethenumberofkeyindicatorstocomparethenumberofkeywordsandmobile.Keywords:bubblesort,simpleselectionsort,quicksort,mergesort,straightinsert

5、sort.1数据结构设计1.1 .基础知识在计算机所描绘的3D世界中，所有的物体模型(如树木，人物，山峦)都是通过多边形网格来逼近表示的，这些多边形可以是三角形，也可以是四边形。任何物体都可以用三角形网格来逼近表示，三角形网格是构建物体模型的基本单元。众所周知，一个三角形有三个顶点，为了能够通过大量的三角形组成三角形网格来描述物体，首先需要定义好三角形的顶点(Vertex),三个顶点确定一个三角形，而顶点除了定义每个顶点的坐标位置以外，还含有颜色等其他属性。在Direct3D中，顶点的具体表现形式是顶点缓存(VertexBuffer),顶点缓存保存了顶点数据的内存空间。灵活顶点格式(Flexi

6、bleVertexFormat,FVF)来描述三角形网格的每个顶点。1.2 顶点缓存使用1.2.1 设计顶点缓存structstD3DVertex（floatx,y,z,rhw;顶点的三维坐标值，x,y,z,以及rhw值（包含经过坐标变换的顶点坐标值）unsignedlongcolor;/顶点的颜色值;stD3DVertexobjData300;/顶点数组#defineD3DFVF_VERTEX(D3DFVF_XYZRHW|D3DFVF_DIFFUSE)/FVF灵活顶点格1.2.2 创建顶点缓存创建顶点缓存的代码合起来就是：LPDIRECT3DVERTEXBUFFER9g_pVertexBuf

7、fer=NULL;顶点缓冲区对象/创建顶点缓冲区if(FAILED(g_D3DDevice->CreateVertexBuffer(sizeof(objData),0,D3DFVF_VERTEX,D3DPOOL_DEFAULT,&g_VertexBuffer,NULL)returnfalse;IV.顶点缓存使用四步曲之三：访问顶点缓存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

8、*2);objDatai.y=j;objDatai+1.y=400;objDatai+2.y=j;objDatai+3.y=400;objDatai.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_p

9、VertexBuffer->Lock(0,sizeof(vertices),(void*)&pVertices,0);/力口锁memcpy(ptr,objData,sizeof(objData);/顶点数组内容的拷贝g_pVertexBuffer->Unlock();/解锁1.2.3 图形的绘制/【Direct3D渲染五步曲之二】：开始绘制g_pd3dDevice->BeginScene();/开始绘制/【Direct3D渲染五步曲之三】：正式绘制，利用顶点缓存绘制图形g_pd3dDevice->SetRenderState(D3DRS_SHADEMODE,D3

10、DSHADE_GOURAUD);g_pd3dDevice->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 直接插入排序(straightinsertsort)2.1.1 基本原理将一个记录

11、插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。要点：设立哨兵，作为临时存储和判断数组边界之用。2.1.2 排序稳定性如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。2.1.3 算法的实现voidStraightInsertSort()inti,j,pos,t;init();从小到大排序Sleep(2000);for(i=4;i<300;i+=4)if

12、(objDatai.y>objDatai-4.y)/若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入intj=i-4;intx=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 时间复杂度分析从空间来看，它只需要一个记录的辅助空间，从时间来看，排序的基本操作为：比较两个关键

13、字的大小和移动记录。于当待排序列为正序的时候，所需进行关键字间比较的次数达最小值n-1，记录不需移动；反之，当为逆序的时候，总队比较次数为(n+2)*(n+1)/2,记录移动的次数也达到最大值(n+4)*(n-1)/2。若待排记录是随机的，取上述最小值与最大值的平均值，约为n*n/4。所以它的时间复杂度为5H2.2 简单选择排序(simpleselectionsort)2.2.1 基本原理在要排序的一组数中，选出最小(或者最大)的一个数与第1个位置的数交换；然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换，依次类推，直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为

14、止。2.2.2 排序稳定性选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列58529,我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。2.2.3 算法实现voidSelectSort()init();Sleep(2000);intkey,

15、tmp;for(inti=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-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。比较次数。忖),比较次数与关键字的初

16、始状态无关，总的比较次数N=(n-1)+(n-2)+.+1=n*(n-1)12。交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1、次。交换次数比冒泡排序少多了，由于交换所需CPU寸间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为。(川)。2.3 冒泡排序(bubblesort)2.3.1 基本原理在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻

17、的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。2.3.2 排序稳定性冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。2.3.3 算法实现voidbubblesort()从小到大排序inti,j,t;init();Sleep(500);for(

18、i=0;i<=296;i+=4)/依次比较相邻的两个数的大小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 时间复杂度分析若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数Af均达到最小值：Cmin="-1,Mmi口二°。所以，冒泡排序最好的时间复杂度为若初始文

19、件是反序的，需要进行H1趟排序。每趟排序要进行并-i次关键字的比较(1wiwn-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：Coax=n1=On2=Ofn2)冒泡排序的最坏时间复杂度为111综上，因此冒泡排序总的平均时间复杂度为°(H)。2.4 冒泡排序改进算法一2.4.1 基本原理pos位置设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于之后的记录均已交换到位，故在进行下一趟排序时只要扫描到pos位置即可。2.4.2 算法实现voidbubblesort_1()从小到大排序intcurPos=292;初始时，

20、最后位置保持不变inti,j,t;init();Sleep(500);while(curPos>0)intpos=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 时间复杂度分析同冒泡排序一样，若文件的初始状态是正序的，

21、一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin=n-1,Mmin=0。所以，最好的时间复杂度为0(折。若初始文件是反序的，需要进行此一1趟排序。每趟排序要进行n_j次关键字的比较(1<i<n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：l=地>=。(周Ma=3吗-D=O(n2)最坏时间复杂度为11'1综上，此排序总的平均时间复杂度为0(2)。2.5 冒泡排序改进算法二2.5.1 基本原理传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，我们考虑利用在每趟排序中进行正向和反向两

22、遍冒泡的方法一次可以得到两个最终值(最大者和最小者)，从而使排序趟数几乎减少了一半。2.5.2 算法实现voidbubblesort_2()inti,j,t;intlow=0;inthigh=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-

23、=4;for（j=high;j>=low;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 时间复杂度分析同冒泡排序一样，若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数Af均达到最小值：。血如=M-1,Mmin二。所以，最好的时间复杂度为。（打）。若初始文件是反序的，需要进行趟排序。

24、每趟排序要进行修一i次关键字的比较（1WiWn-1）,且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：=。（的卜=O（n?）ji最坏时间复杂度为11'ji综上，此排序总的平均时间复杂度为。（打）。2.6 快速排序2.6.1 基本原理1）选择一个基准元素，通常选择第一个元素或者最后一个元素，2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。3）此时基准元素在其排好序后的正确位置4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。2.6.2 排序稳定性快速排序

25、是一个不稳定的排序方法。2.6.3 算法实现intpartition(stD3DVertexobjData,intlow,inthigh)(从小到大排序/objData0.y=objDatalow.y;intprivotKey=objDatalow.y;基准元素while(low<high)从表的两端交替地向中间扫描while(low<high&&objDatahigh.y<=privotKey)high=high-4;从high所指位置向前搜索，至多到low+1位置。将比基准元素小的交换到低端SWAP(objDatalow.y,objDatahigh.y);

26、objDatahigh+2.y=objDatahigh.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;returnlow;快速排序voidquickSort(stD3DVertexa,intlow,inthigh)if(low<high)intprivotLoc=par

27、tition(a,low,high);将表分为二quickSort(a,low,privotLoc-4);递归对低子表递归排序quickSort(a,privotLoc+4,high);递归对高子表递归排序2.6.4 时间复杂度分析我们先分析函数partition的性能，该函数对于确定的输入复杂性是确定的。观察该函数，我们发现，对于有n个元素的确定输入Lp.r,该函数运行时间显然为。(n)。最坏情况无论适用哪一种方法来选择pivot,由于我们不知道各个元素间的相对大小关系(若知道就已经排好序了)，所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言，最坏情况和最好情

28、况都是相同的。我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候(设输入的表有n个元素)。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。对于有n个元素的表Lp.r,由于函数Partition的计算时间为0(n),所以快速排序在序坏情况下的复杂性有递归式如下：T(1)=0(1),T(n)=T(n-1)+T(1)+0(n)(1)用迭代法可以解出上式的解为T(n)=0(n2)。这个最坏情况运行时间与插入排序是一样的。下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。设T(n)是过程Quick_Sor

29、t作用于规模为n的输入上的最坏情况的时间，则T(n)=max(T(q)+T(n-q)+0(n),其中1wqwn-1(2)我们假设对于任何k<n,总有T(k)wck,其中c为常数；显然当k=1时是成立的。将归纳假设代入(2),得到：T(n)<max(cq2+c(n-q)2)+0(n)=c*max(q2+(n-q)2)+0(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)+0(n)wcn2只要c足够大，上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n)<cn。这

30、样，排序算法的最坏情况运行时间为。(n2),且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。时间复杂度为)。最好情况如果每次划分过程产生的区间大小都为n/2,则快速排序法运行就快得多了。这时有:T(n)=2T(n/2)+0(n),T(1)=0(1)(3)解得：T(n)=0(nlogn)快速排序法最佳情况下执行过程的递归树如下图所示，图中lgn表示以2位底的对数，而本文中用logn表示以2位底的对数.由于快速排序法也是基于比较的排序法，其运行时间为Q(nlogn),所以如果每次划分过程产生的区间大小都为n/2,则运行时间0(nlogn)就是最好情况运行时间。但是，

31、是否一定要每次平均划分才能达到最好情况呢？要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分，乍一看该划分很不对称。我们可以得到递归式：T(n)=T(n/10)+T(9n/10)+0(n),T(1)=0(1)(4)请注意树的每一层都有代价n,直到在深度10g10n=0(logn)处达到边界条件，以后各层代价至多为n。递归于深度10g10/9n=0(logn)处结束。这样，快速排序的总时间代价为T(n)=0(nlogn),从渐进意义上看就和划分是在中间进行的一样。事实上，即使是99:1的划分时间代价也为0(nlogn)。其原因在于，任何一种按

32、常数比例进行划分所产生的递归树的深度都为0(nlogn),其中每一层的代价为O(n),因而不管常数比例是什么，总的运行时间都为0(nlogn),只不过其中隐含的常数因子有所不同。(关于算法复杂性的渐进阶，请参阅算法的复杂性)平均情况快速排序的平均运行时间为0(nlogn)。2.7 归并排序2.7.1 基本原理归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。设rin由两个有序子表巾m和rm+1n组成，两个子表长度分别为n-i+1、n-m。1 .j=m+1；k=i；i=i;/置两个子

33、表的起始下标及辅助数组的起始下标2 .若i>m或j>n,转4其中一个子表已合并完，比较选取结束3 .选取ri和rj较小的存入辅助数组rf如果ri<rj,rfk=ri;i+;k+;转2否则，rfk=rj;j+;k+;转24 .将尚未处理完的子表中元素存入rf如果i<=m,将rim存入rfkn/前一子表非空如果j<=n,将巾n存入rfkn/后一子表非空5 .合并结束。6 .7.2算法稳定性归并排序是一种稳定的排序方法。7 .7.3算法实现voidMerge(stD3DVertex*r,stD3DVertex*rf,inti,intm,intn)(intj,k;for(

34、j=m+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；)elserfk.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;)voidMergeSort(stD3DVertex*r,stD3DVertex*rf,intlenght)init();Sleep(2000);intlen=4;s

35、tD3DVertex*q=r;/*stD3DVertex*tmp;*/while(len<lenght)ints=len;len=2*s;inti=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(intm=0;m<lenght;m+=4)qm.y=rfm.y;qm+2.y=qm.y;8 .7.4时间复杂度分析一趟归并排序的操作是，调用n/2h次mer

36、ge将sr1.n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在TR1n中，整个归并排序需进行10g2n(以2为底)趟。可见，实现归并排序需和待排记录等数量的辅助空间，其时间复杂度为O(nlogn)。3运行程序截图3.1直接插入排序3.2简单选择排序3.3冒泡排序3.5冒泡算法改进二3.6快速排序3.7归并排序4总结排序算法是是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。各种排序的稳定性，时间复杂度和空间复杂度总结:类别排序方法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况辅助存储插入排序直接插入2O(n)O(n)2O(n)O(1)稳定Shell排序13nO(n)2O(n)O(1)不稳定选择排序直接选择2O(n)2O(n)2