2019年整理排序算法可视化

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

2、法快速排序，归并 排序Sorting algorithm visualizationLI Che n Xi ng(School of compu ter and Software engin eeri ng XiHua Uni versity.,Che ngdu 610065 China)Abstract:Sort ing is a compu ter p rogram ming is an imp orta nt op eratio n , and its function is a data eleme nt ( or record ) in any seque nee , rearra

3、nged an ordered seque nee by keyword . There are a lot of sort of way, but its overall p erforma nee , it is hard propo sed method is con sidered to be the best , each method has its own adva ntages and disadva ntages , suitable for differe nt environments (such as the in itial alig nment state reco

4、rd etc.) use . This paper focuses on seve n kinds of sort ing algorithms , n amely, direct insertion sort, simply select sort, bubble sort , bubble sort algorithm is an imp roveme nt , two , quick sort and merge sort . Paper we create objects with DirectX, the object is gen erated by ran dom , witho

5、ut huma n in terve nti on to select or en ter data. Compare the nu mber of key in dicators to compare the nu mber of keywords and mobile .Keywords: bubble sort, simple select ion sort, quick sort , merge sort,straight in sert sort.1数据结构设计1.1.基础知识在计算机所描绘的 形网格来逼近表示的， 形网格来逼近表示，三角形网格是构建物体模型的基本单元。顶点，为了能够

6、通过大量的三角形组成三角形网格来描述物体，3D世界中，所有的物体模型（如树木，人物，山峦）都是通过多边 这些多边形可以是三角形， 也可以是四边形。 任何物体都可以用三角 众所周知，一个三角形有三个 首先需要定义好三角形的顶点（Vertex），三个顶点确定一个三角形，而顶点除了定义每个顶点的坐标位置以外，还含 有颜色等其他属性。在Direct3D中，顶点的具体表现形式是顶点缓存（ Vertex Buffer），顶点缓存保存了顶点数据的内存空间。灵活顶点格式（Flexible Vertex Format，FVF）来描述三角形网格的每个顶点。1.2顶点缓存使用1.2.1设计顶点缓存struct st

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

