数据结构之排序比较

《数据结构之排序比较》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构之排序比较实验目的：通过比较选择，插入，冒泡和交换排序的执行时间，明口这几种排序的原理和复杂程度，并通过实验分析在数组为升序，降序，无序时算法的执行效率。实验原理：选择排序：算法从位置0开始，判断表屮最小元素的小标。一旦找到最小元素，就把这个元素与v[0]的内容进行交换。即v[0]中存放的是最小的元素，而表中其他元素则处于无序状态。接着向后移动位置1,判断子表v[l]-v[n-l]中最小元素的位置。完成交换后，前两个位置是有序的，接着对位置2到m2重复这个过程。在位置ml处不进行选择，这是因为v[n-l]是最大的元素。经过ml趟排序得到有序结果。

2、算法复杂度为O(n*n)o插入排序：假设第1个元素处于正确的位置，因此，此函数需要在1到v.size()-l范围内进行n・l遍来排序其余的元素。插入排序的基木思想是经过i-1遍处理后v[O..i-l]B排好序。第i遍处理仅将v[i]插入v[O..i-l]的适当位置，使得v[O.・i]又是排好序的序列。复制v[i]到一个称作target的临时对彖屮。向下扫描表，首先比较target和如果v[i-1]

3、v[O..i]已排好序,第i遍处理就结束了,否则v[i]=v[i-l],即把每个大于target的元素右移1个位置，一旦确定了正确的位置，

4、复制target到那个位置。若v[i]小于以前任何一个排序过的元素时，则排序在表的开始处(j=0)停止。这样，v[i]将占有新的排序后子表的第1个位置。复杂度O(n*n),最好是O(n)。冒泡排序：冒泡排序的基本思想是，将待排序的元素看作是竖着排列的“气泡"，较小的元素比较轻，从而要往上浮。每进行一遍处理，就是自底向上检查一遍这个序列，如果发现两个相邻元素的顺序不对，即“轻,啲元素在下面，就交换它们的位置。在处理一遍Z后，“最轻"的元素就浮到了最高位置；处理二遍Z后，“次轻”的元素就浮到了次高位置。在进行第i遍处理时，不必检查第i高位置以上的元素，因为经

5、过前面i・l遍的处理，它们已正确地排好序。复杂度O(n*n)o交换排序：此算法重复扫描向量，并交换元素，直到表按升序排列。从第一个元素开始，依次和第二第三个元素比较，直到n=v.size()-1,若v[O]>v[l],贝ij两者交换。继续与v[3]比较,若v[0]>v[2],则交换,重复此过程，直到v[l]为最小元素。再从第二个元素，找到v[l]〜v[n・l]中最小的元素，对位置2到n・2重复这个过程。复杂度O(n*n)o实验原代码:#include#include#include"d_timer.h"#inclucl

6、eud_ranclom.hnusingnamespacestd：voidselectionSort(vector&v){intsmallindex,pass,j,temp,n=v.size()；for(pass=0；pass

7、择排序voidinsertionSort(vector&v){inti,j,target,n=v>size()；for(i=l；i0&&target&v){inttemp,n=v.sizeO；for(inti=0Uv[j+l]){temp=v[j]；v[j]=v[j+1]；vlj+l]=temp

8、；冒泡排序交换排序主程序voidexchangesort(vector&v)intvsize=v.size(),temp；for(intpass=O；pass〈vsizeT；pass++)for(int匸pass；iv[i+11){temp=v[pass]；v[pass]=v[i+1]；v[i+1]=temp；}}intmainO{randomNumberrnd；intvalue,i；vectorvl,v2,v3,v4,v5,v6,v7,v8,v9,vl0,vll,vl2；for(i=0

9、；i<10000；i++){value=rnd.random仃()()()())