选择类排序比较数据结构综合实验报告

《选择类排序比较数据结构综合实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构综合实验报告2015/2016(2)题目：交换类排序算法实现和比较学号：28班级：计1411分析21.1课题描述21.2系统功能21・2分析课题21）冒泡排序排序22）快速排序22设计22.1类的设计21）排序类22.2冒泡排序算法的设计3（1）冒泡排序排序3（2）快速排序33算法的实现33.1主要算法的实现3（1）快速排序3（2）冒泡排序44运行结果55出现的错误及错误原因66总结76.1和同点与不同点7（1）相同点7（1）不同点71）冒泡排序（稳定的排序算法）72）快速排序（不稳定的排序算法）77.2快

2、速排序和冒泡排序比较77参考文献71分析1.1课题描述实现简单-选择排序、堆排序算法，并比较两种算法的比较次数和移动次数。1・2系统功能(1)输入：输入不少于10个元素的无序、正序、降序三组序列；(2)排序：分别用堆排序和简单选择排序算法进行排序，并显示各自的比较次数和移动次数；(3)输出：输出每组元索序列、每种算法的比较次数和移动次数；(4)分析：对结果进行简单的分析。图1・1用例图1.2分析课题1)冒泡排序排序1.比较相邻的元索。如果第一个比第二个大，就交换他们两个。2.对每一对相邻元素作同样的工作，从开始第一

3、对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3.针对所有的元素重复以上的步骤，除了最后一个。4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。2)快速排序设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动2设计2.1类的设计1)排序类Cl

4、asssortlist//排序类{private:intcurrentsize;//数据表中数据的个数public:type*arr;//存储向量的存储表sortlist():currentsize(0){arr=newtype[maxsize];}//构造函数sortlist(intn){arr二newtype[maxsize];currentsize二n;}voidinsert(inti,typex){arr[i]二x;}^sortlist(){delete[]arr;}//析构函数voidswap(type&

5、x,type&y)//交换函数{typetemp=x;x=y;y=temp;}voidBubbleSort();冒泡排序voidoutput();voidquicksort(intlow,inthigh);//快速排序};2・2冒泡排序算法的设计(1)冒泡排序排序①在一组元素中选择具有最小排序码的元素：②若它不是这组元索中的第一个元索，则将它与这组元素中的第一元索对调；③在这组元素中剔除这个具冇最小排序码的元素，在剩下的元素屮重复执行第①②步，直到剩余元素只有一个为止。(2)快速排序1)设置两个变量i、j,排序开始

6、的时候:i=0,j=N-l；2)以第一个数组元索作为关键数据，赋值给key,即key二A[0]；3)从j开始向前搜索，即由后开始向前搜索(J-),找到第一个小于key的值A[j],将A[j]和A[i]互换；4)从i开始向后搜索，即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;5)重复第3、4步,直到匸j;(3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于koy的时候改变j、i的值，使得j二j-l,i二i+1,直至找到为止。找到符合条件的值，进行交

7、换的吋候i,j指针位置不变。另外，匸二j这一过程一定正好是i+或j-完成的时候，此时令循环结束)。3算法的实现3.1主要算法的实现(1)快速排序templatevoidsortlist〈type>::quicksort(intlow,inthigh)//快速排序{inti=low,j=high;typetemp=arr[low];//取区间笫一个位置为基准{{whilc(i

8、i],arr[j]);i++;Qremove++;}while(i〈j&&temp>=arr[i])i++;{Qcompare++;}if(i