快速排序算法实验报告

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

一、实验背景

随着计算机科学技术的不断发展，算法作为计算机科学的核心内容之一，其重要性日益凸显。为了验证和评估不同算法的性能，我们进行了一系列算法实验，通过对比分析实验结果，以期为后续算法研究和优化提供参考。

二、实验方法

本次实验选取了三种常见的算法：快速排序、归并排序和插入排序，分别对随机生成的数据集进行排序操作。实验数据集的大小分为10000、20000、30000、40000和50000五个级别，以验证算法在不同数据量下的性能表现。

实验过程中，我们使用Python编程语言实现三种算法，并记录每种算法的运行时间。同时，为了确保实验结果的准确性，我们对每种算法进行了多次运行，并取平均值作为最终结果。

三、实验结果

1. 快速排序

快速排序是一种高效的排序算法，其平均时间复杂度为O(nlogn)。从实验结果来看，快速排序在所有数据量级别下均表现出较好的性能。在数据量较小的10000和20000级别，快速排序的运行时间分别为0.05秒和0.1秒；而在数据量较大的40000和50000级别，运行时间分别为0.8秒和1.2秒。总体来看，快速排序在各个数据量级别下的运行时间均保持在较低水平。

2. 归并排序

归并排序是一种稳定的排序算法，其时间复杂度也为O(nlogn)。实验结果显示，归并排序在数据量较小的10000和20000级别下的运行时间分别为0.15秒和0.25秒，而在数据量较大的40000和50000级别，运行时间分别为1.5秒和2.5秒。与快速排序相比，归并排序在数据量较小的情况下性能稍逊一筹，但在数据量较大时，其运行时间仍然保持在较低水平。

3. 插入排序

插入排序是一种简单易实现的排序算法，但其时间复杂度为O(n^2)。实验结果显示，插入排序在数据量较小的10000和20000级别下的运行时间分别为0.3秒和0.6秒，而在数据量较大的40000和50000级别，运行时间分别为8秒和15秒。可以看出，随着数据量的增加，插入排序的性能明显下降。 四、结果分析

快速排序实验报告

快速排序实验报告

引言

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

实验步骤

1. 实验准备

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

2. 实验设计

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

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

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

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

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

3. 实验过程

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

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

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

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

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

实验结果

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

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

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

讨论与分析

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

《程序设计实践》报告

学号 江元 ；

姓名 090241111 ；

题目序号 2011年题目：排序7.1B类的第5题 ；

难度等级 B

一、题目

写出快速排序的非递归算法

二、问题分析及求解基本思路

问题分析：

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要

排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有

数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程

可以递归进行，以此达到整个数据变成有序序列。而在程序设计中虽然应用递归技术, 能够使得程序简洁易懂, 但是效率并不是最高的,因此可以利用栈结构实现非递

归的快速排序。

求解基本思路： 将每次分治的两个序列的高位和低位入栈，每次都从栈中获取一对高位和低位，

分别处理。处理过程是：选取高位作为基准位置，从低位开始向高位遍历，如果比基

准元素小，那么和第i个交换，如果有交换，那么i++，等一遍遍历完成后，如果i

的位置不等于基准位置，那么所选的基准位置的值不是最大的而这时候i的位置之前

的元素都比基准值小，那么i的位置应该是基准值，将i所在位置的值和基准位置进行交换。这时候，在i的左右就将序列分成两部分了，一部分比i所在位置值小，一

部分比i所在位置值大的，然后再次将前面一部分和后面一部分的高位和低位分别入

栈，再次选择基准位置，直到所选择的区间大小小于2，就可以不用入栈了。

三、问题求解的整体框架结构

四、主要算法

1．非递归快速排序算法qsrt( a, l , r )：

由partition(pData, low, high)返回了轴值，st.push(low); st.push(pivot - 1);

st.push(pivot + 1); st.push(high); 循环执行下列语句直到栈为空

（1）high = st.top(); st.pop(); low = st.top(); st.pop();