- 实验目的：
- 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理
- 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。
- 问题重述（问题描述）：
问题一：
实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法
问题二：
生成20组数量规模为n（10万，20万，30万，40万，50万）的待排序随机数，然后用上述五种排序算法计算这20个样本的平均运行时间。并且要做出这五个排序算法在20个随机样本的平均运行时间，理论运行时间与输入规模n的关系曲线图（横纵坐标都要均匀）。比较两条曲线，理论和实际是否一致，不一致要分析给出原因。
问题三：
有10亿的数据（每个数据四个字节），请快速挑选出最大的十个数，并在小规模数据上验证算法的正确性。
- 实验原理（代码思想以及求解问题的算法原理描述）：
- 选择排序：
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素。（一般都是挑最小的数）
Fig1:选择排序原理图
2.冒泡排序：
相邻的两个元素进行比较,按照要求进行交换。
Fig2:冒泡排序原理图
3.合并排序：
先将数组中的元素拆分成若干小部分,然后再将这些小部分按照顺序进行重新组合,从而实现排序。（有点分治法的味道）
4.快速排序：
将比这个数大或等于的数全放到它的右边，小于它的数全放到它的左边(为由小到大排序)
5.插入排序：
将一个数插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
6.TOP 10:
按照正常思路肯定是便利数据10遍选择最大的十个数（即为选择排序）
可以选取上述五种排序算法中的最高效的来排序。
堆排序，维护10个数的小顶堆。
理论分析：
每个数据是4字节，那么10亿个数据就是40亿byte=3.725 G；所以在测试TOP 10时要预留足够的储存空间来存放待排的样本。
三、实验内容：
排序问题要求我们按照升序排列给定列表中的数据项，目前为止，已有多种排序算法提出。本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理，并进行代码实现。通过对大量样本的测试结果，统计不同排序算法的时间效率与输入规模的关系，通过经验分析方法，展示不同排序算法的时间复杂度，并与理论分析的基本运算次数做比较，验证理论分析结论的正确性。
流程图
- 实验过程及其优化分析（算法实现的核心伪代码以及算法测试结果及效率分析）：
设计随机数生成20组样本：
先是设置生成随机数样本，一开始使用的是rand（）这个函数；但发现每次产生的随机数虽然随机，但每个生成的随机数样本是一模一样的，缺乏说服力。然后我就是又去查了一下其他的生成随机数的方法mt19937随机数方法。
Fig：生成随机数的伪代码
通过小规模的数据生成发现：mt19937 随机数引擎生成的数比较随机，且数的范围比较大，数据比较杂乱，会使得我们后续的排序实验更加具有说服力。
接着为了更加方便我们跑数据我直接让程序一次性跑完20个样本并且把算出的数据给跳出来，解放劳动力。
Fig：一起运行20个样本的伪代码
- 选择排序（O（n2））：
1.1简单选择排序：
第一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素。
Fig3：选择排序伪代码
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 5657 | 23451 | 54387 | 98447 | 154215 |
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 5657 | 22784 | 51264 | 91136 | 142400 |
Fig4：选择排序实际与理论时间的曲线
分析：实际和理论运行时间曲线大致吻合，后面数据规模变大时出现了小偏差，可能测试的数据还不够多，导致平均实际运行时间纯在偶然性，有点小偏差。
可优化的方向：
- 因为一趟下来只排好了一个数，所以可以设计趟下来同时排好最大和最小的（一趟下来排好两个数）。
1.2优化的选择排序
Fig5：优化的选择排序伪代码
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 4238.75 | 17032 | 37788.67 | 66642.67 | 106555.7 |
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 4238.75 | 16955 | 38148.75 | 67820 | 105968.75 |
Fig6：优化的选择排序实际与理论时间的曲线
分析：理论和实际运行时间曲线大致吻合，拟合度高。
简单与优化对比：
效率有着明显的提升。优化后的选择排序虽然操作数增加了，但仍比简单的选择排序要高效。
2.冒泡排序：
2.1简单冒泡排序：
Fig7：冒泡排序伪代码
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 35367 | 137851 | 305605 | 545475 | 859000 |
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 35367 | 141468 | 318303 | 565872 | 884175 |
Fig8：冒泡排序实际与理论时间的曲线
分析：理论和实际运行时间曲线大致吻合，拟合度高。由于每趟排序进行了很多次交换，使得操作变得复杂，所以运行时间也比选择排序要大的多。
可以优化的方向：
- 可以设置一个变量flag，来判断该趟冒泡是否有发生交换，如果flag的状态发生改变，说明该趟冒泡有发生交换，如果没有交换，说明这一趟排序前一个位置的数都比后一个位置的数小或者等于，即已经排好序，可以提前结束排序
- 可以设置一个变量last，来记录最后一次交换的位置，然后下次遍历只用遍历到last即可，因为last后面的数已经排好序了。
2.2优化的冒泡排序：
Fig9：优化的冒泡排序伪代码
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 23887 | 96103 | 216001 | 383713 | 600446 |
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 23887 | 95548 | 214983 | 382192 | 597175 |
Fig10：优化的冒泡排序实际与理论时间的曲线
分析：理论和实际运行时间曲线大致吻合，拟合度高。
简单与优化对比：
效率有着极大的提升。
3.合并排序
Fig11：合并排序伪代码
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 24.33 | 51.85714 | 85 | 120.5 | 153.4286 |
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 24.33 | 51.5896 | 79.96 | 109.038 | 138.6556 |
Fig12：归并排序实际与理论时间的曲线
分析：对于快排来说，此数据规模偏小，所以造成了实际和理论的运行时间有着较大的偏差，但总体来说实际与理论大致吻合。
4.快速排序
Fig13：快速排序伪代码
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 7.5 | 18.45 | 28.85294 | 45 | 61.69231 |
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 7.5 | 15.903 | 24.647 | 33.61236 | 42.74228 |
Fig14：快速排序实际与理论时间的曲线
分析：对于快排来说，此数据规模偏小，而且递归函数的调用也耗了很多时间。所以造成了实际和理论的运行时间有着较大的偏差，但总体来说实际与理论大致吻合。
5.插入排序
Fig15：插入排序伪代码
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 7337.5 | 29683.5 | 67651.5 | 119289.5 | 186942.5 |
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 7337.5 | 29350 | 66037.5 | 117400 | 183437.5 |
Fig16：插入排序实际与理论时间的曲线
分析：实际与理论的运行时间曲线大致吻合,重合度高。
可以优化的方向：
- 在插入过程中因为插入的数是已经有序的，所以可以使用折半查找来找到要插入的位置。
理论：
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 4012 | 17868 | 43740 | 81779 | 127270 |
实际:
| 数据规模n | 100000 | 200000 | 300000 | 400000 | 500000 |
| 运行时间/ms | 4012 | 16046 | 36108 | 64192 | 100300 |
6.TOP 10
有三种可行的算法:
- 第一种就是选择排序，便利10次选出最大的十个数 O（n*10）
- 第二种就是通过上面对比课得知快速排序是最快的，可以先排序好再选10个最大的数O（nlog（n））
- 第三种就是堆排序，维护十个数的小顶堆。O（nlog(k)）
当选10个最大数时：
| 数据规模 | 选择排序 | 快速排序 | 堆排序 |
| 1千万 | 1689ms | 17126ms | 150ms |
| 2千万 | 3752ms | 33057ms | 340ms |
当选100个最大数时：
| 数据规模 | 选择排序 | 快速排序 | 堆排序 |
| 1千万 | 16597ms | 17157ms | 178ms |
| 2千万 | 34285ms | 33175ms | 469ms |
分析：当数据规模越多时选择和堆排序增长的速率近乎成比例翻倍，但当选出最大数的规模增大时，快排的变化不明显，选择和对排序仍是成比例翻倍。所以当选的数少时可以考虑使用选择和堆排序。选择最大数的数量大时可以考虑快排和堆排序，但总体而言，堆排序在TOP K这类问题中都明显优于选择排序和快速排序，这说明堆排序算法在这个问题中的正确性。
现在有10亿的数据（每个数据四个字节），请快速挑选出最大的十个数
使用堆排序可以在20000ms左右搞定。
Ps：每个数据是4字节，那么10亿个数据就是40亿byte=3.725 G；所以在测试TOP 10时要预留足够的储存空间来存放待排的样本（本次实验发现最少要给c盘留够12G的空间）。
五、讨论与总结（请阐述实验过程中所遇到的问题及解决办法，或者后续可以继续探索的问题等）
1.对算法的优化不能纸上谈兵。
在原有基础代码中其实有很多冗余的操作，比如排好序的任要继续遍历等，所以要多敲多实践，当然也不能只是想当然，比如选择排序空以为一趟下来排好两个位置会使运行时间减半，但其实也增加了一趟下来的操作，虽有优化，但也不至于是减半。
2.算法的运行时间在不同时刻会有所不同。
可能冒泡排序在今天我测的时候的运行时间会是我明天运行时间的不太一样，可能是对计算机的运行较多导致精度有点偏差，所以要测量某个算法最好是当天跑完所以数据。
3.不同的数量级要使用不同的算法来进行排序。
当数据规模一大的时候，快排和归并排序的优势就会凸显，所以当要排序的数据规模很大的时候，我们可以尽量选择快排与归并。
4.快速排序优于其他四个排序算法。
Fig17：五种算法对比
总的来说，快排是五种算法中最快的，但遇到极端情况数本来就有序就会降到O（n2）
但是由于随机生成随机数所以这种极端情况的出现概率为1n!
当数据规模比较大时可以基本忽略不看。冒泡排序虽然和选择排序以及插入排序的时间复杂度都为O（n2），但由于冒泡进行了更多的交换操作，所以平均运行时间也比选择排序以及插入排序要多
平均运行时间：冒泡排序＞插入排序序＞选择排序序＞归并排序序＞快速排序
5.当一些排序的运行时间比较久时可以想办法去优化。
比如去知网查文献
询问chatgpt等
标签：10,TOP,算法,时间,ms,排序,数据,运行 From： https://blog.csdn.net/m0_63790127/article/details/136396111