深圳大学算法实验一——排序算法性能分析

深圳大学算法实验一

一、实验目的与要求

1. 掌握九种排序算法原理

2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。

3. 对多种排序算法提出改进方案

4. 综合比较各种排序算法

5. 解决大规模数据排序问题

6. 排序实验经验总结

二、实验内容与方法

1.理解算法原理，编写程序实现多种排序算法

(1)冒泡排序

        冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

        在数据完全有序的时候冒泡排序展现出最优时间复杂度，为。正常情况下，几乎总是。

        伪代码如下：

(2)选择排序

        首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

        选择排序的时间复杂度为，是一种原地排序算法，空间复杂度为O(1)。

        伪代码如下：

(3)插入排序

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

        插入排序的时间复杂度为，是一种原地排序算法，空间复杂度为O(1)。

        伪代码如下：

(4)希尔排序

        希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

        希尔排序是基于插入排序性质提出改进方法的：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位，很难快速使序列基本有序。

        希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

        希尔排序是原地排序，空间复杂度为O(1)。希尔排序的时间复杂度众说纷纭，难以确定。大致认为希尔排序的时间复杂度为，其中k为1.3~2之间的数。本实验认为希尔排序时间复杂度为。

        伪代码如下：

(5)归并排序

        归并排序是一种分治思想在排序算法中的典型应用。它的实现步骤大致如下：

        步骤1，申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

        步骤2，设定两个指针，最初位置分别为两个已经排序序列的起始位置；

        步骤3，比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

        重复步骤 3 直到某一指针达到序列尾，然后将另一序列剩下的所有元素直接复制到合并序列尾。它的程序实现有两种方法，分别为自上而下的递归，和自下而上的迭代。

        伪代码如下：

(6)快速排序

        快速排序，顾名思义，最大的特点就是速度快。这种算法的平均时间复杂度为。在原始数据完全有序的最坏状况下，快速排序退化为简单排序，时间复杂度暴增至，但这种状况并不常见，所以说快速排序在绝大多数情况下都有着极为优秀的效率。事实上，快速排序通常明显比其他相同时间复杂度的排序算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来，复杂度中隐含的常数因子很小。  

        算法实现步骤如下：

        步骤一，从数列中挑出一个元素，称为 "基准"；

        步骤二，重新排序数列，把比基准值小的元素放在基准元素之前，把比基准值大的元素放在基准元素之后。为分区（partition）操作；

        步骤三，递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

        伪代码如下：

(7)基数排序

        基数排序通过分配-收集的操作对多关键字的数据进行排序。一种常见的情况是将待比较的整数按照位数进行切分，分配到不同的序列中，然后再重新收集。这是一种非比较性的排序算法，因此它可以突破比较排序算法时间复杂度的限制，时间复杂度进一步提升到的线性级别。需要注意的是，基数排序的分配-收集操作需要占用大量空间，因此数据规模很大时使用基数排序会导致内存爆栈退出。 

        伪代码如下：

 (8)堆排序

        堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一个二叉树结构，并满足子结点的键值总是小于(或者大于)父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。构建堆分为两种方法：

        大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

        小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

        堆排序的平均时间复杂度为。这是一种原地排序，空间复杂度为O(1)。并且，堆排序不是稳定排序。

        堆排序首先创建一个堆，把它调整为大顶堆(或小顶堆)。然后把堆顶数据与无序序列尾的数据交换，排好一个元素。然后调整堆使其重新成为大顶堆(或小顶堆)。不断重复这一步骤，完成排序。

        伪代码如下：

(9)计数排序

        计数排序的步骤如下：

        步骤一，找出待排序的数组中最大和最小的元素；

        步骤二，统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

        步骤三，对所有的计数累加；

        步骤四，根据计数数组反向填充目标数组。

        由于用来计数的数组C的长度取决于待排序数组中数据的范围，这使得使用计数排序来排序范围很大的数据，需要消耗大量空间。

        计数排序不是比较排序，排序的速度快于任何比较排序算法。它的时间复杂度为线性的O(n+k)，空间复杂度为O(k)，其中k为待排序元素大小的极差。

        伪代码如下：

2. 以待排序数组的大小n为输入规模，固定n，随机产生20组测试样本，统计不同排序算法在20个样本上的平均运行时间。

3. 分别以n=10, n=100, n=1000, n=10000, n=100000，n=1000000，重复2的实验。

