算法排序上机实验报告

上机实验报告篇1用户名se××××学号姓名学院①实验名称：②实验目的：③算法描述（可用文字描述，也可用流程图）：④源代码：（.c的文件）⑤用户屏幕（即程序运行时出现在机器上的画面）：2．对c文件的要求：程序应具有以下特点：a可读性：有注释。

b交互性：有输入提示。

c结构化程序设计风格：分层缩进、隔行书写。

3.上交时间：12月26日下午1点-6点，工程设计中心三楼教学组。

请注意：过时不候哟！四、实验报告内容0．顺序表的插入。

1.顺序表的删除。

2．带头结点的单链表的\'插入。

3.带头结点的单链表的删除。

注意：1.每个人只需在实验报告中完成上述4个项目中的一个，具体安排为：将自己的序号对4求余，得到的数即为应完成的项目的序号。

例如：序号为85的同学，85%4=1，即在实验报告中应完成顺序表的删除。

2.实验报告中的源代码应是通过编译链接即可运行的。

3.提交到个人空间中的内容应是上机实验中的全部内容。

上机实验报告篇2一、《软件技术基础》上机实验内容1．顺序表的建立、插入、删除。

2．带头结点的单链表的建立（用尾插法）、插入、删除。

二、提交到个人10m硬盘空间的内容及截止时间1．分别建立二个文件夹，取名为顺序表和单链表。

2．在这二个文件夹中，分别存放上述二个实验的相关文件。

每个文件夹中应有三个文件(.c文件、.obj文件和.exe文件)。

3. 截止时间：12月28日（18周周日）晚上关机时为止，届时服务器将关闭。

三、实验报告要求及上交时间（用a4纸打印）1．格式：《计算机软件技术基础》上机实验报告用户名se××××学号姓名学院①实验名称：②实验目的：③算法描述（可用文字描述，也可用流程图）：④源代码：（.c的文件）⑤用户屏幕（即程序运行时出现在机器上的画面）：2．对c文件的要求：程序应具有以下特点：a 可读性：有注释。

b 交互性：有输入提示。

算法实验报告算法实验报告引言：算法是计算机科学的核心内容之一，它是解决问题的方法和步骤的描述。

算法的设计和分析是计算机科学与工程中的重要研究方向之一。

本实验旨在通过对算法的实际应用和实验验证，深入理解算法的性能和效果。

实验一：排序算法的比较在本实验中，我们将比较三种常见的排序算法：冒泡排序、插入排序和快速排序。

我们将通过对不同规模的随机数组进行排序，并记录每种算法所需的时间和比较次数，以评估它们的性能。

实验结果显示，快速排序是最快的排序算法，其时间复杂度为O(nlogn)，比较次数也相对较少。

插入排序的时间复杂度为O(n^2)，比较次数较多，但对于小规模的数组排序效果较好。

而冒泡排序的时间复杂度也为O(n^2)，但比较次数更多，效率相对较低。

实验二：图的最短路径算法在图的最短路径问题中，我们将比较Dijkstra算法和Floyd-Warshall算法的效率和准确性。

我们将使用一个带权有向图，并计算从一个顶点到其他所有顶点的最短路径。

实验结果表明，Dijkstra算法适用于单源最短路径问题，其时间复杂度为O(V^2)，其中V为顶点数。

而Floyd-Warshall算法适用于多源最短路径问题，其时间复杂度为O(V^3)。

两种算法在准确性上没有明显差异，但在处理大规模图时，Floyd-Warshall算法的效率较低。

实验三：动态规划算法动态规划是一种通过将问题分解成子问题并记录子问题的解来解决复杂问题的方法。

在本实验中，我们将比较两种动态规划算法：0-1背包问题和最长公共子序列问题。

实验结果显示，0-1背包问题的动态规划算法可以有效地找到最优解，其时间复杂度为O(nW)，其中n为物品个数，W为背包容量。

