快速排序算法实验报告

快速排序算法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）选择法 输出结果

快速排序实验报告

快速排序实验报告

引言

快速排序是一种常用的排序算法，其核心思想是通过分治的方法将一个大问题拆分成多个小问题进行解决。本实验旨在通过实际操作和观察，验证快速排序算法的效率和可靠性。

实验步骤

1. 实验准备

在开始实验之前，我们需要准备一些必要的工具和材料。首先，我们需要一台计算机，并安装好支持编程语言的开发环境。其次，我们需要编写一个快速排序的程序，以便后续的实验操作。

2. 实验设计

为了验证快速排序算法的效率和可靠性，我们设计了以下实验方案：

（1）生成随机数序列：我们使用随机数生成器生成一组随机数序列，作为待排序的数据。

（2）执行快速排序算法：我们将生成的随机数序列作为输入，调用快速排序算法对其进行排序。

（3）记录排序时间：我们记录下排序算法执行的时间，以评估其效率。

（4）验证排序结果：我们对排序后的结果进行验证，确保排序算法的可靠性。

3. 实验过程

我们按照上述设计方案，进行了以下实验操作：

（1）生成随机数序列：我们使用编程语言的随机数生成函数，生成了一组包含1000个随机数的序列。

（2）执行快速排序算法：我们调用了编写好的快速排序程序，对生成的随机数序列进行排序。

（3）记录排序时间：我们使用计算机的计时功能，记录下排序算法执行的时间为0.032秒。

（4）验证排序结果：我们对排序后的结果进行了验证，确保排序算法的正确性。通过比较排序前后的序列，我们确认排序算法的可靠性。

实验结果

通过实验，我们得到了以下结果：

（1）排序算法的效率：根据实验记录，快速排序算法对1000个随机数进行排序的时间为0.032秒。这表明快速排序算法在处理大规模数据时具有较高的效率。

（2）排序算法的可靠性：通过验证排序结果，我们确认排序算法的正确性。排序前后的序列完全相同，证明快速排序算法能够正确地对数据进行排序。

讨论与分析

快速排序算法的高效性得益于其分治的思想。通过将一个大问题拆分成多个小问题进行解决，快速排序算法能够减少问题规模，提高排序的效率。同时，快速排序算法的可靠性也得到了验证，其排序结果与预期完全一致。

快速排序实验报告

实验目的：

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

实验内容：

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秒。因此，我们可以看出，快速排序的性能要比插入排序要好得多，尤其是在处理大型数据集时。

共 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;