快速排序实验报告

快速排序算法c语言实验报告

冒泡法和选择法排序C程序实验报告 实验六：冒泡法排序

物理学416班 赵增月 F12 2011412194日期：2013年10

月31日 一·实验目的 1.熟练掌握程序编写步骤；

2.学习使用冒泡法和选择法排序； 3.熟练掌握数组的定义和输入输出方法。

二·实验器材

1.电子计算机； 2.VC6.0

三·实验内容与流程 1.流程图

（1）冒泡法

(2)选择法 2.输入程序如下： （1）冒泡法 #includestdio.h void main() { int a[10]; int i,j,t; printf(请输入10个数字：\n);

for(i=0;i10;i++)scanf(%d,&a[i]); printf(\n); for(j=0;j9;j++)for(i=0;i9-j;i++) if(a[i]a[i+1]) { t=a[i]; a[i]=a[i+1];

a[i+1]=t; } printf(排序后如下：\n); for(i=0;i10;i++) printf(%d,a[i]);

printf(\n); } （2）选择法 #includestdio.h void main() { int a[10]; int i,j,t,k;

printf(请输入10个数字：\n); for(i=0;i10;i++)scanf(%d,&a[i]);

printf(\n); for(i=0;i9;i++) {k=i;for(j=i+1;j10;j++) if

(a[k]a[j])k=j;t=a[i];a[i]=a[k];a[k]=t; }

printf(排序后如下：\n); for(i=0;i10;i++)printf(%d,a[i]); printf(\n); }

四．输出结果 （1冒泡法） 请输入10个数字： 135****2468

排序后如下： 12345678910 （2）选择法 输出结果

数据结构与算法设计

实验报告

（2016 — 2017 学年第1 学期）

实验名称：

年 级：

专 业：

班 级：

学 号：

姓 名：

指导教师：

成都信息工程大学 通信工程学院 一、 实验目的

验证各种简单的排序算法。在调试中体会排序过程。

二、实验要求

（1） 从键盘读入一组无序数据，按输入顺序先创建一个线性表。

（2） 用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。

三、实验步骤

1、 创建工程（附带截图说明）

2、 根据算法编写程序（参见第六部分源代码）

3、 编译

4、 调试

四、实验结果图

图 1-直接输入排序

图 2-冒泡排序

图 3-直接选择排序

五、心得体会

与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。

本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。

六、源代码

要求：粘贴个人代码，以便检查。

#include

#define MAXSIZE 100

typedef int KeyType;

typedef int DataType;

共 4 页 第 1 页 制表单位：设备处 天津商业大学学生实验报告

开课实验室： 开课时间 2019年4 月26日 实验报告 2019年5月 9日

学院名称 信息工程学院 年级、专业、班 软件1803班 学号 20181132 姓名 董健伟 同组姓名 无

课程名称 算法分析与设计 实验项目名称 实验二 快速排序及归并排序（分治策略） 指导教师 宋建材

实验类型 验证 □√ 综合 □ 设计□ 创新□ 成绩

教师评语：

教师签字:

一、 实验目的

通过快速排序和归并排序的算法实现来加深对分治策略的了解。

二、 实验描述

快速排序和归并排序都是使用分治策略的算法，他们将原有冒泡排序和插入排序的时间复杂度从O(n2)降低到O(nlgn)。是当下最为流行的排序算法。

三、 实验内容

编程完成随机生成100个数，用快速排序和归并排序进行排序，并完成实验报告（要求粘贴代码和实验结果截图）。

四、 实验代码

1、归并排序

#include

#include

#define MAX 100

using namespace std;

void merge(int array[], int p, int q, int r)

{

int i, k;

int begin1, end1, begin2, end2;

int* temp = new int[r - p + 1];

begin1 = p;

end1 = q;

快速排序实验报告

实验目的：

通过实现快速排序算法，掌握分治思想及其在排序算法中的应用；并比较快速排序和插入排序的性能。

实验内容：

1. 实现快速排序算法。

2. 设计实验，比较快速排序和插入排序的性能差异。

实验方法：

本实验使用C++语言编写程序，在Visual Studio 2019开发环境中进行。

快速排序算法的基本思想是通过让一个元素进行递归地归为有序的序列来对数据进行排序的。我们先选出一个基准值（通常是序列中的第一个元素）来作为枢轴，通过交换位置将小于基准值的元素移动到其左侧，将大于基准值的元素移动到其右侧，然后递归地排序左右两个子序列。

```cpp

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pivotPos = partition(arr, low, high);

quickSort(arr, low, pivotPos - 1);

quickSort(arr, pivotPos + 1, high);

}

}

为了比较快速排序和插入排序的性能差异，我们需要对两种算法进行时间复杂度分析，并在同一数据集上分别测试两种算法的运行时间。

快速排序的时间复杂度为O(nlogn)，其中n为数据集大小。而插入排序的时间复杂度为O(n²)。 为了进行性能测试，我们选择随机生成10万个整数作为测试数据。首先，我们使用快速排序进行排序并记录时间，然后使用插入排序进行排序并记录时间，最后比较两种算法的运行时间。

实验结果：

运行快速排序算法的运行时间为0.011秒，运行插入排序算法的运行时间为17.037秒。因此，我们可以看出，快速排序的性能要比插入排序要好得多，尤其是在处理大型数据集时。