最长公共子序列问题的动态规划算法可以找到两个序列的最长公共子序列，其时间复杂度为O(mn)，其中m和n分别为两个序列的长度。

结论：通过本次实验，我们对不同算法的性能和效果有了更深入的了解。

排序算法中，快速排序是最快且效率最高的；在图的最短路径问题中，Dijkstra算法和Floyd-Warshall算法分别适用于不同的场景；动态规划算法可以解决复杂的问题，并找到最优解。

实验名称：排序算法性能比较实验目的：1. 理解常见的排序算法及其原理。

2. 分析不同排序算法的时间复杂度和空间复杂度。

3. 通过实际编程实现排序算法，并进行性能比较。

实验环境：1. 操作系统：Windows 102. 编程语言：Python3.83. 开发环境：PyCharm实验内容：1. 实现冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序算法。

2. 对随机生成的数据集进行排序，比较不同算法的执行时间和稳定性。

3. 分析不同排序算法在不同数据规模下的性能差异。

实验步骤：1. 实现冒泡排序算法。

2. 实现选择排序算法。

3. 实现插入排序算法。

4. 实现快速排序算法。

5. 实现归并排序算法。

6. 实现堆排序算法。

7. 生成不同规模的数据集，对每个数据集使用上述算法进行排序。

8. 记录每个算法的执行时间，并进行比较。

9. 分析不同排序算法在不同数据规模下的性能差异。

实验结果与分析：一、冒泡排序冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

遍历数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

在数据规模较小的情况下，冒泡排序的性能较好。

二、选择排序选择排序是一种简单直观的排序算法。

它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

在选择排序中，元素的移动次数较少，因此在某些情况下，选择排序的性能可能优于冒泡排序。

三、插入排序插入排序是一种简单直观的排序算法。

它的工作原理是：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

实习题11. 用两种不同的顺序计算644834.11000012≈∑=-n n，试分析其误差的变化解：从n=1开始累加，n 逐步增大，直到n=10000；从n=10000开始累加，n 逐步减小，直至1。

算法1的C 语言程序如下： #include<stdio.h> #include<math.h> void main() { float n=0.0; int i; for(i=1;i<=10000;i++) { n=n+1.0/(i*i); } printf("%-100f",n); printf("\n"); float m=0.0; int j; for(j=10000;j>=1;j--) { m=m+1.0/(j*j); } printf("%-7f",m); printf("\n"); }运行后结果如下：结论： 4.设∑=-=Nj N j S 2211，已知其精确值为)11123(21+--N N 。

1）编制按从大到小的顺序计算N S 的程序； 2）编制按从小到大的顺序计算N S 的程序；3）按2种顺序分别计算30000100001000,,S S S ，并指出有效位数。

解：1）从大到小的C语言算法如下：#include<stdio.h>#include<math.h>#include<iostream>using namespace std;void main(){float n=0.0;int i;int N;cout<<"Please input N"<<endl;cin>>N;for(i=N;i>1;i--){n=n+1.0/(i*i-1);N=N-1;}printf("%-100f",n);printf("\n");}执行后结果为：N=2时，运行结果为：N=3时，运行结果为：N=100时，运行结果为：N=4000时，运行结果为：2）从小到大的C语言算法如下：#include<stdio.h>#include<math.h>#include<iostream>using namespace std;void main(){float n=0.0;int i;int N;cout<<"Please input N"<<endl;cin>>N;for(i=2;i<=N;i++){n=n+1.0/(i*i-1);}printf("%-100f",n);printf("\n");}执行后结果为：N=2时，运行结果为：N=3时，运行结果为：N=100时，运行结果为：N=4000时，运行结果为：结论：通过比较可知：N 的值较小时两种算法的运算结果相差不大，但随着N 的逐渐增大，两种算法的运行结果相差越来越大。

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

算法分析与设计实验报告：合并排序与快速排序一、引言算法是计算机科学中非常重要的一部分，它涉及到解决问题的方法和步骤。

合并排序和快速排序是两种经典而常用的排序算法。

