【STL】算法 — partial_sort
算法 STL Sort partial
2023-09-14 09:07:57 时间
partial_sort接受一个middle迭代器,使序列中的middle-first个最小元素以递增顺序排序。置于[first, middle)内。以下是測试代码:
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int a[] = {10,9,8,7,6,5,4,3,2,1,0}; vector<int> vec(a, a+11); vector<int>::iterator b = vec.begin(); vector<int>::iterator e = vec.end(); partial_sort(b, b+6, e); // 前6个最小元素排序 while (b != e) cout << *(b++) << ' '; return 0; }
执行结果:
从结果能够看出,前6个最小元素放在了前6个位置上,而剩下的元素则放于容器后面未排序。
实现partial_sort的思想是:对原始容器内区间为[first, middle)的元素运行make_heap()操作构造一个最大堆。然后拿[middle, last)中的每一个元素和first进行比較,first内的元素为堆内的最大值。假设小于该最大值,则互换元素位置,并对[first, middle)内的元素进行调整。使其保持最大堆序。
比較完之后在对[first, middle)内的元素做一次对排序sort_heap()操作。使其按增序排列。注意。堆序和增序是不同的。
以下分析STL的源代码。partial_sort有两个版本号,一个默认以小于作为比較规则,出来的顺序为递增排列。
还有一个能够传入一个仿函数。即自己定义比較规则。这里仅仅分析前者。
template <class RandomAccessIterator> inline void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) { __partial_sort(first, middle, last, value_type(first)); }
进入__partial_sort函数:
template <class RandomAccessIterator, class T> void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, T*) { make_heap(first, middle); // [first, middle)区间构造一个heap for (RandomAccessIterator i = middle; i < last; ++i) if (*i < *first) // 当前元素比堆中最大的元素小 __pop_heap(first, middle, i, T(*i), distance_type(first)); // first值放i中,i的原值融入heap并调整 sort_heap(first, middle); }
此函数和上面的文字描写叙述基本同样。有一点小的差别在于当*i < *first时,代码中没有互换i所指元素和first所指元素。究竟怎么做的?来看看__pop_heap函数:
template <class RandomAccessIterator, class T, class Distance> inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator result, T value, Distance*) { *result = *first; // 弹出元素放vector尾端 __adjust_heap(first, Distance(0), Distance(last - first), value); }
此函数把first中的元素放在了result,也就是i位置上。成功地把最大值挤出了[first, middle)区间。
但此时first位置形成了一个空洞。即索引值Distance(0)。所以须要调整heap,这由__adjust_heap函数负责。调整大致过程是找出最大元素放入first,然后把value保存的值插入到堆的适当位置,在这里value即为T(*i),即把i所指元素融入到了[first, middle)区间。
由此可见,__adjust_heap的复用性还是非常高的。
再回到__partial_sort函数。for循环就是反复上面的“挤出”和“融入”操作直到容器末尾。
当跳出for循环时,区间[first, middle)中已经存放有容器的前middle-first个最小元素了。最后运行sort_heap(),由堆序变为增序排列:
template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last) { while (last - first > 1) pop_heap(first, last--); }
弹出堆的最大值并放入尾部,然后缩小堆的范围。循环运行弹出操作直至堆仅仅剩下最后一个元素。
这样就能够达到排序效果了。注意。此函数仅仅能用于堆上。
若要对整个普通容器施行堆排序操作。能够借partial_sort接口。仅仅需把middle參数改为last就可以:
partial_sort(first, last, last);
这样的方法用到了STL的高速排序身上,感觉越来越有意思了。
个人认为这个局部排序还是蛮重要的,至少是它的排序思想非常好,要不然STL也不会使用它了。
參考:
《STL源代码剖析》 P386.
相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- 深入浅出PID控制算法(一)————连续控制系统的PID算法及MATLAB仿真[通俗易懂]
- 支持向量回归(SVR)的详细介绍以及推导算法
- 匈牙利算法(Kuhn-Munkres)算法[通俗易懂]
- 高精度快速阶乘算法
- [Unity算法]斜抛运动[通俗易懂]
- 前端工程师leetcode算法面试必备-二分搜索算法(中)
- A星算法说明「建议收藏」
- a星算法c++实现_递归算法理解
- 数据结构:文件管理,算法
- 负载均衡算法
- 使用ChatGPT生成了十种排序算法
- STL算法详解
- c++ set_difference(STL set_difference)算法详解
- C++ includes(STL includes)算法详解
- C++ sort(STL sort)排序算法详解
- C++ partial_sort(STL partial_sort)排序算法详解
- C++ is_sorted(STL is_sorted)排序算法详解
- C++ find(STL find)查找算法详解
- C++ find_if_not(STL find_if_not)查找算法详解
- C++ find_first_of(STL find_first_of)查找算法详解
- C++ partition_copy(STL partition_copy)算法使用详解
- C++ lower_bound(STL lower_bound)二分查找算法详解
- 深入浅出:Redis 集群算法(redis集群算法)
- 下的应用STL在Linux下的应用:利用精彩技术推动发展(stl在linux)
- STL和Redis加速程序效率的提升(stl与redis效率)