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

实验报告实验名称冒泡排序和快速排序班级学号姓名成绩实验概述： 【实验目的及要求】 实验目的通过编程程序达到熟悉并掌握教材中所介绍的几种排序方法。2. 实验内容1）随机产生20位整数2）输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。1.冒泡排序2.快速排序3）纪录每种方法比较次数和移动次数3. 实验步骤和要求同上【实验原理】冒泡排序冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第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-完成的时候，此时令循环结束）。【实验环境】（使用的软硬件）处理器英特尔 Core i5-4200M @ 2.50GHz 双核内存 4 GB ( 记忆科技 DDR3L 1600MHz )操作系统 Windows 10 专业版 64位 ( DirectX 12 )编译环境 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#defineN 20//定义用于比较和交换计数的全局变量staticint compare, move;int main(){int data1[N], data2[N];int i;void bubbleSort(int[20]);void quickSort(int[20], int, int);//创建两个相同的数组用于两种排序方法for (i = 0; iN; i++){data1[i] = rand() % 100 + 1;data2[i] = data1[i];}printf(The original array:\n);for (i = 0; iN; i++)printf(%d , data1[i]);//调用冒泡排序法bubbleSort(data1);//计数器置零compare = 0;move = 0;//调用快速排序法quickSort(data2, 0, N - 1);printf(Quicksort completed!The results are as follows:\n);for (i = 0; iN; i++)printf(%d , data2[i]);print