本文将对这两种排序算法进行分析和设计实验，通过对比它们的性能和效率，以期得出最优算法。

二、合并排序合并排序是一种分治算法，它将原始数组不断分解为更小的数组，直到最后细分为单个元素。

然后，再将这些单个元素两两合并，形成一个有序数组。

合并排序的核心操作是合并两个有序的数组。

1. 算法步骤（1）将原始数组分解为更小的子数组，直到每个子数组只有一个元素；（2）两两合并相邻的子数组，同时进行排序，生成新的有序数组；（3）重复步骤（2），直到生成最终的有序数组。

2. 算法性能合并排序的最优时间复杂度为O(nlogn)，其中n为待排序数组的长度。

无论最好情况还是最坏情况，合并排序的复杂度都相同。

合并排序需要额外的存储空间来存储临时数组，所以空间复杂度为O(n)。

三、快速排序快速排序也是一种分治算法，它将原始数组根据一个主元（pivot）分成两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元。

然后，递归地对这两个子数组进行排序，最后得到有序数组。

快速排序的核心操作是划分。

1. 算法步骤（1）选择一个主元（pivot），可以是随机选择或者固定选择第一个元素；（2）将原始数组根据主元划分为两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元；（3）递归地对这两个子数组进行快速排序；（4）重复步骤（2）和（3），直到每个子数组只有一个元素，即得到最终的有序数组。

2. 算法性能快速排序的平均时间复杂度为O(nlogn)，其中n为待排序数组的长度。

最坏情况下，当每次选择的主元都是最小或最大元素时，时间复杂度为O(n^2)。

快速排序是原地排序，不需要额外的存储空间，所以空间复杂度为O(1)。

四、实验设计为了验证合并排序和快速排序的性能和效率，我们设计以下实验：1. 实验目的：比较合并排序和快速排序的时间复杂度和空间复杂度。

一、实验目的1. 掌握排序算法的基本原理和实现方法。

2. 熟悉常用排序算法的时间复杂度和空间复杂度。

3. 能够根据实际问题选择合适的排序算法。

4. 提高编程能力和问题解决能力。

二、实验内容1. 实现并比较以下排序算法：冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序。

2. 对不同数据规模和不同数据分布的序列进行排序，分析排序算法的性能。

3. 使用C++编程语言实现排序算法。

三、实验步骤1. 冒泡排序：将相邻元素进行比较，如果顺序错误则交换，直到序列有序。

2. 插入排序：将未排序的元素插入到已排序的序列中，直到序列有序。

3. 选择排序：每次从剩余未排序的元素中选取最小（或最大）的元素，放到已排序序列的末尾。

4. 快速排序：选择一个枢纽元素，将序列分为两部分，一部分比枢纽小，另一部分比枢纽大，递归地对两部分进行排序。

5. 归并排序：将序列分为两半，分别对两半进行排序，然后将两半合并为一个有序序列。

6. 堆排序：将序列构建成一个最大堆，然后依次取出堆顶元素，最后序列有序。

四、实验结果与分析1. 冒泡排序、插入排序和选择排序的时间复杂度均为O(n^2)，空间复杂度为O(1)。

这些算法适用于小规模数据或基本有序的数据。

2. 快速排序的时间复杂度平均为O(nlogn)，最坏情况下为O(n^2)，空间复杂度为O(logn)。

快速排序适用于大规模数据。

3. 归并排序的时间复杂度和空间复杂度均为O(nlogn)，适用于大规模数据。

4. 堆排序的时间复杂度和空间复杂度均为O(nlogn)，适用于大规模数据。

五、实验结论1. 根据不同数据规模和不同数据分布，选择合适的排序算法。

2. 冒泡排序、插入排序和选择排序适用于小规模数据或基本有序的数据。

3. 快速排序、归并排序和堆排序适用于大规模数据。

4. 通过实验，加深了对排序算法的理解，提高了编程能力和问题解决能力。