4. 得出不同排序算法在20个随机样本的平均运行时间与输入规模n的关系。绘制表格和log折线图，将实际值和理论值进行比较，并提出理论时间与实测时间不一致的解释。

5.提出改进算法，对以上的一些排序算法提出优化方案

6.比较各种排序算法，分析算法各种情况下的时间复杂度、空间复杂度和稳定性等数据，绘制表格和折线图对比多种排序算法的综合性能。

7. 问题描述：现在有1万亿的数据，请选择合适的排序算法与数据结构，在有限的时间内完成进行排序。综合多方资料，提出解决大规模数据排序问题的方法。这里介绍一种采用多路归并的思想解决大规模数据排序问题的方法，步骤如下：

        一，将大数据文件切分为小数据文件；

        二，对小数据文件进行内部排序；

        三，对排序好的小文件进行多路归并排序，重新写回硬盘。

        对小数据文件进行排序可以选择快速排序、堆排序、基数排序、计数排序等排序方法进行排序。接下来思考外部排序实现方法。

        若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为s(n-1)(k-1)。参考公开资料，此时可以使用败者树实现归并排序。

        败者树是树形选择排序的一种变形， 主要会用于外部多路归并排序。在大部分情况下我们接触到的都是胜者树, 即每个非终端节点均表示其左、右孩子节点中的胜者。反之， 如果在双亲节点中记下刚进行完的这场比赛中的败者，而让胜者去参加更高一层的比赛，便可得到一棵败者树。

        由于实现k-路归并的败者树的深度为⌈log2^n⌉ + 1，则在k个记录中选择最小关键字仅需进行⌈log2^n⌉次比较。败者树的初始化也容易实现，只要先令所有的非终端节点指向一个含最小关键字的叶子节点，然后从各个叶子节点出发调整非终端节点为新的败者即可。

8.就算法解决问题的角度对本实验进行经验总结。

三、实验步骤与过程

1.实现算法并测试运行数据

        通过C++语言实现多种排序方式以及改进，分别对这些排序算法进行测试。记录数据与绘制对数图表如下。本实验选取的理论值基准均为数据规模为1000000时的测试数据。

(1)冒泡排序

         冒泡排序、选择排序和插入排序这三种时间复杂度为的算法，理论曲线计算方法为：取基准时间(数据规模为1000000时算法用时)，数据规模为n时，理论时间相对基准时间变化倍。即数据规模每扩大(缩小)10倍，理论用时相对变化100倍。

        可以看到在数据规模较小时，冒泡排序的实测值和理论值相差较大。理由可能是，在数据规模较小时，冒泡排序进行大量比较和交换消耗大量时间。以及算法运行过快，clock()函数难以准确测量时间。即使按照附录所提示的重复一百次计时的方法，计时误差和硬件耗时依旧无法忽略。

        接下来对冒泡排序提出改进策略。我们可以尝试设置一个工具变量，来计算每一趟冒泡排序有没有交换数据，如果一趟冒泡排序没有交换数据，则数据已经有序。然而我们会发现，在数据规模较大时，很难出现能够提前多轮完成全部排序的情况，因此这种判断并不能让算法显著变快，反而因为频繁的判断使算法时间消耗更大了。

        可能这样的改进不够。我们可以再添加一个变量，记录每次冒泡最后一次交换的位置。下次冒泡的终点到达最后一次交换的位置即可停止。

        但实际测试发现这种改进方式仍然不理想。因为数据规模较大时，很难提前几轮排好序让一整趟排序都不需要交换，也很难在一趟排序排到底之前提早很多结束。与此同时，多次判断标志变量和检测最后一次交换发生的位置，同样需要消耗大量时间。这使得这种改进方式的效果不说出类拔萃，也可以说惨不忍睹。改进之后的算法甚至比简单的冒泡排序算法更慢了。

        因此提出另一种改进算法——鸡尾酒排序。

        鸡尾酒排序，即双向冒泡排序，鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。所以鸡尾酒排序能更好地应对一些数据不那么均匀的情况。

        以下展示冒泡排序、冒泡排序改进1(添加标志位判断本趟排序是否发生交换)、冒泡排序改进2(添加记录变量记录本趟排序最后一次发生交换的位置)、双向冒泡(鸡尾酒排序)的算法耗时。

        对数图如下：

         可以发现，双向冒泡排序是有效优化，它的运行时间普遍短于冒泡排序。然而，双向冒泡排序的时间复杂度仍为，与其他排序算法相比不占优势。 

