排序算法可视化.doc

《排序算法可视化.doc》由会员分享，可在线阅读，更多相关《排序算法可视化.doc（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、的移动次数。关键词： 直接插入排序，简单选择排序，冒泡排序，冒泡排序改进算法快速排序，归并排序 Sorting algorithmvisualizationLI 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

3、 sequence , rearranged an ordered 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 s

4、tate record etc.) use . This paper 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 , wit

5、hout human intervention to select 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数据结构设计1.1.基础知识在计算机所描绘的3D世界中，所有的物体模型（如树木，人物，山峦）都是通过多边形网格来逼近表示的，这些多边形可以是三角形，也可以

6、是四边形。任何物体都可以用三角形网格来逼近表示，三角形网格是构建物体模型的基本单元。众所周知，一个三角形有三个顶点，为了能够通过大量的三角形组成三角形网格来描述物体，首先需要定义好三角形的顶点（Vertex），三个顶点确定一个三角形，而顶点除了定义每个顶点的坐标位置以外，还含有颜色等其他属性。在Direct3D中，顶点的具体表现形式是顶点缓存（Vertex Buffer），顶点缓存保存了顶点数据的内存空间。灵活顶点格式（Flexible Vertex Format，FVF）来描述三角形网格的每个顶点。1.2顶点缓存使用1.2.1设计顶点缓存struct stD3DVertex float x,

7、 y, z, rhw;/顶点的三维坐标值，x，y，z，以及rhw值（包含经过坐标变换的顶点坐标值） unsigned long color;/顶点的颜色值stD3DVertex objData300;/顶点数组#define D3DFVF_VERTEX (D3DFVF_XYZRHW | D3DFVF_DIFFUSE)/FVF灵活顶点格式1.2.2 创建顶点缓存创建顶点缓存的代码合起来就是：LPDIRECT3DVERTEXBUFFER9 g_pVertexBuffer = NULL; /顶点缓冲区对象/创建顶点缓冲区if(FAILED(g_D3DDevice-CreateVertexBuffer

