下载文档原格式
算法调研报告算法调研报告一、引言算法是计算机科学中的核心概念，它是一种有序的操作序列，用来解决特定问题或完成特定任务。
不同的算法在解决同一个问题时，可能会有不同的时间和空间复杂度，因此正确选择合适的算法对于程序的性能至关重要。
本报告将对几种常用的算法进行调研。
二、排序算法1. 冒泡排序冒泡排序是一种简单直观的排序算法，它重复地遍历要排序的数组，比较相邻元素的大小并交换，直到整个数组按照要求有序。
冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
2. 快速排序快速排序是一种高效的排序算法，它采用分治的策略。
通过选择一个元素作为基准，将数组分成两部分，一部分小于基准，一部分大于基准，然后递归地对两部分进行排序。
快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。
三、查找算法1. 二分查找二分查找是一种在有序数组中查找特定元素的算法。
它通过比较中间元素和目标元素的大小关系，缩小查找范围，最终找到目标元素或确定目标元素不存在。
二分查找的时间复杂度为O(logn)，空间复杂度为O(1)。
2. 哈希查找哈希查找是一种通过计算目标元素的哈希值，将其映射到数组中的位置进行查找的算法。
哈希查找的时间复杂度为O(1)，但需要额外的空间来存储哈希表。
四、图算法1. 广度优先搜索广度优先搜索是一种用于图的遍历的算法。
它从图中的一个顶点开始，逐层遍历图中的顶点，直到所有顶点都被访问过。
广度优先搜索的时间复杂度为O(|V|+|E|)，其中V为顶点数，E 为边数。
2. 最短路径算法最短路径算法用于寻找图中两个顶点之间的最短路径。
常见的最短路径算法有迪杰斯特拉算法和弗洛伊德算法。
迪杰斯特拉算法适用于求解单源最短路径，时间复杂度为O(|V|^2)。
弗洛伊德算法适用于求解多源最短路径，时间复杂度为O(|V|^3)。
五、总结本报告对常用的排序算法、查找算法和图算法进行了调研，分析了它们的时间复杂度和空间复杂度。
常用排序算法分析比较排序算法是计算机科学中的基本概念之一，它主要用于对一组元素进行排序，使得这些元素按照某种规则有序排列。
常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等等，这些算法都有自己的特点和适用场景，下面针对这些排序算法进行分析比较。
1.冒泡排序冒泡排序是一种简单的排序算法，它的主要思想是依次比较相邻的两个元素，如果它们的顺序不对就交换它们的位置，可以保证每次循环后最后一个元素是已经排序好的。
冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
2.插入排序插入排序是一种稳定的排序算法，它的基本思想是将待排序的数据分为两个区间，已排序区间和未排序区间，在未排序区间内遍历，将每个元素插入到已排序区间的合适位置。
插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
3.选择排序选择排序是一种比较简单的排序算法，它的主要思想是通过不断选择未排序区间内的最小值，然后和未排序区间的第一个元素交换位置，以此类推，直到排序完毕。
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
4.快速排序快速排序是一种经典的排序算法，它的思想是采用分治的思想，将序列分为左右两个子序列，通过递归的方式对左右两个子序列进行快速排序，最后合并两个排好序的子序列。
快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。
5.归并排序归并排序是一种稳定的排序算法，它的基本思想是采用分治的思想，将序列分为左右两个子序列，通过递归的方式对左右两个子序列进行排序，最后将两个排好序的子序列合并成一个有序序列。
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
通过比较以上五种排序算法，可以发现每种算法都有自己的特点和适用场景，对于元素数量较少的情况下，可以选择冒泡排序、插入排序或选择排序，这些算法思路简单易懂，实现也比较容易；对于大规模数据排序，可以选择归并排序或快速排序，因为它们的时间复杂度比较优秀。
各种排序算法的总结和比较1 快速排序（QuickSort ）快速排序是一个就地排序，分而治之，大规模递归的算法。
从本质上来说，它是归并排序的就地版本。
快速排序可以由下面四步组成。
（1 ）如果不多于1 个数据，直接返回。
（2 ）一般选择序列最左边的值作为支点数据。
（3 ）将序列分成2 部分，一部分都大于支点数据，另外一部分都小于支点数据。
（4 ）对两边利用递归排序数列。
快速排序比大部分排序算法都要快。
尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。
快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序（MergeSort ）归并排序先分解要排序的序列，从1 分成2 ，2 分成4 ，依次分解，当分解到只有1 个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。
合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序( HeapSort )堆排序适合于数据量非常大的场合(百万数据)。
堆排序不需要大量的递归或者多维的暂存数组。
这对于数据量非常巨大的序列是合适的。
比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。
接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell 排序( ShellSort )Shell 排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。
平均效率是O(nlogn) 。
其中分组的合理性会对算法产生重要的影响。
现在多用D.E.Knuth 的分组方法。
Shell 排序比冒泡排序快5 倍，比插入排序大致快2 倍。
Shell 排序比起QuickSort ，MergeSort ，HeapSort 慢很多。
各种内排序算法的实验心得
1. 冒泡排序
冒泡排序是一种简单的排序算法，但它的时间复杂度为O(n^2)，在处理大量数据时效率很低。
在实验过程中，我发现当数据量较小时，冒泡排序的效率其实还是不错的，但一旦数据量增加，它的效率就明显下降了。
2. 插入排序
插入排序的时间复杂度也是O(n^2)，类似于冒泡排序。
但是插入排序比冒泡排序更快，因为它每次只需要比较一个元素。
在实验中，我发现当数据量比较小且有序时，插入排序的效率非常高，但如果数据量较大且随机分布，效率就会明显下降。
3. 选择排序
选择排序同样是时间复杂度为O(n^2)的算法，但是它比冒泡排序和插入排序都要快。
在实验中，我发现当数据量很大时，选择排序的效率比较稳定，但是当数据量比较小时，它的效率反而不如插入排序。
4. 快速排序
快速排序是一种常用的排序算法，它的时间复杂度为O(nlogn)，比冒泡、插入和选择排序都要快。
在实验中，我发现当数据量比较大时，快速排序的效率非常高，但是当数据量比较小时，它的效率反而不如插入排序和选择排序。
5. 归并排序
归并排序与快速排序的时间复杂度相同，都是O(nlogn)。
但是归并排序比快速排序更稳定，因为它的最坏时间复杂度是O(nlogn)。
在实验中，我发现当数据量比较大时，归并排序的效率非常高，而且在处理大量数据时表现优异。
6. 基数排序
基数排序是一种特殊的排序算法，它适用于数据量较大且每个元素长度相同的情况。
在实验中，我发现基数排序的效率非常高，尤其是对于大量数据的排序。
但需要注意的是，基数排序无法处理字符串等非数字类型的数据。
软件工程师常见算法分析一、概述在软件开发中，算法是程序员必备的核心能力之一。
算法是解决问题的方法和步骤，是一种数学思维方式的体现。
对于软件工程师而言，常见的算法分析是学习和掌握各种算法的性能特点，选择合适的算法来解决具体的问题。
本文将介绍一些常见的算法以及其分析。
二、冒泡排序算法冒泡排序是一种简单且常见的排序算法。
它通过不断比较相邻的两个元素，并根据规则交换位置，实现将较大（或较小）的元素逐渐“冒泡”到最终位置的目的。
冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
三、插入排序算法插入排序是一种简单且高效的排序算法。
它将数组分为已排序和未排序两个部分，逐个将未排序的元素插入到已排序的部分中，使得整个数组有序。
插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
四、选择排序算法选择排序是一种简单但较低效的排序算法。
它通过不断选择最小（或最大）的元素，并放置到已排序部分的末尾，实现整个数组的排序。
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
五、快速排序算法快速排序是一种高效的排序算法。
它采用分治思想，通过确定一个基准元素，将数组划分为两个子数组，并递归地对子数组进行排序，最终实现整个数组的排序。
快速排序的时间复杂度通常为O(nlogn)，空间复杂度为O(logn)。
六、二分查找算法二分查找是一种常见的搜索算法。
它适用于有序数组，通过不断将待查找区间缩小为一半，最终找到目标元素的位置。
二分查找的时间复杂度为O(logn)，空间复杂度为O(1)。
七、动态规划算法动态规划是一种常见且重要的算法思想。
它通过将大问题拆分为子问题，并存储子问题的解，避免重复计算，从而提高算法的效率。
常见的动态规划问题包括斐波那契数列、背包问题等。
八、贪心算法贪心算法是一种简单且常用的算法思想。
它通过每一步选择当前状态下的最优解，从而希望得到全局最优解。
贪心算法通常适用于当局部最优解能够导致全局最优解的情况。
五种常见的排序方法排序是计算机科学中最基础、最重要的算法之一。
排序算法的目的是将一组数据按照某个规则进行排序，以便于查找、统计和分析。
排序算法在各个领域都有广泛的应用，如数据库查询、图像处理、搜索引擎等。
本文将介绍五种常见的排序方法，它们分别是冒泡排序、选择排序、插入排序、快速排序和归并排序。
一、冒泡排序冒泡排序是最简单、最容易理解的排序算法之一。
它的基本思想是将相邻的两个元素进行比较，如果前面的元素大于后面的元素，则交换它们的位置。
这样一轮下来，最大的元素就会“冒泡”到最后面。
接着进行下一轮比较，直到所有元素都排好序。
冒泡排序的时间复杂度为O(n^2)，其中n为待排序元素的个数。
虽然冒泡排序的时间复杂度较高，但由于它的实现简单，所以在某些特定情况下还是有用武之地的。
二、选择排序选择排序是一种简单直观的排序算法。
它的基本思想是从待排序的元素中选择最小的元素，将它放在第一个位置；然后从剩余的元素中选择最小的元素，将它放在第二个位置；以此类推，直到所有元素都排好序。
选择排序的时间复杂度也是O(n^2)，但相比冒泡排序，它的比较次数要少一些。
选择排序的优点是不占用额外的内存空间，但它的缺点是不稳定，即相同元素的相对位置可能会发生变化。
三、插入排序插入排序是一种简单而有效的排序算法。
它的基本思想是将待排序的元素插入到已排好序的元素中，使得插入后的序列仍然有序。
插入排序可以分为直接插入排序和希尔排序两种。
直接插入排序的时间复杂度为O(n^2)，但如果待排序的元素已经基本有序，那么它的时间复杂度会降低到O(n)。
希尔排序是直接插入排序的改进版，它通过将待排序的元素分组，先对每个小组进行排序，然后逐步缩小组的大小，最终整个序列就会变得有序。
希尔排序的时间复杂度介于O(n)和O(n^2)之间，取决于所选的增量序列。
插入排序的优点是对于小规模的数据集合，它的效率比较高；缺点是不适用于大规模的数据集合，而且它是稳定排序算法。
排序算法比较在计算机科学中，排序算法是一类重要且基础的算法。
通过对数据进行排序，我们可以更高效地检索、查找以及分析数据。
在实际应用中，我们经常需要比较不同排序算法的性能和效率，以便选择最适合特定任务的排序算法。
本文将对几种常见的排序算法进行比较。
一、冒泡排序冒泡排序是一种简单但效率较低的排序算法。
其基本思想是通过多次交换相邻的元素，将最大（或最小）的元素逐渐“冒泡”到待排序序列的末尾。
具体实现过程如下：从头开始依次比较相邻的两个元素，如果顺序不正确，则进行交换。
重复此过程，直到没有任何交换发生。
冒泡排序的时间复杂度为O(n^2)，其中n为待排序序列的长度。
这使得冒泡排序在大规模数据排序时表现较差。
二、插入排序插入排序是一种简单且高效的排序算法。
它的基本思想是将未排序部分的元素依次插入到已排序部分的正确位置，直到全部元素都有序。
具体实现过程如下：将未排序部分的第一个元素插入到已排序部分中的正确位置，然后再将第二个元素插入到已排序部分中，依此类推。
插入排序的时间复杂度为O(n^2)，但在实际应用中，插入排序通常要比冒泡排序快得多。
插入排序对于小规模或基本有序的数据集合表现良好。
三、选择排序选择排序是一种简单但不稳定的排序算法。
其基本思想是从未排序部分选择最小（或最大）的元素，将其放到已排序部分的末尾。
具体实现过程如下：从未排序部分中选出最小的元素，将其与未排序部分的第一个元素交换位置，然后将已排序部分的长度加1。
重复此过程，直到全部元素都有序。
选择排序的时间复杂度为O(n^2)，与冒泡排序和插入排序相同。
尽管选择排序的性能较差，但由于其实现简单，对于小规模数据集合仍然是一种可用的排序方法。
四、快速排序快速排序是一种高效的排序算法，常被用作标准库中的排序函数实现。
其基本思想是通过分治的策略将待排序序列划分为较小和较大的两个子序列，然后分别对子序列进行递归排序。
具体实现过程如下：选择一个基准元素，通过一趟排序将待排序序列分割为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。
一．七大排序算法基本属性1.稳定性KMP模糊匹配算法二叉树的建立顺序查找：哨兵设置二．七大排序算法（）/jingmoxukong/p/4329079.html1.冒泡排序：冒泡排序是一种交换排序。
什么是交换排序呢？交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。
算法思想它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。
假设有一个大小为N 的无序序列。
冒泡排序就是要每趟排序过程中通过两两比较，找到第i 个小（大）的元素，将其往上排。
图-冒泡排序示例图以上图为例，演示一下冒泡排序的实际流程：假设有一个无序序列{ 4. 3. 1. 2, 5 }第一趟排序：通过两两比较，找到第一小的数值1 ，将其放在序列的第一位。
第二趟排序：通过两两比较，找到第二小的数值2 ，将其放在序列的第二位。
第三趟排序：通过两两比较，找到第三小的数值3 ，将其放在序列的第三位。
至此，所有元素已经有序，排序结束。
要将以上流程转化为代码，我们需要像机器一样去思考，不然编译器可看不懂。
假设要对一个大小为N 的无序序列进行升序排序（即从小到大）。
(1) 每趟排序过程中需要通过比较找到第i 个小的元素。
所以，我们需要一个外部循环，从数组首端(下标0) 开始，一直扫描到倒数第二个元素（即下标N - 2) ，剩下最后一个元素，必然为最大。
(2) 假设是第i 趟排序，可知，前i-1 个元素已经有序。
现在要找第i 个元素，只需从数组末端开始，扫描到第i 个元素，将它们两两比较即可。
所以，需要一个内部循环，从数组末端开始（下标N - 1），扫描到(下标i + 1)。
核心代码public void bubbleSort(int[] list) {int temp = 0; // 用来交换的临时数// 要遍历的次数for (int i = 0; i < list.length - 1; i++) {// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上for (int j = list.length - 1; j > i; j--) {// 比较相邻的元素，如果前面的数大于后面的数，则交换if (list[j - 1] > list[j]) {temp = list[j - 1];list[j - 1] = list[j];list[j] = temp;}}}}时间复杂度若文件的初始状态是正序的，一趟扫描即可完成排序。
深圳大学实验报告课程名称：算法分析与复杂性理论实验项目名称：实验一排序算法性能分析学院：计算机与软件学院专业：软件工程指导教师：**报告人：赖辉学号：班级：软工学术型实验时间：2015-10-15实验报告提交时间：2015-11-24教务部制一．实验目的1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。
二．实验步骤与结果实验总体思路：根据实验要求，需要用while循环控制用户选择相应算法(选择通过switch实现)或者选择输入0跳出while循环，退出程序。
Switch中选择相应的算法后需要通过一个for(int j=0;j<5;j++)循环更改数组大小MAX的值(MAX *= 10)，从而控制输入不同问题规模的耗时。
再通过一个for(int i=0;i<20;i++)循环控制20组随机数组。
为了使得程序输出更加直观，部分数据后面没有输出。
相应结果和过程如下所示（代码和结果如下图所示）。
各排序算法的实现及实验结果：1、随机数产生代码1：srand((unsigned)time(NULL));For i=0 to 19randNum(MAX,array);当问题规模较小时，生成随机函数randNum()在for循环下运行时间短，每次产生的随机数组都是一样的，将srand((unsigned)time(NULL))语句放在for循环外面，就产生了20组不同的随机数组。
图1、产生20组随机数组2、选择排序代码2：for i=0 to n-2min=ifor j= i+1 to n-1if ele[min]>ele[j] min=jswap(ele[i],ele[min]) //交换元素图2、选择排序在不同数据规模下排序所消耗的时间3、冒泡排序代码3：for i= 0 to n-1for j=0 to n-1-iif a[j]>a[j+1]swap(a[j],a[j+1]) //交换图3、冒泡排序在不同数据规模下排序所消耗的时间3、合并排序代码4：MERGE(A, p, q, r)n1 ←q - p + 1n2 ←r - qcreate arrays L[1 ‥n1 + 1] and R[1 ‥n2 + 1]for i ←1 to n1do L[i] ←A[p + i - 1]for j ←1 to n2do R[j] ←A[q + j]L[n1 + 1] ←∞R[n2 + 1] ←∞i ←1j ←1for k ←p to rdo if L[i] ≤R[j]then A[k] ←L[i]i ←i + 1else A[k] ←R[j]j ←j + 1图4、合并排序在不同数据规模下排序所消耗的时间4、快速排序代码5：quick(ele[0...n-1],left,right)if l<rl←left r←right x←ele[l];while l<rwhile l<r && x<=ele[r] //比x小则之后交换到前面的部分r--if l<rele[l]←ele[r] l++while l<r && x>ele[l] //比x大则前面交换到后面部分ll++if l<rele[r]←ele[l] r--ele[l]←x;quick(ele,left,l-1) // 递归调用quick(ele,l+1,right)图5、快速排序在不同数据规模下排序所消耗的时间5、插入排序代码6：for i=1→n-1if ele[i]<ele[i-1] temp=ele[i]for j= i-1 to 0 && ele[j]>tempele[j+1]←ele[j]ele[j+1]←temp图6、插入排序在不同数据规模下排序所消耗的时间三．实验分析选择排序：图7、由图2数据整合而成的折线图数据规模：10 100 1000 10000 100000耗时（ms）0 0 2.05 195.25 19868.5图形上：形状基本符合n2（二次增长）数据上：我们发现当数据规模增大10倍时：1000→10000： 195.25/2.05=95.24≈10010000→100000：19868.5/195.25=101.75≈100其他倍数也可得到类似的结果。
结论：当数据规模为10和100时因为数据太小，耗时约为0。
但当数据规模为1000增大到10000时，并10000到100000时，规模增大10倍耗时都增大约100倍，可以计算出，选择排序的时间复杂度为o（n2）。
冒泡排序：图8、由图3数据整合而成的折线图表2、冒泡排序在不同数据规模下排序所消耗的时间数据规模：10 100 1000 10000 100000耗时（ms）0 0.1 2 194.15 19708图形上：形状基本符合n2（二次增长）数据上：我们发现当数据规模增大10倍时：100→1000：2/0.1=20 （误差太大）1000→10000:194.15/2=97.075 ≈ 10010000→100000:19708/194.15=101.5 ≈ 100其他倍数也可得到类似的结果。
结论：由于开始问题规模较小，产生误差较大，但随着问题规模的按10的倍数增大，耗时逐渐呈100的倍数增大，分析伪代码也可以算出该算法的时间复杂度为o（n2）。
随着问题规模的增大，多种误差会逐渐累积，耗时会超过o（n2）的倍数，但是整体上不会相差太大。
与此相比，电脑等其他因素造成轻微的误差可以忽略不计。
合并排序：图9、由图4数据整合而成的折线图数据规模：10 100 1000 10000 100000耗时（ms）0 0.1 0.7 6.05 59.2图形上：形状基本符合n（线性增长）数据上：我们发现当数据规模增大10倍时：100→1000：:0.7/0.1=7 ≈10（误差较大）1000→10000： 6.05/0.7=8.64 ≈1010000→100000：59.2/6.05=9.78 ≈10其他倍数也可得到类似的结果。
结论：根据该算法的伪代码，可以计算出时间复杂度为o（nlog2n），当数据规模扩大10倍时，耗时呈线性增长，逐渐接近于n。
当数据规模扩大n倍时，相应的在时间的消耗上会扩大nlog2n倍，同时我们发现，理论上乘以nlog2n后的数据普遍会略小于实际数据，这主要原因快速排序需要递归调用，递归调用需要花费额外的时间。
快速排序：图10、由图5数据整合而成的折线图数据规模：10 100 1000 10000 100000耗时（ms）0 0 1.5 12.15 137.95图形上：形状基本符合n（线性增长）数据上：我们发现当数据规模增大10倍时：1000→10000：:12.15/1.5=8.1 ≈ 1010000→100000： 137.95/12.15=10.1 ≈10其他倍数也可得到类似的结果。
结论：根据快速排序算法的伪代码，可以分析出该算法的时间复杂度是o（nlog2n），当数据规模扩大n倍时，相应的在时间的消耗上会扩大nlog2n倍。
从实验的数据上，可以看出随着问题规模的增大，耗时上面也呈线性增长，但累积起来的误差也使得程序的结果略微高于实验值。
总体上的实验结果和预期还是很接近的。
插入排序：图11、由图6数据整合而成的折线图表5、插入排序在不同数据规模下排序所消耗的时间数据规模：10 100 1000 10000 100000 耗时（ms）0 0 1.2 112.85 11329.5图形上：形状基本符合n2（二次增长）数据上：我们发现当数据规模增大10倍时：1000→10000： 112.85/1.2=94 ≈10010000→100000： 11329.5/112.85=100.4 ≈100其他倍数也可得到类似的结果。
结论：根据插入算法的伪代码，可以计算出该算法的时间复杂度是o（n2），当数据规模扩大n倍时，相应的在时间的消耗上会扩大n2倍，理论上，如果数据大具有特殊性，那此算法被影响的程度会比较大，他的的比较次数可以从线性次数，到n2次，赋值次数也可能由常数次变成n2总的来说，受数据影响较大。
将五种排序的实验汇总在一起，如下图12所示图12、由图7、8、9、10、11整合而来从图中以及之前的分析中我们可以得到以下结论1、在平均时间复杂度上面，冒泡排序、插入排序和选择排序都最差为o（n2）。
其主要原因是：随着问题规模的增大，冒泡排序在比较次数上达到了o（n2），但这种排序同时也受交换次数的影响，而且最多时间复杂度也是o（n2）。
如此，同样是o（n2），但冒泡排序的二次项系数会比另外两个大不少，所以最为耗时。
2、快速排序和合并排序都表现出比较好的复杂度。
但这两者中，合并排序表现更好。
其原因是：在最坏情况下，即整个序列都已经有序且完全倒序的情况下，快速排序呈o（n2）的增长，而归并排序不管在什么情况下都呈o（nlog2n），随着问题规模的增大，快速排序逐渐体现出这种弊端。
四．实验心得本次实验虽然花费很大的心思，但确实让我对这几种排序的认识更加深刻，同样的数据，排序的时间可以相差如此之大，这可能会改变我每次都使用冒泡排序的这一习惯，同时，对算法的优良性不同而导致的结果差异之大，感觉到好的算法是多么的重要，当然合理利用算法也是不可忽视的。
这次实验虽然花了很大精力，却收获累累。
注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
附录：代码#include<stdio.h>#include<iostream>#include<windows.h>#include <Mmsystem.h>using namespace std;#include <ctime>#include <fstream>using namespace std;#define ARRAY_MAX 100000/*****************************生成随机函数*************************/ void randNum(int MAX,int *array){//srand((unsigned)time(NULL));//cout<<"生成的随机数为："<<endl;;for(int i=0;i<MAX;i++){array[i] = rand()%100;//cout<<array[i]<<" ";}//cout<<"\t\t耗时：";}/*****************************选择排序*************************/ void select_sort(int MAX,int *array){int i, j, k;for (i = 0; i < MAX; i++){k = i;for (j = i + 1; j < MAX; j++){if (array[j] < array[k]){k = j;}}if (k != i){int temp = array[k];array[k] = array[i];array[i] = temp;}}}/***************************冒泡排序*************************/void buddle_sort(int MAX,int *array){int i, j;for(i=0;i<MAX;i++){for(j=i+1;j<MAX;j++){if(array[i]>array[j]) swap(array[i],array[j]);}}}/***************************合并排序*************************/ void Merge(int *array, int p, int q, int r){int n1 = q - p + 1;int n2 = r - q;int *L, *R, i, j, k;L = new int[n1 + 1];R = new int[n2 + 1];for (i = 0; i < n1; i++)L[i] = array[p + i];for (i = 0; i < n2; i++)R[i] = array[q + 1 + i];L[n1] = INT_MAX;R[n2] = INT_MAX;for (i = 0, j = 0, k = p; k <= r; k++){if (L[i] <= R[j]){array[k] = L[i++];}else{array[k] = R[j++];}}delete []L;delete []R;}void merge_sort(int *array, int p, int r){if (p < r){int q = (p + r) / 2;merge_sort(array, p, q); //递归调用merge_sort(array, q + 1, r);Merge(array, p, q, r);}else{return;}}/***************************快速排序*************************/ void quick_sort(int a[], int low, int high){if(low >= high){return;}int first = low;int last = high;int key = a[first];while(first < last){while(first < last && a[last] >= key){--last;}a[first] = a[last]; //将比第一个小的数移到后面while(first < last && a[first] <= key){++first;}a[last] = a[first]; //将比第一个大的数移到前面}a[first] = key; //记录当前位置quick_sort(a, low, first-1);quick_sort(a, first+1, high);}/***************************插入排序*************************/ void insert_sort(int MAX,int *array){int i, j, temp;for (i = 1; i < MAX; i++){temp = array[i];for(j=i;j > 0 && array[j-1] > temp;j--){array[j] = array[j-1];}array[j] = temp;}}int main(){int n,loop = 1;while(loop != 0){//产生随机数组clock_t time_start,time_end;double time_used = 0,count = 0;int MAX = 10;int array[ARRAY_MAX];cout<<"\n\t\t请输入序号选择相应的操作："<<endl;cout<<"1.选择排序 2.冒泡排序 3.合并排序 4.快速排序 5.插入排序0.退出程序"<<endl;cout<<"******************************************************************"< <endl;cin>>n;switch(n){case 0: loop = 0;break;case 1:for(int j=0;j<5;j++){ //控制问题规模MAX从10-100000cout<<"数组规模MAX="<<MAX<<" 时,耗时："<<endl;srand((unsigned)time(NULL));for(int i=0;i<20;i++){ //控制20组随机数产生randNum(MAX,array);time_start = clock();select_sort(MAX,array);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" ";//cout<<endl;count += time_used;}cout<<"\n选择排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count = 0;MAX *= 10;}break;case 2:for(int j=0;j<5;j++){ //控制问题规模MAX从10-100000cout<<"数组规模MAX="<<MAX<<" 时,耗时："<<endl;srand((unsigned)time(NULL));for(int i=0;i<20;i++){ //控制20组随机数产生randNum(MAX,array);time_start = clock();buddle_sort(MAX,array);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" ";//cout<<endl;count += time_used;}cout<<"\n冒泡排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count = 0;MAX *= 10;}break;case 3:for(int j=0;j<5;j++){ //控制问题规模MAX从10-100000cout<<"数组规模MAX="<<MAX<<" 时,耗时："<<endl;srand((unsigned)time(NULL));for(int i=0;i<20;i++){ //控制20组随机数产生randNum(MAX,array);time_start = clock();merge_sort(array,0,MAX-1);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" ";//cout<<endl;count += time_used;}cout<<"\n合并排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count = 0;MAX *= 10;}break;case 4:for(int l=0;l<5;l++){ //控制问题规模MAX从10-100000cout<<"数组规模MAX="<<MAX<<" 时,耗时："<<endl;srand((unsigned)time(NULL));for(int i=0;i<20;i++){ //控制20组随机数产生randNum(MAX,array);time_start = clock();quick_sort(array,0,MAX);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" ";//cout<<endl;count += time_used;}cout<<"\n快速排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count = 0;MAX *= 10;}break;case 5:for(int j=0;j<5;j++){ //控制问题规模MAX从10-100000cout<<"数组规模MAX="<<MAX<<" 时,耗时："<<endl;srand((unsigned)time(NULL));for(int i=0;i<20;i++){ //控制20组随机数产生randNum(MAX,array);time_start = clock();insert_sort(MAX,array);time_end = clock();time_used = time_end - time_start;cout<<time_used<<" ";//cout<<endl;count += time_used;}cout<<"\n插入排序平均耗时："<<count/20<<"毫秒"<<endl<<endl;count = 0;MAX *= 10;}break;default: cout<<"请输入合法的序号！";}}return 0;}。