(2)选择排序

         可以看到在数据规模较小时，选择排序的实测值和理论值相差较大。理由大致与冒泡排序的情况相似，在数据规模较小时，选择排序执行大量比较操作消耗时间。同时，数据规模太小，算法运行过快，clock()函数难以准确测量时间，计时误差和硬件耗时依旧无法忽略。

        接下来对选择排序提出改进策略。

        如果算法每次把全部数据都搜索一遍，只排好一个数据就太浪费了。因此可以每次搜索同时查找数据中的最大最小项，分别把它们放在待排序数组的两端。这样可以提升一定的效率，但是时间复杂度仍然是级别的。 

         可见，这种改进策略有效地提升了算法运行效率。

(3)插入排序

         由于插入排序同样需要进行大量比较操作，因此数据规模较小时实测曲线与理论曲线仍有较大差异。可以注意到几种简单排序在数据规模较大时，实测值和理论值拟合得很好。

        接下来对插入排序提出改进策略——折半插入。

        插入排序的一个步骤，就是要查找已经排好序的元素的大小，然后将待排序数据插入合适的位置。根据学过的查找算法，我们发现使用折半查找比顺序查找更快。因此我们提出插入排序的改进算法，利用折半查找确定待排序数据在有序部分的位置。

        因此，可以认为折半插入算法是一种有效的改进方法。然而，无论如何改进简单排序算法，它们的时间复杂度始终是，在面对大规模的数据时依旧十分无力。优化过的简单排序算法，排序一百万个整数，仍然需要十几分钟，面临更大规模的数据时显然不堪用。因此，我们需要其他更好的排序算法。 

(4)希尔排序

        希尔排序的时间复杂度突破了。下面是希尔排序运行数据实测表及对数折线图。 

        希尔排序理论时间计算方法：取基准时间(数据规模为1000000时算法用时)，数据规模为n时，理论时间相对基准时间变化倍。即数据规模每扩大(缩小)10倍，理论用时相对变化19.952倍。

        我们注意到数据规模较小时希尔排序耗时和理论曲线不符合。原因大致有大量交换耗时，切分数组耗时以及计时误差。

        接下来对希尔排序提出改进策略——移位法。

        数据交换消耗时间较大。为了进一步优化算法我们想到可以减少交换数据的次数。我们可以在每趟希尔排序时，单纯地逐个移动数据元素的位置，然后把待排序数据放置到它应该在的空位中。

        我们注意到某些算法运行速度过快，以至于无法准确计量算法用时。同时，鉴于从希尔排序开始，时间复杂度低于级别，足以在较短时间内完成比一百万更大规模数据的排序。因此，从希尔排序开始，我们将会测试一千万的数据规模作为补充，期待能够更好地测试这些算法在更大规模数据下的表现。 

        可以看到，希尔排序移位法可以有效地节省耗时。这是一项合理的优化方法。

(5)归并排序

        以下是使用递归实现的归并排序的数据表和对数折线图。

        归并排序、堆排序、快速排序理论时间计算方法：取基准时间(数据规模为1000000时算法用时)，数据规模为n时，理论时间相对基准时间变化倍。

        可见，分治归并实测值和理论值符合得较好。

        接下来对分治归并提出改进策略——放弃递归。

        非递归每次操作步长倍增，是对递归树的自底向上的层次遍历，而非对递归树的自顶向下的先序遍历。递归和非递归的实现方法排序结果是一样的。但是相比于递归，非递归的二路归并排序时间和空间的开销大大减少。

        可见，在大规模数据排序的问题中，非递归的实现方式快于递归实现方式。因为节省了递归操作带来的额外时间空间消耗。在数据规模较小时，两种实现方式耗时相近。递归实现由于代码简单而取得优势。

(6)堆排序

        堆排序性能数据如下：

        堆排序的实测曲线和理论曲线在数据规模较小时相差较大。理由可能有硬件耗时、计时误差以及数据规模小时建堆消耗的时间空间无法忽略。

(7)快速排序

        另外，快速排序在原始序列有序的最坏情况下，时间复杂度退化到级别。 

        由简单的测试即可证明，在最坏条件下快速排序的表现令人一言难尽，甚至在耗时上不如冒泡排序等简单排序。在处理数据规模稍大的数据时直接爆栈溢出。简单排序不需要占用额外空间，而最坏情况下的快速排序大量递归占用非常多时间空间。

