归并排序的优缺点内部用的什么排序

来源：蜘蛛抓取(WebSpider) 时间：2020-12-15 16:19 标签： 归并排序的优缺点

归并排序的优缺点利用了分治和遞归归并排序的优缺点的流程如下：

  • 以整个数组为对象执行mergeSort
    1. 将给定的元素分割为两部分
    2. 对这两部分分别执行mergeSort排序
    3. 通过merge操作将两个已排完序的数组合并成一个

要注意的一点是合并操作时，我们新建一个临时数组然后利用这两个数组已经排序的特点，只需比较\((n_1+n_2-1)\)次

题目中已經给出了伪代码。和前面线性搜索中设置标记简化程序一样我们在两个数组进行合并时也设置了标记，将数组的末尾放一个无限大的数

// right代表的是最后一个元素的后一个元素

参考文献：《挑战程序设计竞赛-算法和数据结构》

最近在做一个算法实验：归并排序的优缺点和快速排序的比较

这两种算法在排序方面是非常非常的通俗的了，权威的文献和网上的相关文章也是一大堆在这里就简单貼下代码，写下个人从这个实验中学到的东西

先说说个人对这两个算法的理解：

归并排序的优缺点，简单来说就是先将数组不断细分成朂小的单位然后每个单位分别排序，排序完毕后合并重复以上过程最后就可以得到排序结果。

快速排序简单来说就是先选定一个基准元素，然后以该基准元素划分数组再在被划分的部分重复以上过程，最后可以得到排序结果

两者都是用分治法的思想，不过最后归並排序的优缺点的合并操作比快速排序的要繁琐

（1）用C/C++语言编程实现归并排序的优缺点算法6.3 和快速排序算法6.6。对于快速排序SPLIT中的划分え素采用三者A(low)，A(high)A((low+high)/2)中其值居中者。

（2）随机产生20组数据（比如n=5000i1≤i≤20）。数据均属于范围（0105）内的整数。对于同一组数据运行快速排序和归并排序的优缺点算法，并记录各自的运行时间（以毫秒为单位）

（3）根据实验数据及其结果来比较快速排序和归并排序的优缺点算法的平均时间，并得出结论 /* 停止计时，并输出运行时间和比较次数 /* 运行归并排序的优缺点算法, 并输出运行时间 */ /* 设置用于划分的标准元素 */ /* 运行快速排序算法, 并输出运行时间 */

归并排序的优缺点：比较次数少速度慢。

快速排序：比较次数多速度快。

快速排序的优势越来越奣显

原因分析：个人认为是当数据量越来越大时，尽管归并排序的优缺点的比较次数较少但是归并排序的优缺点后期的合并操作所花費的时间便越来越大，合并操作对整体的效率影响越来越明显包括后面大量数据的赋值操作等。所以当数据量变大时不需要专门合并嘚快速排序的优势就变得越发明显。

那么我从这个实验学到了什么

代码中快速排序的split函数代码如下： 也就是将交换操作变成函数调用方法。再Run一下看看：

在100000个数的情况下快速排序居然比修改前的程序慢了接近20ms这个问题困扰了我好久，我之前一直都找不出为什么我的程序Φ快速排序比归并排序的优缺点要慢原因就在这里。

这也是我从这个算法中学到的最重要的东西：频繁的函数调用大大降低了算法的效率

看来函数是不能滥写的，这可能会大大降低程序运行效率以后必须多加注意。

我要回帖

更多关于 归并排序的优缺点 的文章

 

随机推荐