8、-CreateVertexBuffer(sizeof(objData), 0, D3DFVF_VERTEX, D3D POO L_DEFAULT, &g_VertexBuffer, NULL) retur n false;W 顶点缓存使用四步曲之三：访问顶点缓存for(i = 0;i Lock( 0, sizeof(vertices), (void* )&p Vertices, 0 ) ;/ 加锁 memcpy(ptr, objData, sizeof(objData);/ 顶点数组内容的拷贝g_pVertexBuffer-Unlock();/ 解锁1.2.3图形的绘制/【Direct3D渲染

9、五步曲之二】：开始绘制g_pd3dDevice-BeginScene();/ 开始绘制/【Direct3D渲染五步曲之三】：正式绘制，利用顶点缓存绘制图形g_pd3dDevice-SetRe nderState(D3DRS_SHADEMODE,D3DSHADE_GOURAUD);0, sizeof(CUSTOMVERTEX)g_pd3dDevice-SetStreamSource( 0, g_pVertexBuffer,)；/g_pd3dDevice-SetFVF( D3DFVF_CUSTOMVERTEX g_D3DDevice-Draw Primitive(D3D PT_TRIANGLEST

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

11、序序列出去的顺序就是排好序后的顺序, 插入排序是稳定的。2.1.3算法的实现void StraightI nseilSort()int i,j, pos,t;ini t();/从小到大排序Slee p(2000);for(i= 4; i objDatai-4.y)插入。小于的话，移动有序表后插入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;若第

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

13、ort2.2.1基本原理在要排序的一组数中，选出最小 (或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换，依次类推，直到第n-1个元素(倒数第二个数)和第 n个元素(最后一个数)比较为止。2.2.2排序稳定性选择排序是给每个位置选择当前元素最小的, 素里面给第二个元素选择第二小的，在剩余元 依次类推，直到第n-1个元素，第n个元素不用选择了，比如给第一个位置选择最小的,因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口,举个例子，序列

14、5 8 5 2 9 ，我们知道第一遍选择第 1个元素5会和2交换，那么原序列中 两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。223算法实现void SelectSort()in it();Slee p(2000);int key, tmp;for(i nt i = 0; i=296; i+=4) key = SelectMi nKey(objData, 296,i);if(key != i)tmp = objDatai.y;objDatai.y = objDatakey.y;objDatai+2.y =objDatai.y ;objDatakey.y = tmp; /最

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

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

17、， 我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻， 那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。2.3.3算法实现void bubblesort()/从小到大排序int i,j,t;in it();Slee p(500);for(i=0;i=296;i+=4) /依次比较相邻的两个数的大小for(j=0;j=296-i;j+=4)if(objDataj.yobjDataj+4.y)t=objDataj.y;objDataj.y=objDataj+4.y;objDataj+4.y=t;objD

18、ataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y;234时间复杂度分析若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 移动次数M均达到最小值：M I , Mmin二0。C和记录所以，冒泡排序最好的时间复杂度为。(乳)。若初始文件是反序的，需要进行序。每趟排序要进行次关键字的比较(1 i0)int pos=0;/每趟开始时，无记录交换for(j=0;j=curPos;j+=4)if(objDataj.yobjDataj+4.y)p os=j;/记录交换的位置t=objDataj.y;objDataj.y=objDataj+4

19、.y;objDataj+4.y=t;objDataj+2.y = objDataj.y;objDataj+6.y = objDataj+4.y;curPos=pos;/为下一趟排序作准备243时间复杂度分析同冒泡排序一样，若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字 比较次数C和记录移动次数 M均达到最小值：Crnin二tt - I , Mmin = 0。所以，最好的时间复杂度为 O若初始文件是反序的，需要进行 = 1趟排序。每趟 排序要进行 K f次关键字的比较(1 i n-1),且每次比较都必须移动记录三次来达到交换记 录位置。在这种情况下，比较和移动次数均达到最大值：A最

20、坏时间复杂度为0( )综上，此排序总的平均时间复杂度为O( )o 2.5冒泡排序改进算法二2.5.1基本原理传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者)，从而使排序趟数几乎减少了一半。2.5.2算法实现void bubblesort_2()int i,j,t;int low=0;int high=296;in it();while(low=high)for(j=low;j=high;j+=4)if(objDataj.y=low; j-=4) / 反向冒泡，找到最小者 if(objDataj.

21、yobjDataj+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和记录移动次数 M 均达到最小值：二总I , Mrniri 0。所以，最好的时间复杂度为。（乳）。若初始文件是反序的，需要进行趟排序。每趟排序 要进行rt-i次关键字的比较（1 i Wn -1），且每次比较都必须移动记录三次来达到交换

22、记录 位置。在这种情况下，比较和移动次数均达到最大值：叽= O的2最坏时间复杂度为2综上，此排序总的平均时间复杂度为（ 。2.6快速排序261基本原理 1）选择一个基准元素，通常选择第一个元素或者最后一个元素 2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。3）此时基准元素在其排好序后的正确位置 4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。262排序稳定性快速排序是一个不稳定的排序方法。263算法实现int P artitio n(stD3DVertex objData, i nt low, i

23、 nt high) /从小到大排序/objData0.y=objDatalow.y;/基准元素/从表的两端交替地向中int p rivotKey = 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.y;objDatalow+2.y=objDatalow.y;while(

24、low = 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, i nt low, i nt high)if(low high)/将表一分为二/递归对低子表递归排序递归对高子表递归排序int p rivotLoc = p artiti on(a,low, high);quickSort(a,low, p rivotLoc -4);

25、quickSort(a,p rivotLoc + 4, high);264时间复杂度分析观察该函数，我0 (n)。我们先分析函数partition的性能，该函数对于确定的输入复杂性是确定的。们发现，对于有n个元素的确定输入Lp.r，该函数运行时间显然为最坏情况无论适用哪一种方法来选择pivot，由于我们不知道各个元素间的相对大小关系(若知道就pivot 选已经排好序了)，所以我们无法确定pivot的选择对划分造成的影响。因此对各种择法而言，最坏情况和最好情况都是相同的。n-1个元在后文我我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含 素和1个元素的时候(设输入的表有n个

26、元素)。下面我们暂时认为该猜测正确, 们再详细证明该猜测。对于有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)是过程QuickSort作用于规模为n的输入上的最坏情况的时间，则T(n)=max(T(q)+T(n-q)+0 (n),其中 1 qw n-

27、1 (2)我们假设对于任何 km或)门，转4 其中一个子表已合并完，比较选取结束3选取ri和rj较小的存入辅助数组rf如果 rirj , rfk=ri ；i+ ；k+ ；转 2否则，rfk=rj ;j+ ;k+ ; 转 24.将尚未处理完的子表中元素存入rf如果i=m，将rim存入rfkn II前一子表非空 如果j=n ,将rjn存入rfkn II后一子表非空5合并结束。2.7.2算法稳定性归并排序是一种稳定的排序方法2.7.3算法实现 void Merge(stD3DVertex *r,stD3DVertex *rf, in t i, i nt m, i nt n) int j,k;for(

28、j=m+4,k=i; i=m & j 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;void MergeSort(stD3DVertex *r, stD3DVertex *rf, in t le nght) in it();Slee p(2000);int len = 4;stD3D

29、Vertex *q = r ;/*stD3DVertex *tmp ;*/while(le n len ght) int s = len;len = 2* s ;int i = 0;while(i+ len le nght)Merge(q, rf, i, i+ s-4, i+ len-4 ); /对等长的两个子表合并i = i+ len;if(i + s =le nght)Merge(q,戊i, i+ s -4, lenght -4); /对不等长的两个子表合并 /把rf的值付给qfor(i nt m=0;mle nght;m+=4)qm.y=rfm.y; qm+2.y=qm.y;2.7.4时

30、间复杂度分析一趟归并排序的操作是，调用n/2h次merge将sr1.n中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为 2h的有序段，并存放在 TR1.n中，整个归并排 序需进行Iog2n(以2为底)趟。可见，实现归并排序需和待排记录等数量的辅助空间，其时 间复杂度为O(nlogn)。3运行程序截图3.1直接插入排序3.2简单选择排序 D3D Tutorbl 03; MatricesI.III予h 030 Tutorial 031 MatricesI 回 ihoriad3.3冒泡排序 DD Tutorial 03; Matrkes3.4冒泡排序改进s DSD Tutorial 0

31、3; Matrices3.5冒泡算法改进二3.6快速排序3=D3D Tutonal 03; Matrices D3D Tutorial 03; Matrices.HillIII.I，回3.7归并排序II D3D Tutorial 03; Matrices.IIIT回.111All4 总结排序算法是是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基 础，广泛应用于信息学、系统工程等各种领域。学习排序算法是为了将实际问题中涉及的对 象在计算机中进行处理。各种排序的稳定性，时间复杂度和空间复杂度总结:类别排序方法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况辅助存储插入排序直接插入20（n）0(n)20(n )0(1)稳定Shell排序n130(n)20(n )0(1)不稳定选择排序直接选择20(n )20(n )20(n )0(1)不稳定堆排序o(nsg；)0(nl og2)o(n log2)0(1)不稳定交换排序冒泡排序2o(n )0(n)20(n )0(1)稳定快速排序0(n log；)0( n log2)0(n2)o(n log2)不稳定归并排序o(nsg；)0(nl og2)o(n log2)0(n)稳定稳定性:稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序选择排序算法准