(8)基数排序

        基数排序和计数排序都是时间复杂度为线性的排序算法。理论曲线计算方法为数据规模变化十倍，理论耗时变化十倍。

        数据规模较小时实际开销超过理论预期的原因：分配-收集操作需要占用大量时间空间，因此数据规模小的时候耗时无法忽略。

(9)计数排序

        可以看见计数排序实测曲线和理论曲线拟合得很好。

        下面提出计数排序改进方法。

        我们注意到简单计数排序计数容器占用空间很大，这会占用大量的内存空间。并且算法也会浪费大量的时间来搜索并没有记录的容器位置。因此我们可以进行优化，在排序前先计算出待排序数据大小的极差，针对性地开辟计数容器空间，起到节省空间的作用。

        改进计数排序算法时间上的优化肉眼可见。通过计算待排序元素极差来针对性开辟计数空间，可以高效节省时间和空间的消耗。

2. 排序算法对比分析

        比较各种排序算法，分析算法各种情况下的时间复杂度、空间复杂度和稳定性等数据，绘制表格和折线图对比多种排序算法的综合性能。

         根据图像，我将排序算法分为三类。

        第一类，简单排序。即冒泡、选择和插入排序。这几种排序方法的优点在于简单直观，代码好写，并且在数据规模较小时运算速度有些微优势。缺点在于，当数据规模增大时，简单排序的耗时会很快增加到令人难以忍受的程度。因此，这三种排序算法适用于数据规模小的情况。推荐插入排序和选择排序。

        第二类，希尔排序、归并排序和堆排序。这三种排序的时间复杂度优于.可以应对较多情况。 

        第三类，快速排序、基数排序和计数排序。基数排序和计数排序时间复杂度到达线性级别。而快速排序复杂度中隐含的常数因子很小，是复杂度级别中最快的一种排序方法。这三种排序方法速度极快，然而空间占用较高(归并排序也有空间占用的问题)，并且对待排序数据有要求(快排数据不能是顺序的，基数排序需要数据有基数，基数排序需要数据可以计数)。在数据规模特别大时，需要考虑空间复杂度的问题。

3.大规模数据排序方法

        具体方法已经在(二、)中给出。

        可采用多路归并的思想解决大规模数据排序问题，步骤如下：

        一，将大数据文件切分为小数据文件；

        二，对小数据文件进行内部排序；

        三，对排序好的小文件进行多路归并排序，重新写回硬盘。

        对小数据文件进行排序可以选择快速排序、堆排序、基数排序、计数排序等排序方法进行排序。接下来思考外部排序实现方法。

        若归并趟数为s次，那么对n个记录的文件进行外排时，内部归并过程中进行的总的比较次数为s(n-1)(k-1)。参考公开资料，此时可以使用败者树实现归并排序。

四、实验结论或体会

实验结论：

        对问题一，在处理小规模数据排序问题时，插入排序和选择排序是较好的选择，冒泡排序也是可选的算法。在数据规模较大时，应该选择希尔排序、堆排序、归并排序、快速排序、基数排序或基数排序。并且，数据规模大时，若采用归并排序、快速排序、基数排序或计数排序，需要考虑空间复杂度的问题。

        对问题二，求解大规模数据排序问题，主要采用多路归并的思想。归并的具体算法可以用败者树实现。

实验体会：

        很多算法的时间复杂度表达式看起来都是一样的，但实际运行起来会差别很大。尤其是冒泡排序和选择排序插入排序相比，同样的复杂度下，选择排序和插入排序就要比冒泡排序快数倍。并且同样的时间复杂度表达式下，快速排序就比归并排序和堆排序要更快。这是算法内隐含的常数因子的不同导致的。 

        我们需要应对不同情况使用不同的排序算法。待排序数据的规模，极差，类型和基础有序度，都是我们选择排序算法时需要考虑的东西。

五、思考

        完成这个实验我耗费了不少时间，参考了不少网络资料，也遇到了很多错误和问题。比如说，数据规模小时，对运行速度很快的算法没法进行计时。无论是网络资料还是老师提供的方法都难以将计时精确到毫秒以下。这也是本实验中很多实验数据最低到“0.000……”的原因。此外，我把基数排序时间复杂度搞错了，一开始以为它是的复杂度，后来想起来是O(n)级别的复杂度。用错误的复杂度表达式计算出了错误的理论曲线，导致ppt展示时的图表和对数折线图是错误的。这个问题在后来得以解决，实验提交到BB的word版实验报告和PPT上的数据是正确的。 

        总的来说，通过完成这个实验，我代码编写的能力提升了，对排序算法的掌握也增加了。花时间编写代码，完成实验，制作PPT和word版实验报告，并且用PPT向同学展示自己的实验成果，都是需要付出努力并且能够有所收获的。希望我能通过算法设计与分析这门课，收获更多知识，培养自己求解问题的能力。

        此外，在运行代码时尽量确保电脑状态一致！应让你的机器在运行算法时保持充电状态，或至少控制电池处在相同模式。同时尽量关闭其他软件并且控制打开的软件差不多相同。不同的电量、电池模式和其他软件对电脑资tm源的占用可能导致算法运行时间不同。

