实验一 排序算法比较

实验目的和要求

1. 探究在一定的软件和硬件条件下数据的储存限制
2. 探究不同的排序算法所需的时间与数据量的关系

实验环境

1. Ubuntu 16.04
2. CLion 2017.3
3. I5-7200U
4. 2G RAM

实验内容

1. 创建大小递增的数组，测试出数组的大小上限
2. 分别使用泡排序、选择排序对数据进行排序

实验过程

1. 依次创建大小为 10000、20000、30000 …的数组，直到程序崩溃
2. 根据上一步实验结果，分别生成 5000、10000、20000、30000、40000、50000、60000、70000、80000、90000、100000、200000、500000、1000000、1500000、2000000 个随机数字，使用冒泡排序、选择排序对这些数字进行排序

测试及结果分析

实验数据

使用 C++ 提供的随机数函数生成的数据

结果及分析

任务一

结果：创建数组的运行截图如下

分析：发现当数组大小达到 2090000 后，继续创建更大的数组时程序出现错误，可知当前条件下数组只能达到 2090000 ~ 2100000。

根据资料可知，C++ 中的数组创建在栈内存中，程序所能使用的最大栈内存在不同的环境下的默认值不同，当前环境的默认栈内存为 8192KB。

已知 C++ 中的 int 类型占用 4Byte，计算可得 8192KB 内存可容纳 2097152 个 int 类型数据，与实验所得的 2090000 ~ 2100000 相近，考虑到程序代码及其他变量占用的内存和本实验中数组大小变化的步长，可认为实验结果正确。

若在堆上创建动态数组，可得到如下结果：

当数组大小达到 438390000 时，程序出错，经计算 438390000 个 int 类型数据大约占 1.6GB，与当前环境下的可用物理内存总数相等。可知，在堆上创建数组时，受到物理内存大小的制约。

任务二

结果：

分析可知冒泡排序和选择排序的均为 O(n2)，对实验所得的数据进行分析可得如下拟合图像，二者所需时间均为数据量的二次函数，故可验证理论分析的正确性。

实验收获

数据在计算机中的储存是有限制的，直接创建的数组储存在栈中，其大小受到系统的限制。为了储存更多的数据，可在堆上创建动态数组，但是其速度也会降低。从这个结果看，在研究数据结构时，不仅仅要关注数据之间的逻辑结构，还要考虑到数据的储存结构，考虑到计算机的一些限制，这样才能设计出更加合理的程序。

不同的排序算法都可以在理论上分析其复杂度，从而筛选出更优秀的排序算法，达到在一定量的数据时，使用更少的时间对其进行排序。