80数据结构第七章排序7.5归并排序 80数据结构第七章排序7

7.4.3堆排序一性能分析。1：堆排序的时间复杂度为：本次课程内容为《数据结构》第七章。

它这种不稳定的排序，接下来再看看叫做规并排序。什么是规定排？有的地方称为叫合并排序，有的地方称为叫规并或者两路规并。什么叫规并？其实这个有点类似前面快速排序的一种反应过程，前面是进行划分，这里面是把不同的把它合并在一起。

首先将两个以上合并成一个有序的序列叫做规避。通常是用两个规避，将两个位相应的记录进行规定。这样的一个情况是有序子序列，让这里把它变成一个，这个说的可能不是特别明显。这里给大家讲一下。

比如说有n个元素，假设是132、467，这是58，这样子怎么做？把这两个周围一录合并进行排序版，这一说，这两个周围一录，二四进行排列，六七进行排列。大家会发现这里面好像都能已经一个顺序了。

接下，把这两个又作为一个整体，把它合在一起，这里面作为新的排序，就是1234，这个又做一个新的排序，就变成5678。这里面是两个序列，再把这两个序列合并在一起，直接读到12345678，这个就叫做两路合并。每一次把两路合在一起慢慢的就变成一个序列了，本来很多个序列变成一个序列了，这叫做规避。

例如，如下图为2-路归并的一个例子：我们看这规定是什么？首先这个就是这里合并，合并合并，这种两个进行合并，变成这个，再进行合并，变成这个，这种变成引路。

规避排序的算法要注意：它是一般由几个部分组成：

·第一个是前面这一个，就按照关键字来进行排序，归并为一个记录的有序序列。可以变成一个有序的这一款。这慢慢的就得到了这种形式规避算法只能变成引路。

这里面注意其实对n个记录进行规避的时间复杂度，也是这一个n乘以那个n。这个是一个线性阶乘以一个倍数阶。每一趟规定的时间复杂度是on，总共需要进行logon ton。

结论首先规定排序的时间复杂度是什么呢？它应该是这一个，所需的复杂空间是on，它是一个稳定的排序。