六、实验总结本次实验通过对排序算法的学习和实现，掌握了常用排序算法的基本原理和实现方法，分析了各种排序算法的性能，提高了编程能力和问题解决能力。

排序的实验报告排序的实验报告引言：排序是计算机科学中非常重要的一个概念，它涉及到对一组数据按照一定规则进行重新排列的操作。

在计算机算法中，排序算法的效率直接影响到程序的运行速度和资源利用率。

为了深入了解各种排序算法的原理和性能，我们进行了一系列的排序实验。

实验一：冒泡排序冒泡排序是最简单的排序算法之一。

它的原理是通过相邻元素的比较和交换来实现排序。

我们编写了一个冒泡排序的算法，并使用Python语言进行实现。

实验中，我们分别对10、100、1000个随机生成的整数进行排序，并记录了排序所需的时间。

实验结果显示，随着数据规模的增加，冒泡排序的时间复杂度呈现出明显的增长趋势。

当数据规模为10时，排序所需的时间约为0.001秒；而当数据规模增加到1000时，排序所需的时间则增加到了1.5秒左右。

这说明冒泡排序的效率较低，对大规模数据的排序并不适用。

实验二：快速排序快速排序是一种常用的排序算法，它的核心思想是通过分治的策略将数据分成较小的子集，然后递归地对子集进行排序。

我们同样使用Python语言实现了快速排序算法，并对相同规模的数据进行了排序实验。

实验结果显示，快速排序的时间复杂度相对较低。

当数据规模为10时，排序所需的时间约为0.0005秒；而当数据规模增加到1000时，排序所需的时间仅为0.02秒左右。

这说明快速排序适用于大规模数据的排序，其效率较高。

实验三：归并排序归并排序是一种稳定的排序算法，它的原理是将待排序的数据分成若干个子序列，然后将子序列两两合并，直到最终得到有序的结果。

我们同样使用Python 语言实现了归并排序算法，并进行了相同规模数据的排序实验。

实验结果显示，归并排序的时间复杂度相对较低。

当数据规模为10时，排序所需的时间约为0.0008秒；而当数据规模增加到1000时，排序所需的时间仅为0.03秒左右。

这说明归并排序同样适用于大规模数据的排序，其效率较高。

讨论与结论：通过以上实验，我们可以得出以下结论：1. 冒泡排序虽然简单易懂，但对于大规模数据的排序效率较低，不适用于实际应用。

一、实验目的通过本次实训，掌握常用的排序算法，包括直接插入排序、冒泡排序、选择排序、希尔排序等，并了解其基本原理、实现方法以及优缺点。

通过实际编程，加深对排序算法的理解，提高编程能力。

二、实验环境1. 开发工具：Visual Studio 20222. 编程语言：C++3. 操作系统：Windows 10三、实验内容本次实训主要涉及以下排序算法：1. 直接插入排序2. 冒泡排序3. 选择排序4. 希尔排序四、实验过程1. 直接插入排序（1）原理：将无序序列中的元素逐个插入到已有序序列的合适位置，直到整个序列有序。

（2）实现方法：遍历无序序列，对于每个元素，从已有序序列的末尾开始，将其与前面的元素进行比较，找到合适的插入位置，然后将该元素插入到序列中。

（3）代码实现：```cppvoid insertionSort(int arr[], int n) {int i, j, key;for (i = 1; i < n; i++) {key = arr[i];j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}```2. 冒泡排序（1）原理：通过相邻元素的比较和交换，将序列中的元素按从小到大（或从大到小）的顺序排列。

（2）实现方法：遍历序列，比较相邻元素，如果顺序错误，则交换它们的位置。

重复此过程，直到整个序列有序。

（3）代码实现：```cppvoid bubbleSort(int arr[], int n) {int i, j, temp;for (i = 0; i < n - 1; i++) {for (j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}```3. 选择排序（1）原理：每次从无序序列中选出最小（或最大）的元素，放到已有序序列的末尾。