北航计算机软件技术基础实验报告计软实验报告3——冒泡排序和快速排序

实验报告实验名称冒泡排序和快速排序班级学号姓名成绩实验概述：【实验目的及要求】1.实验目的通过编程程序达到熟悉并掌握教材中所介绍的几种排序方法。2.实验内容1）随机产生20位整数2）输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。1.冒泡排序2.快速排序3）纪录每种方法比较次数和移动次数3.实验步骤和要求同上【实验原理】1.冒泡排序冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。2.快速排序设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。一趟快速排序的算法是：1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；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步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。【实验环境】（使用的软硬件）处理器英特尔Corei5-4200M@2.50GHz双核内存4GB(记忆科技DDR3L1600MHz)操作系统Windows10专业版64位(DirectX12)编译环境Dev-C++5.6.1编译语言C实验内容：【实验方案设计】1.利用rand()函数生成20个随机数，并放到两个数组中分别用于冒泡排序和快速排序2.利用比较和交换，每次讲一个最大的元素放到数组末尾，实现冒泡排序3.在每次快速排序的算法中，先设置一个基准值，利用头指针和尾指针轮流比较数组中的元素，若遇到不属于low或high的元素则交换到另一个组中去，最后将基准值放入首尾指针相交的位置上。利用递归调用实现对整个数组的快速排序算法。4.整理实验结果，写出实验报告【实验过程】（实验步骤、记录、数据、分析）实验一：源代码：/*实验3:冒泡排序和快速排序1.随机产生20位整数2.输入序列,编写程序,按下列排序方法将序列从小到大排序并输出。(1)冒泡排序(2)快速排序3.纪录每种方法比较次数和移动次数*/#includestdio.h#includestdlib.h#defineN20//定义用于比较和交换计数的全局变量staticintcompare,move;intmain(){intdata1[N],data2[N];inti;voidbubbleSort(int[20]);voidquickSort(int[20],int,int);//创建两个相同的数组用于两种排序方法for(i=0;iN;i++){data1[i]=rand()%100+1;data2[i]=data1[i];}printf(Theoriginalarray:\n);for(i=0;iN;i++)printf(%d,data1[i]);//调用冒泡排序法bubbleSort(data1);//计数器置零compare=0;move=0;//调用快速排序法quickSort(data2,0,N-1);printf(Quicksortcompleted!Theresultsareasfollows:\n);for(i=0;iN;i++)printf(%d,data2[i]);printf(\nComparetimes:%d\n,compare);printf(Movetimes:%d,move);return0;}//冒泡排序法voidbubbleSort(inta[N]){inti,j,temp;compare=0;move=0;//总共循环N-2轮for(i=0;iN-1;i++){//每轮循环从头开始,到有序序列前结束for(j=0;jN-i-1;j++){//比较交换,将较大的数放到后面if(a[j+1]a[j]){temp=a[j+1];a[j+1]=a[j];a[j]=temp;move++;}compare++;}}printf(\n\nBubblesortcompleted!Theresultsareasfollows:\n);for(i=0;iN;i++)printf(%d,a[i]);printf(\nComparetimes:%d\n,compare);printf(Movetimes:%d\n\n,move);}//快速排序法voidquickSort(inta[N],intleft,intright){//将数组一分为二的键值intpivotkey;if(leftright){//第一次排序将数组一分为二pivotkey=partition(a,left,right);//递归调用,对数据比键值小的数组排序quickSort(a,left,pivotkey-1);//递归调用,对数据比键值大的数组排序quickSort(a,pivotkey+1,right);}}//进行一次快速排序intpartition(inta[N],intleft,intright){intkey,i,low=left,high=right;//设置基准key=a[low];while(lowhigh){//high中数据比基准大,则向前依次查找while((lowhigh)&&(a[high]key)){high--;compare++;}//如果不是两指针相遇,说明存在需要交换到low的值if(lowhigh){a[low]=a[high];move++;}//low中数据比基准小,则向后依次查找while((lowhigh)&&(a[low]=key)){low++;compare++;}//如果不是两指针相遇,说明存在需要交换到high的值if(lowhigh){a[high]=a[low];move++;}}//首尾指针相遇后,将基准放入空位a[low]=key;//返回此时的键值returnlow;}运行结果：【结论】（结果）1.由实验结果知，编写的冒泡排序法和快速排序法都成功的将一个无序的数组排成了一个有序数组并打印输出，说明这两种算法是可行的。2.从记录的比较值和移动值的大小来看，冒泡排序比较了190次，即(N*N-1)/2次，交换了87次；快速排序法比较了64次，交换了27次。可以明显的看出快速排序法的效率较高，运行速度较快。可以猜想，当数据量进一步扩大时，快速排序法将比冒泡排序法的平均运行速度更短【小结】这次的实验题目是关于两种算法的。由于在之前的c语言学习中我已经对这两种算法有了一个大致的了解，所以编写源程序及调试并不困难，最后的运行结果也是正确的。但是，与之前的学习不同的是，在本次试验中加入了对比较和交换次数的比较。这就涉及到了数据结构中算法的时间复杂度问题。经过查阅资料得知，冒泡排序最好的时间复杂度为O(n)。若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：。冒泡排序的最坏时间复杂度为O(n2)。综上，冒泡排序总的平均时间复杂度为O(n2)。快速排序法的最坏情况运行时间为θ（n2），且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。最好情况是O(nlogn),出现在每次划分过程产生的区间大小都为n/2时。综上，快速排序总的平均时间复杂度为O(n2)。在数据量小时两者区别不大，但在数据量大且数据较无序时宜用快速排序法进行排序。另外，在编写代码的过程中，我也对快速排序法和冒泡排序法的逻辑思路有了一个更清楚的认识。快速排序法使用了递归和分治的思想，通过设置头指针和尾指针一步步将数组分成两部分，最后完成一趟时空出的位置就是基准值的位置。再利用递归的思想，把数组分成两部分，对每一部分进行快速排序，最后完成排序。指导教师评语及成绩：成绩：指导教师签名：批阅日期：