当前位置：首页 > news >正文

STL算法之merge sort

news 2025/3/10 15:12:52

在 STL算法之其它算法_下-CSDN博客中，我们对inplace_merge进行了简要的描述，但是对里面的细节描述的不是很清晰；本章进行更细致的拆解；同时inplace_merge将使用merge sort作为实现算法的主要手段。

inplace_merge（应用于有序区间）

merge sort

inplace_merge（应用于有序区间）

如果两个连接在一起的序列[first,middle)和[middle,last)都已经排序，那么inplace_merge可将它们结合成单一一个序列，并仍保有序性。如果原先两个序列式递增排序，执行结果也会是递增序列，如果原先两个徐磊是递减序列，执行结果也会是递减序列。

和merge一样，inplace_merge也是一种稳定操作。每个作为数据来源的子序列中的元素相对次序都不会变动；如果两个子序列有等同的元素，第一序列的元素会被排在第二元素之前。

inplace_merge 默认使用operator<作为排序依据，同时可接受仿函数comp作为比较运算符的替代。默认源码如下：

template <class BidrectionalIterator>
inline void inplace_merge(BidrectionalIterator first,BidrectionalIterator middle,BidrectionalIterator last) {if (first == middle || middle == last) return ;__inplace_merge_aux(first, middle, last, value_type(first), distance_type(first));
}template <class BidrectionalIterator, class T,  class Distance>
inline void inplace_merge_aux(BidrectionalIterator first,BidrectionalIterator middle,BidrectionalIterator lastT*, Distance*) {Distance len1 = 0;distance(first, middle, len1);Distance len2 = 0;distance(middle, last, len2);//注意，本算法会使用额外的内存空间(暂时缓冲区)temporary_buffer<BidrectionIterator, T> buf(first, last);if (buf.begin() == 0)   // 内存配置失败__merge_without_buffer(first, middle, last, len1, len2);else _merge_adaptive(first, middle, last, len1, len2, buf, buf.begin(), Distance(buf.size()));}

这个算法如果有额外的内存（缓冲区）辅助，效率会好很多。但是在没有缓冲区或缓冲区不足的情况下，也可以运作，为了篇幅，我们接下来的源码主要讨论有缓冲区的情况。

// 辅助函数。有缓冲区的情况
template <class BidrectionalIterator,  class Distance, class Pointer>
void __merge_adaptive(BidrectionalIterator first,BidrectionalIterator middle,BidrectionalIterator last,Distaince len1, Distaince len2,Pointer buffer, Distance buffer_size) {if (len1 <= len2 && len1 <= buffer_size) { // case1. 缓冲区足够安置序列1Pointer end_buffer = copy(first, middle, buffer);merge(buffer, end_buffer, middle, last, first);} else if ( len2 <= buffer_size) { //case2. 缓冲区足够安置序列2Pointer end_buffer = copy(middle, last, buffer);__merge_backward(first, middle, buffer, end_buffer, last);} else { // case3. 缓冲区空间不足安置任何一个序列BidrectionalIterator first_cut = first;BidrectionalIterator second_cut = middle;Distance len11 = 0;Distance len22 = 0;if (len1 > len2) {len11 = len1 / 2;advance(first, len11);sencond_cut = lower_bound(middle, last, *first_cut);distance(middle, second_cut, len22);} else {len22 = len2 / 2;advance(second_cut, len22);first_cut = upper_bound(first, middle, *second_cut);distance(first, first_cut, len11);}BidrectionalIterator new_middle = __rotate_adative(first_cut, middle, second_cut, len1 - len11, len22, buffer, buffer_size);// 针对左半段，递归调用__merge_adaptive(first, first_cut, new_middle, len1, len22, buffer, buffer_size);// 针对右半段，递归调用__merge_adaptive(new_middle, second_cut, last, len1 - len11, len2 - len22, buffer, buffer_size);}
}

上面的辅助函数首先判断缓冲区是否足以容纳inplace_merge所接受的两个序列中的任何一个。如果空间充裕(源代码中标示case1和case2之处)，工作逻辑很简单：把两个序列中的某一个copy到缓冲区，再使用merge完成其余的工作。此处的merge逻辑比较简单，只需从两个序列的first进行比较，将较小的first元素填入目的迭代器，同时对应的++first。其示例如下：

但是当缓冲区不足以容纳任何一个子序列是(源代码中标示case3处)，情况就棘手很多。面对这种情况，我们的处理原则是，以递归分割(recursive partitioning)的方式，让长序列减半，看看是否容纳于缓冲区中。如上图中的缓冲区大小为3，小于序列一的长度4和序列二的长度5，于是对长度更长的序列二进行拆分，而后求出first_cut和second_cut如下图所示。

然后针对，[first,middle),[middle, second_cut)图中的{7,2,4},执行以下旋转操作。

BidrectionalIterator new_middle = __rotate_adative(first_cut, middle, second_cut, len1 - len11, len22, buffer, buffer_size);

这个__rotate_adative函数的功效和STL 算法rotate并没有什么不同，只是它针对缓冲区的存在做了优化。万一缓冲区不足，最终还是交给STL算法rotate去执行。代码如下：

template<BidrectionalIterator1, class BIdrectionalIterator2, class Distance>
BidrectionalIterator1 __rotate_adaptive(BidrectionalIterator1 first,BidrectionalIterator1 middle,BidrectionalIterator1 last,Distance len1, Distance len2,BidrectionalIterator2 buffer, Distance buffer_size) {BidrectionalIterator2 buffer_end;if (len1 > len2 && len2 <= buffer_size) {buffer_end = copy(middle, last, buffer);copy_backward(first, middle, last);return copy(buffer, buffer_end, first);} else (len1 <= buffer_size) {buffer_end = copy(first, middle, buffer);copy(middle, last, first);return copy_backward(buffer, buffer_end, last);} else {rotate(first, middle, last);advance(first, len2);return first;}   
}

经过这样的处理，原序列现在变成了：

经过旋转后，不难发现，[first, new_middle)内的所有元素的值都是<= *second_cut,[new_middle, last)的所有元素的值都是>=*second_cut的；所以，后面可以针对左半段{first, first_cut, new_middle}和右半段{new_middle, second_cut, last}分别执行__merge_adaptive，可以达到整个区间实现merge的效果。

针对新的左右两个字段，左半段只需要buffer_size>=2,即可完成merge，右子半段只需要buffer_size>=1则可完成合并。

其合并过程如下：

至此完成了inplace_merge的大体介绍；

merge sort

虽然SGI STL所采用的排序法是IntroSort（STL算法之sort-CSDN博客），不过，另一个很有名的排序算法Merge Sort，很轻易就可以利用STL 算法inplace_merge实现出来。

Merge Sort的概念是这样的：既然我们知道，将两个有序区间归并成一个有序区间，效果不错，那么我们可以利用“分而治之”的概念，以各个击破的方式对一个区间进行排序。首先，将区间对半分割，左右两段各自排序，再利用inplace_merge重新组合为一个完整的有序序列。对半分割的操作可以递归进行，直到每一小段长度为0或1。下面是实现代码：

template <class BidrectionalIterator>
void mergesort(BidrectionalIterator first, BidrectionalIterator last) {typename iterator_traits<BidrectionalIterator>::difference_type n = distance(first, last);if (n == 0 || n == 1) return;else {// 此处代码，与书中mid = first + n/2有差异；【书中的写法在传入BidrectionalIterator后会导致编译错误】BidrectionalIterator mid = first;advance(mid, n/2);mergesort(first, mid);mergesort(mid, last);inplace_merge(first, mid, last);}
}

Merge Sort时间复杂度为 $O(N logN)$ 。虽然这和Quick Sort是一样的，但因为Merge Sort需额外借用内存，而且再内存之间移动(复制)数据也会耗费不少时间，所以Merge Sort的效率比不上Quick Sort。实现简单、概念简单，是Merge Sort的两大优点。

Merge Sort还有一个优点是，MergeSort接受的指针是BidrectionIterator，所以MergeSort是可以针对list的迭代器进行处理的。

测试代码如下：

#include <algorithm>
#include <list>
#include <iostream>
using namespace std;template <class BidrectionalIterator>
void mergesort(BidrectionalIterator first, BidrectionalIterator last) {typename iterator_traits<BidrectionalIterator>::difference_type n = distance(first, last);if (n == 0 || n == 1) return;else {BidrectionalIterator mid = first;advance(mid, n/2);mergesort(first, mid);mergesort(mid, last);inplace_merge(first, mid, last);}   
}template<class T>
struct display{
void operator() (const T&x){cout << x << " ";
}
};int main() {int ia[] = {1 , 5, 3, 4, 9,6};list<int> iv(ia, ia + 6);for_each(iv.begin(), iv.end(), display<int>());cout << endl;mergesort(iv.begin(), iv.end());for_each(iv.begin(), iv.end(), display<int>());cout << endl;// 下面这条语句会编译报错// sort(iv.begin(), iv.end());return 0;
}

ps：经实测，在STL中未找到mergesort的定义；需要使用mergesort时，可以直接将上述代码定义后直接使用。

参考文档《STL源码剖析》---侯捷

查看全文

http://www.mrgr.cn/news/79231.html