8、(sizeof(objData), 0, D3DFVF_VERTEX, D3DPOOL_DEFAULT, &g_VertexBuffer, NULL) return false;.顶点缓存使用四步曲之三：访问顶点缓存for(i = 0;i Lock( 0, sizeof(vertices), (void*)&pVertices, 0 ) ;/加锁 memcpy(ptr, objData, sizeof(objData);/顶点数组内容的拷贝 g_pVertexBuffer-Unlock();/解锁1.2.3图形的绘制 / 【Direct3D渲染五步曲之二】：开始绘制 g_pd3dDevice-

9、BeginScene(); / 开始绘制/ 【Direct3D渲染五步曲之三】：正式绘制，利用顶点缓存绘制图形 g_pd3dDevice-SetRenderState(D3DRS_SHADEMODE,D3DSHADE_GOURAUD); g_pd3dDevice-SetStreamSource( 0, g_pVertexBuffer, 0, sizeof(CUSTOMVERTEX) ); g_pd3dDevice-SetFVF( D3DFVF_CUSTOMVERTEX ); g_D3DDevice-DrawPrimitive(D3DPT_TRIANGLESTRIP, 0, 298);/ 【Di

10、rect3D渲染五步曲之四】：结束绘制 g_pd3dDevice-EndScene(); / 结束绘制 2 三种排序算法2.1直接插入排序（straight insert sort）2.1.1基本原理将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。要点：设立哨兵，作为临时存储和判断数组边界之用。2.1.2排序稳定性 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插

11、入排序是稳定的。2.1.3算法的实现void StraightInsertSort()int i,j,pos,t;init();/从小到大排序Sleep(2000);for(i= 4; i 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(j0)break;obj

12、Dataj+4.y = x; /插入到正确位置objDataj+6.y = x;2.1.4时间复杂度分析从空间来看，它只需要一个记录的辅助空间，从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。于当待排序列为正序的时候，所需进行关键字间比较的次数达最小值n-1，记录不需移动；反之，当为逆序的时候，总队比较次数为(n+2)*(n+1)/2,记录移动的次数也达到最大值(n+4)*(n-1)/2。若待排记录是随机的，取上述最小值与最大值的平均值，约为n*n/4。所以它的时间复杂度为。2.2简单选择排序（simple selection sort）2.2.1基本原理在要排序的一组数中，选出

13、最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。2.2.2排序稳定性选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2

14、交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。2.2.3算法实现void SelectSort()init();Sleep(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+

15、2.y = objDatakey.y;2.2.4时间复杂度分析选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数，比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+.+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。该算法运行时间与元素的初始排列无关。不论初始排列如何，该算法都必

16、须执行n-1趟，每趟执行n-i-1次关键字的比较，这样总的比较次数为：所以，简单选择排序的最好、最坏和平均情况的时间复杂度都为。2.3冒泡排序（bubble sort）2.3.1基本原理在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。2.3.2排序稳定性冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，

17、那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。2.3.3 算法实现void bubblesort()/从小到大排序int i,j,t;init();Sleep(500); for(i=0;i=296;i+=4) /依次比较相邻的两个数的大小 for(j=0;j=296-i;j+=4)if(objDataj.y0)int pos=0;/每趟开始时,无记录交换for(j=0;j=curPos;j+=4)if(objDataj.yobjDataj+4.y)pos=j;/记录交换的位置 t=objDataj.y;objDa

18、taj.y=objDataj+4.y;objDataj+4.y=t;objDataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y; curPos=pos;/为下一趟排序作准备2.4.3时间复杂度分析同冒泡排序一样，若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：，。所以，最好的时间复杂度为。若初始文件是反序的，需要进行趟排序。每趟排序要进行次关键字的比较(1in-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：最坏时间复杂度为综上，此排序总的平均时间复杂

19、度为。2.5冒泡排序改进算法二2.5.1基本原理传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) ,从而使排序趟数几乎减少了一半。2.5.2算法实现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=low; j-=4) /反向冒泡,找到最小者 if(objDataj.yobjDataj+4.y)t=objDataj.y;ob

20、jDataj.y=objDataj+4.y;objDataj+4.y=t;objDataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y; low+=4;2.5.3时间复杂度分析同冒泡排序一样，若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：，。所以，最好的时间复杂度为。若初始文件是反序的，需要进行趟排序。每趟排序要进行次关键字的比较(1in-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：最坏时间复杂度为综上，此排序总的平均时间复杂度为。2.6快速排序2

21、.6.1基本原理1）选择一个基准元素,通常选择第一个元素或者最后一个元素,2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。3）此时基准元素在其排好序后的正确位置4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。2.6.2排序稳定性快速排序是一个不稳定的排序方法。2.6.3算法实现int partition(stD3DVertex objData, int low, int high)/从小到大排序/objData0.y=objDatalow.y;int privotKey = objDatalow.y

22、;/基准元素while(low high) /从表的两端交替地向中间扫描while(low high & objDatahigh.y = privotKey)high=high-4; /从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端SWAP(objDatalow.y, objDatahigh.y);objDatahigh+2.y=objDatahigh.y;objDatalow+2.y=objDatalow.y; while(low = privotKey )low=low+4;SWAP(objDatalow.y, objDatahigh.y);objData

23、low+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(a, low, high); /将表一分为二quickSort(a, low, privotLoc -4);/递归对低子表递归排序quickSort(a, privotLoc + 4, high);/递归对高子表递归排序2.6.4时间复杂度分析我们先分析函数partition的性能，该函数对于

24、确定的输入复杂性是确定的。观察该函数，我们发现，对于有n个元素的确定输入Lp.r，该函数运行时间显然为（n）。最坏情况无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系（若知道就已经排好序了），所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言，最坏情况和最好情况都是相同的。我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候（设输入的表有n个元素）。下面我们暂时认为该猜测正确，在后文我们再详细证明该猜测。对于有n个元素的表Lp.r，由于函数Partition的计算时间为（n），所以快速排序在序

25、坏情况下的复杂性有递归式如下：T(1)=(1),T(n)=T(n-1)+T(1)+(n) (1)用迭代法可以解出上式的解为T(n)=（n2）。这个最坏情况运行时间与插入排序是一样的。下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。设T(n）是过程Quick_Sort作用于规模为n的输入上的最坏情况的时间，则T(n)=max(T(q)+T(n-q)+（n)，其中1qn-1 (2)我们假设对于任何km 或jn，转4 /其中一个子表已合并完，比较选取结束3.选取ri和rj较小的存入辅助数组rf如果rirj，rfk=ri； i+； k+； 转2否则，rfk

26、=rj； j+； k+； 转24.将尚未处理完的子表中元素存入rf如果i=m，将rim存入rfkn /前一子表非空如果j=n , 将rjn 存入rfkn /后一子表非空5.合并结束。2.7.2算法稳定性归并排序是一种稳定的排序方法。2.7.3算法实现void Merge(stD3DVertex *r,stD3DVertex *rf, int i, int m, int n)int j,k;for(j=m+4,k=i; i=m & j 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;whil

27、e(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)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 lengh

28、t)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(int m=0;mlenght;m+=4)qm.y=rfm.y;qm+2.y=qm.y;2.7.4时间复杂度分析一趟归并排序的操作是，调用n/2h次merge将sr1.n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段，并存放在TR1.n中，整个归并排序需进行log2n(以2为底)趟。可见，实

29、现归并排序需和待排记录等数量的辅助空间，其时间复杂度为O(nlogn)。 3运行程序截图 3.1 直接插入排序3.2简单选择排序3.3冒泡排序3.4冒泡排序改进一3.5冒泡算法改进二3.6快速排序3.7归并排序 4总结排序算法是是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对象在计算机中进行处理。各种排序的稳定性，时间复杂度和空间复杂度总结：类别排序方法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况辅助存储插入排序直接插入O()O(n)O()O(1)稳定Shell排序O(n)O()O(1)不稳定

30、选择排序直接选择O()O()O()O(1)不稳定堆排序O()O()O()O(1)不稳定交换排序冒泡排序O()O(n)O()O(1)稳定快速排序O()O()O()O()不稳定归并排序O()O()O()O(n)稳定稳定性：稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序选择排序算法准则：每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。选择排序算法的依据影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得

31、考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：1待排序的记录数目n的大小；2记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；3关键字的结构及其分布情况；4对排序稳定性的要求。设待排序元素的个数为n.1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序：如果内存空间允许且要求稳定性的，归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高

32、。2）当n较大，内存空间允许，且要求稳定性 =归并排序3）当n较小，可采用直接插入或直接选择排序。直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序5） 一般不使用或不直接使用传统的冒泡排序。参考文献：1 严蔚敏 吴伟民.数据结构（C语言版）3.版本.北京.清华大学出版社,1997:1335. 2M. G. Rahman, M. Z. Islam, T. Bossomaier, J. Gao, Cairad: A co-appearance based analysisfor sorting algor

33、ithm, in: Neural Networks (IJCNN), The 2012International Joint Conference on, IEEE, Brisbane, Australia, 2012, pp. 1 10. doi:10.1109/IJCNN.2012.6252669.3 W. Young, G. Weckman, W. Holland, A survey of methodologies for the sorting algorithm: limitations and benefits, Theoretical Issues in Ergonomics Science 12 (1)(2011) 1543.