简述
归并排序思想，假设对数组A[p...r]排序：
- 分解
- 将数组A[p...r]平均划分为2子数组A[p...q-1]个A[q...r]，一直划分直到每个子数组只有1个元素
- 归并
- 对 A[p...q-1]和A[q...r]这两个已排序好的数组进行合并
复杂度
- 时间复杂度
O(nlgn) - 非原地排序，归并时需要额外的空间
O(n)
实现
- begin
- begin...middle之间为已排好序列
- end
- middle...end之间为已排好序列
- middle
- begin...middle之间为已排好序列
- compare
- 一个可调用对象，可用于比较两个对象的小于比较，默认为std::less
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
template<typename Iterator,typename CompareType=std::less<typename std::iterator_traits<Iterator>::value_type>> void merge(const Iterator begin,const Iterator end,const Iterator middle,CompareType compare=CompareType()) { typedef typename std::iterator_traits<Iterator>::value_type T;//迭代器指向对象的值类型 if (std::distance(begin,end) <= 0 || std::distance(middle,end) <= 0) return; std::vector<T> result(begin,end);//暂存结果 auto current = result.begin(); auto left_current = begin;//左侧序列当前比较位置 auto right_current = middle;//右侧序列当前比较位置 while(left_current != middle && right_current != end) { if(compare(*left_current,*right_current)) *current++ = *left_current++;//左侧较小 else *current++ = *right_current++;//右侧较小 } if (left_current == middle && right_current != end)//当左侧序列为空时 std::copy(right_current,end,current); if (right_current == end && left_current != middle) std::copy(left_current,middle,current); std::copy(result.begin(),result.end(),begin);//复制回原序列 } |
- begin
- 待排序序列的起始迭代器（也可以是指向数组中某元素的指针）
- end
- 待排序序列的终止迭代器（也可以是指向数组中某元素的指针）
- compare
- 一个可调用对象，可用于比较两个对象的小于比较，默认为std::less
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
template<typename Iterator,typename CompareType=std::less<typename std::iterator_traits<Iterator>::value_type>> void merge_sort(const Iterator begin,const Iterator end,CompareType compare=CompareType()) { // 迭代器指向对象的值类型 //typedef typename std::iterator_traits<Iterator>::value_type T; auto size = std::distance(begin,end); if (size > 1) { Iterator middle = begin + size/2; merge_sort(begin,middle,compare); merge_sort(middle,end,compare); merge(begin,end,middle,compare); } } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 查找_顺序查找05/09
- ♥ 动态规划_最长公共子序列09/05
- ♥ 排序_基数排序09/04
- ♥ 贪心算法06/29
- ♥ 匹配_KMP模式匹配算法：一11/02
- ♥ BFS和DFS06/29
热评文章
- 排序_快速排序 0
- 动态规划相关 0
- 数据结构_最小优先级队列 0
- 排序_冒泡排序 0
- 一些变量值交换的方法 0
- 匹配_KMP模式匹配算法：二 0