六、全部代码

#include <bits/stdc++.h>
#define SIZE 10000002 //2147483646
using namespace std;
void display(vector <int> a,int n) {
	int i;
	for(i=0; i<n-1; i++)
		cout<<a[i]<<" ";
	cout<<a[i]<<endl;
}
void BubbleSort(vector <int> a,int n) { //冒泡排序
	for(int i=0; i<n-1; i++)
		for(int j=0; j<n-i-1; j++)
			if(a[j]>a[j+1])
				swap(a[j],a[j+1]);
}
void up1BubbleSort(vector <int> a,int n) { //设置标志，如果已经全部排好就停止，不做无用功
	int flag,i,j;
	for(i=0; i<n-1; i++) {
		flag=0;
		for(j=0; j<n-i-1; j++)
			if(a[j]>a[j+1]) {
				swap(a[j],a[j+1]);
				flag=1;
			}
		if(flag==0)
			return;
	}
}
void up2BubbleSort(vector <int> a,int n) { //设置标志位，第i趟交换最后一个位置的下标，只需要循环到这个下标的位置即可 含有插入/选择排序的思想
	int flag,temp,len=n-1;
	for(int i=0; i<n-1; i++) {
		flag=0;
		for(int j=0; j<len; j++)
			if(a[j]>a[j+1]) {
				swap(a[j],a[j+1]);
				flag=1;
				temp=j;
			}
		len=temp;
		if(flag==0)
			return;
	}
}
void up3BubbleSort(vector <int> a,int n) { //双向冒泡
	int low, high, flag, i;
	low = 0;
	high = n - 1;
	while(low < high) {
		flag=0;
		for(i=low; i<high; i++) { //正向冒泡
			if(a[i] > a[i+1]) { //找到剩下中最大的
				swap(a[i], a[i+1]);
				flag = 1;    //标志， 有数据交换
			}
		}
		if(!flag)
			break;
		high--;
		for(i=high; i>low; i-- ) { //反向冒泡
			if(a[i] < a[i-1])   //找到剩下中最小的
				swap(a[i],a[i-1]);
		}
		low++;
	}
}
void ChooseSort(vector <int> a,int n) { //选择排序
	int i,j,k,min;
	for(i=1; i<n; i++) {
		min=a[i];
		k=i;
		for(j=i+1; j<=n; j++) //找出待排序元素最小值下标
			if(min>a[j]) {
				min=a[j];
				k=j;
			}
		swap(a[i],a[k]);
	}
}
void upChooseSort(vector <int> a,int n) { //选择排序 同时选出最大最小
	int i=0,j,k,min_pos,max_pos;
	int arr[100002];
	for(i=0; i<n; i++)
		arr[i]=a[i];
	i=0;
	while(i<=n/2) {
		min_pos=i;
		max_pos=n-1-i;
		for(j=i; j<=n-1-i; j++) {
			if(arr[j]<arr[min_pos])
				min_pos=j;
			if(arr[j]>arr[max_pos])
				max_pos=j;
		}
		swap(arr[max_pos],arr[n-1-i]);//最大放在最右
		if(min_pos==n-1-i)
			min_pos=max_pos;
		swap(arr[min_pos],arr[i]);//最小放在最左
		i++;
	}
	return;
}
void InsertSort(vector <int> a,int n) { //插入排序
	for(int i=1; i<n; i++) {
		int temp=a[i];
		int j=i-1;
		while(j>=0&&temp<a[j]) {
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp;
	}
}
void upInsertSort(vector <int> a,int n) { //折半插入排序
	int temp;
	for(int i=1; i<n; i++) {
		temp=a[i];
		int left=0;
		int right=i-1;
		while(right>=left) {
			int mid=(left+right)/2;
			if(a[mid]>temp)
				right=mid-1;
			else
				left=mid+1;
		}
		for(int j=i-1; j>right; j--)
			a[j+1]=a[j];
		a[right+1]=temp;
	}
}
void ShellSort(vector <int> &a,int n) { //希尔排序
	int gap=n/2;
	while(gap>=1) {
		for(int i=gap; i<n; i++)
			for(int j=i; j>=gap&&a[j]>a[j-gap]; j-=gap) //降序希尔排序
				swap(a[j],a[j-gap]);
		gap/=2;
	}
}
void upShellSort(vector <int> &a,int n) { //希尔排序移位法
	for(int gap=n/2; gap>0; gap/=2) {
		for(int i=gap; i<=n; ++i) {
			int j=i;
			int temp=a[i];
			if(a[j]<a[j-gap]) {
				while(j-gap>=0 &&temp<a[j-gap] ) {//此类判断大于0的必须放在前面，否则会导致数组下标为负数崩溃！
					a[j]=a[j-gap];
					j-=gap;
				}
				a[j]=temp;
			}
		}
	}
}
void recQuickSort(vector<int> &a, int l, int r) { //递归快速排序
	if(l<0 || r>=a.size() || l>=r) return;
	int key=a[l], i=l, j=r;
	while(i<j) {
		while(i<j &&a[j]>=key) j--;
		swap(a[i], a[j]);
		while(i<j &&a[i]<=key) i++;
		swap(a[i], a[j]);
	}
	a[i]=key;
	recQuickSort(a, l, i-1);
	recQuickSort(a, i+1, r);
}
int Partition(vector <int> a,int low,int high) { //快速排序分块，确定某元素位置
	int pivotkey=a[low];
	while(low<high) {
		while(low<high&&a[high]>=pivotkey)
			high--;
		a[low]=a[high];
		while(low<high&&a[low]<=pivotkey)
			low++;
		a[high]=a[low];
	}
	a[low]=pivotkey;
 
	return low;
}
void QuickSort(vector <int> a,int low,int high,int n) { //升序快速排序
	int pivotloc=low,pivotkey;
	if(low<high) {
		pivotloc=Partition(a,low,high);
		if(low!=pivotloc-1)
			QuickSort(a,low,pivotloc-1,n);
		else if(high!=pivotloc+1)
			QuickSort(a,pivotloc+1,high,n);
		else
			cout<<a[pivotloc+1]<<" "<<pivotloc+2<<endl;
	}
}
void minheap(vector <int> &a, int c_start, int end) {//调整为小顶堆
	int dad = c_start;
	int son = dad * 2 + 1;//分别指向父节点和字结点
	while (son <= end) { //判断是否存在子节点
		if (son + 1 <= end && a[son] > a[son + 1]) //将最小的子节点调整到父节点
			son++;
		if (a[dad] < a[son]) // 结点有序无序调整
			return;
		else { //完成筛选，将小元素上移
			swap(a[dad], a[son]);
			dad = son;
			son = dad * 2 + 1;//完成本结点筛选，更新指针下标
		}
	}
}
void HeapSort(vector <int> a, int n) {//降序堆排序
	for (int i = n / 2 - 1; i >= 0; i--)
		minheap(a, i, n - 1);
	for (int i = n - 1; i > 0; i--) {//把第一个元素和最后一个元素交换，然后重新调整为小顶堆
		swap(a[0], a[i]);
		minheap(a, 0, i - 1);
	}
}
void MergeSort(vector <int> a,int n) {//降序归并排序
	int temp[999];//用于归并的临时空间
	int i,j,k,t=1;
	while(t<n)
		t=t*2;
	for (i=2; i<t+1; i*=2) { //二路归并,i每次取一半,规模从小到大归并
		for (j=0; j<n; j+=i) {
			int l=j,r=j+i/2,mid=r-1,pos=j;//left right middle
			if(r>n)
				break;
			while (r<n&&l<=mid&&r<j+i) {
				if (a[l]>a[r])
					temp[pos++]=a[l++];//归并结果存放在临时数组
				else
					temp[pos++]=a[r++];
			}
			while (l<=mid)
				temp[pos++]=a[l++];
			while (r<j+i&&r<n)
				temp[pos++]=a[r++];
			for (k=j; k<j+i&&k<n; k++) //把临时数组中的归并结果存回原数组
				a[k]=temp[k];
		}
	}
}
void partitionMergeSort(vector <int> &a,int l,int r) { //分治归并
	int mid;
	if(l<0 || r>=a.size() || l==r)
		return;
	mid=(l+r)/2;
	partitionMergeSort(a,l,mid);
	partitionMergeSort(a,mid+1,r);//分治
	inplace_merge(a.begin()+l,a.begin()+mid+1,a.begin()+r+1); //归并
}
void wayMergeSort(vector <int> &a,int n) { //二路归并
	int step=1;//步长
	int l,mid,r;
	while(step<n) { //终止条件为整个数组参与归并
		for(int i=0; i+step<n; i+=step*2) { //对数组的各部分归并排序
			l=i;
			mid=i+step;
			r=min(n,i+step*2);//设定二路归并参数
			inplace_merge(a.begin()+l, a.begin()+mid, a.begin()+r);
		}
		step=step*2;
	}
}
void RadixSort(vector <int> a,int n) {//升序基数排序
	int upper=9;//可能的数据上限
	int i,j,k;
	for(i=0; i<n; i++) {
		while(a[i]>upper)
			upper=upper*10+9;//upper=99,999,9999……
	}
	vector <vector<int>> numberlist;//分配数据的链表，用容器实现
	for(i=0; i<10; i++) {
		vector <int> temp;
		numberlist.push_back(temp);//把当前位0-9位数链表头指针加入链表,用容器实现
	}
	int sur=10;//取余Surplus,用来取出数据的对应位数的数字，sur=10时即取个位
	while(sur<10*upper) {//判断循环次数
		for(i=0; i<n; i++) {
			k=a[i];
			k=k%sur;
			k=k/(sur/10);//抽出当前排序位数的数
			numberlist[k].push_back(a[i]);//把数据插入对应链表中
		}
		int p=0;
		for(i=0; i<10; i++) { //输出各子链表数据，分配-收集结果
			if(numberlist[i].empty()) {
			} else {
				for(j=0; j<numberlist[i].size(); j++,p++) {
					a[p]=numberlist[i][j];
				}
				numberlist[i].clear();//清空该链表
			}
		}
		sur*=10;//对高位进行分配-收集的基数排序
	}
}
void CountSort(vector <int> a,int n) {
	vector <int> temp,count;
	int i;
	for(i=0; i<n; i++)
		temp.push_back(a[i]);
	for(i=0; i<n; i++)
		count.push_back(0);//初始化
	for(i=0; i<n; i++)
		count[temp[i]]++;
	for (i = 1; i < n; i++)
		count[i] += count[i - 1];
	for (i = n; i > 0; i--)
		a[--count[temp[i - 1]]] = temp[i - 1];
}
void upCountSort(vector <int> a,int n) {
	int i,loc=0;
	int max0=a[0],min0=a[0];
	for(i=1; i<n; i++) {
		if(a[i]>max0)
			max0=a[i];
		if(a[i]<min0)
			min0=a[i];
	}//找出元素大小的极差，节省空间
	
	int *count=new int[max0-min0+1]{0};
	for(i=0; i<n; i++)
		count[a[i]-min0]++;
	for(i=0; i<max0-min0+1; i++){//在count数组中存放各数据项在排序数组中的位置 
		if(count[i]==0)
			continue;
		loc=loc+count[i];
		count[i]=loc;
	}
 
	int *temp=new int[a.size()];
	for(int index=n-1;index>=0;index--){
		temp[count[a[index]-min0]-1]=a[index];
		count[a[index]-min0]--;
	}
	for(i=0;i<n;i++)
		a[i]=temp[i];//覆盖原数组
}
int main() {
	int n,i,times;
	vector <int> a(SIZE);
	vector <int> original_data(SIZE);
	cout<<"请输入待排序数组大小和测试组数:"<<endl; 
	cin>>n>>times;//输入待排序数组大小和测试组数
	clock_t c_start,c_end;
	double sort_T=0,bubble_T=0,bubble1_T=0,bubble2_T=0,bubble3_T=0,choose_T=0,choose1_T=0,insert_T=0,insert1_T=0,radix_T=0,shell_T=0,shell1_T=0,heap_T=0,recquick_T=0,waymerge_T=0,partitionmerge_T=0,count_T=0,upcount_T=0;
	for(int j=0; j<times; j++) { //随机产生20组测试样本
		srand((unsigned)time(NULL));//srand()函数产生一个以当前时间开始的随机种子
		for(i=0; i<n; i++) { //产生n个0~n的随机数
			original_data[i]=rand()*rand()%n;
		}
		cout<<"第"<<j+1<<"组随机样本"<<endl;
 
		c_start=clock();
		sort(original_data.begin(),original_data.end());//制造完全有序的原始数据，或统计sort函数运行时间 
		c_end=clock();
		sort_T+=double(c_end-c_start)/CLOCKS_PER_SEC;
		
		//for(i=0;i<n/2;i++)//制造完全反序的原始数据
		//	swap(original_data[i],original_data[n-i-1]);
		
		c_start=clock();
		BubbleSort(original_data,n);//调用排序算法
		c_end=clock();
		bubble_T+= double(c_end-c_start)/ CLOCKS_PER_SEC; //   选择比冒泡快：交换次数少   插入比选择快：比较次数少
		
		c_start=clock();
		up1BubbleSort(original_data,n);//调用排序算法
		c_end=clock();
		bubble1_T+= double(c_end-c_start)/ CLOCKS_PER_SEC;//冒泡提前结束
 
		c_start=clock();
		up2BubbleSort(original_data,n);//调用排序算法
		c_end=clock();
		bubble2_T+= double(c_end-c_start)/ CLOCKS_PER_SEC;//冒泡提前结束+增加标志位减少内循环长度
 
		c_start=clock();
		up3BubbleSort(original_data,n);//调用排序算法
		c_end=clock();
		bubble3_T+= double(c_end-c_start)/ CLOCKS_PER_SEC;//双向冒泡
 
		c_start=clock();
		ChooseSort(original_data,n);
		c_end=clock();
		choose_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;
 
		c_start=clock();
		upChooseSort(original_data,n);
		c_end=clock();
		choose1_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//改进选择排序
 
		c_start=clock();
		InsertSort(original_data,n);
		c_end=clock();
		insert_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//插入排序
 
		c_start=clock();
		upInsertSort(original_data,n);
		c_end=clock();
		insert1_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//折半插入排序
 
		c_start=clock();
		RadixSort(original_data,n);
		c_end=clock();
		radix_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//基数排序
 
		c_start=clock();
		ShellSort(original_data,n);
		c_end=clock();
		shell_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//希尔排序
 
		c_start=clock();
		upShellSort(original_data,n);
		c_end=clock();
		shell1_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//改进希尔排序
 
		c_start=clock();
		HeapSort(original_data,n);
		c_end=clock();
		heap_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//堆排序
 
		c_start=clock();
		recQuickSort(original_data,0,n);
		c_end=clock();
		recquick_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//快排时间复杂度受原始序列有序度影响 考虑最坏情况   快排栈溢出exit
 
		c_start=clock();
		for(int k=0;k<1000;k++)
		wayMergeSort(original_data,n);
		c_end=clock();
		waymerge_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//可以优化  exit
 
		c_start=clock();
		partitionMergeSort(original_data,0,n);
		c_end=clock();
		partitionmerge_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//归并排序
		
		c_start=clock();
		CountSort(original_data,n);
		c_end=clock();
		count_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;//计数排序
 
		c_start=clock();
		upCountSort(original_data,n);
		c_end=clock();
		upcount_T+=double(c_end-c_start)/ CLOCKS_PER_SEC;
	}
	
	cout<<"冒泡排序用时："<<bubble_T/times<<endl;
	cout<<"冒泡排序改进1用时："<<bubble1_T/times<<endl;
	cout<<"冒泡排序改进2用时："<<bubble2_T/times<<endl;
	cout<<"双向冒泡排序用时："<<bubble3_T/times<<endl;
	cout<<"选择排序用时："<<choose_T/times<<endl;
	cout<<"改进选择排序用时："<<choose1_T/times<<endl;
	cout<<"插入排序用时："<<insert_T/times<<endl;
	cout<<"改进插入排序用时："<<insert1_T/times<<endl;
	cout<<"基数排序用时："<<radix_T/times<<endl;
	cout<<"希尔排序用时："<<shell_T/times<<endl;
	cout<<"改进希尔排序用时："<<shell1_T/times<<endl;
	cout<<"堆排序用时："<<heap_T/times<<endl;
	cout<<"递归快速排序用时："<<recquick_T/times<<endl;
	cout<<"二路归并排序用时："<<waymerge_T/times<<endl;
	cout<<"分治归并排序用时："<<partitionmerge_T/times<<endl;
	cout<<"计数排序用时："<<count_T/times<<endl;
	cout<<"改进计数排序用时："<<upcount_T/times<<endl;
	cout<<"sort函数用时"<<sort_T/times<<endl; 
 
	cout<<endl;
}