template <typename _Iterator>
_Iterator find_min(_Iterator begin, _Iterator end)
{
_Iterator min = begin;
for (++begin; begin != end; ++begin) {
if (*begin < *min) {
min = begin;
}
}
return min;
}
在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出
+-------+-----------+-----
| begin | begin + 1 | ...
+-------+-----------+-----
| |
+--( < )--+
/ \
/ \
+----------+ +-------------+ +-----+
| less one | | greater one |--( < )--| max |
+----------+ +-------------+ +-----+
|
| +-----+
+-------------------------( < )--| min |
+-----+
下面是实现的例子
template <typename _Iterator>
std::pair<_Iterator, _Iterator>
_next_pair_min_max(_Iterator min, _Iterator max, _Iterator less, _Iterator greater)
{
if (*less < *min) {
min = less;
}
if (*max < *greater) {
max = greater;
}
return std::make_pair(min, max);
}
template <typename _Iterator>
std::pair<_Iterator, _Iterator>
_find_min_max(_Iterator min, _Iterator max, _Iterator begin, _Iterator end)
{
std::pair<_Iterator, _Iterator> result(min, max);
while (begin != end) {
_Iterator next0 = begin++;
_Iterator next1 = begin++;
if (*next0 < *next1) {
result = _next_pair_min_max(min, max, next0, next1);
} else {
result = _next_pair_min_max(min, max, next1, next0);
}
}
return result;
}
template <typename _RandomAccessIterator>
std::pair<_RandomAccessIterator, _RandomAccessIterator>
find_min_max(_RandomAccessIterator begin, _RandomAccessIterator end)
{
if (std::distance(begin, end) % 2 == 1) {
return _find_min_max(begin, begin, begin + 1, end);
}
return (*begin < *(begin + 1)) ? _find_min_max(begin, begin + 1, begin + 2, end)
: _find_min_max(begin + 1, begin, begin + 2, end);
}
find_min_max 而核心是 _find_min_max, _find_min_max 要求提供初始的 min 和 max, 以及后续迭代的区间. 而找出初始的 min 与 max 迭代器其实是很困难的事情, 如果想要运用到通用情形; 而上述例子中, 从 find_min_max 就可以看出来这并不是什么通用情形, 它要求了一个 STL 中最高级别特化的迭代器类型 random access iterator, 这基本上就宣告了 "除了 vector 别来碰我" (我想实际运用中 deque 这样的容器替代 vector 并不是一个好主意).当然这里有一定故弄玄虚的成分, 实际上需求 random access iterator 是为了
std::distance 能够迅速求得迭代区间的长度, 从而确定元素个数的奇偶性, 确保传递给 _find_min_max 的区间中元素个数一定是偶数个, 同时传递初始的 min 与 max. 任何别的手段只要能提供这些信息, 那么调用 _find_min_max 即可. 但既然有这样的要求, 多多少少会对容器的选择有影响.求最小值, 最大值可以视作两个特化, 那就是, 在一堆元素中找到第 K 小的那个. 一般来说代入 K=1 时, 那么 "在一堆元素中找到第 1 小的那个", 也就是找 "最小" 的那个. 自然语言的表现确实直观, 可是翻译成程序员语, "最小" 其实意味着 K=0, 也就是说如果 N 表示元素个数, 那么 K 的取值范围应该介于 [0, N-1] 这个自然数区间内. 这样的 K 值意义将用于接下来的问题描述和分析.
一个直观的解答方案是, 先找出第 0 小的数, 从集合中排除掉, 接下来是第 1 小的, 如此这般, 直到找到第 K 小的数. 在 K 值较小的时候这不失为一种简单而高效的方法. 当 K 值可能会很大, 或者不确定时, 可以考虑下面的方案.
考虑一个实际情况, 假设现在要在下面这个表 (共 8 个元素) 中找到第 5 小的数
4 9 7 3 8 3 6 1拿出这个序列的开头那个数 4, 将剩下的成两个部分, 一个部分的数全部小于 4, 另一部分全部不小于 4
3 3 1 - 9 7 8 6两个部分中元素的相对排列跟原来容器一致, 或者, 随便怎么排列, 总之不需要排序, 因为排序实在是太耗时了.
较小的那一坨中有 3 个, 那么 4 本身是第 3 小的数 (再说一次, 最小的数是第 0 小的数), 而要找的是第 5 小的数, 因此较小坨和 4 本身都可以直接弃掉, 现在去较大坨找第 (5 - 3 - 1 =) 1 小的数.
与之前类似, 用首个数 9 将序列分开, 结果是
7 8 6 -显然需要找的那个数在现在的较小坨中, 弃掉 (空的) 较大坨和 9, 继续.
6 - 8较小坨中有 1 个数, 因此 7 正是第 1 小的数, 答案产生, 就是 7 自己.
这是个典型的分而治之加上撞大运的算法, 将区间按照是否小于首个数 A 分成三部分 (包括 A 自身一部分), 如果这时 A 恰好是要找的数, 那么撞大运成功返回 A 即可, 否则就看要找的数落在较小那一边还是较大那一边, 然后去递归去找那一边就好了. 下面是实现示例 (为了避免在分元素时产生大量的元素复制操作, 实际存放的是迭代器)
template <typename _Iterator>
_Iterator _find_k_th(std::vector<_Iterator> const& iters, int k)
{
std::vector<_Iterator> lessers;
std::vector<_Iterator> greaters;
typename std::vector<_Iterator>::const_iterator begin = iters.begin();
_Iterator first = *begin;
for (++begin; begin != iters.end(); ++begin) {
if (**begin < *first) {
lessers.push_back(*begin);
} else {
greaters.push_back(*begin);
}
}
if (k == lessers.size()) {
return first;
}
if (k < lessers.size()) {
return _find_k_th(lessers, k);
}
return _find_k_th(greaters, k - lessers.size() - 1);
}
template <typename _Iterator>
_Iterator find_k_th(_Iterator begin, _Iterator end, int k)
{
std::vector<_Iterator> iters;
for (; begin != end; ++begin) {
iters.push_back(begin);
}
return _find_k_th(iters, k);
}
将这个算法做一些推广, 便能得到大名鼎鼎的快速排序了. 在分堆之后, 如果不是去递归找第某小的数, 而是将分开的两堆递归地排个序, 然后将三个部分重新连在一起, 那么就可以得到一个排序过的序列不是么?
template <typename _Iterator>
std::vector<_Iterator> _sort(std::vector<_Iterator> const& iters)
{
if (iters.empty()) {
return std::vector<_Iterator>();
}
std::vector<_Iterator> lessers;
std::vector<_Iterator> greaters;
typename std::vector<_Iterator>::const_iterator begin = iters.begin();
_Iterator first = *begin;
for (++begin; begin != iters.end(); ++begin) {
if (**begin < *first) {
lessers.push_back(*begin);
} else {
greaters.push_back(*begin);
}
}
std::vector<_Iterator> sorted_lessers = _sort(lessers);
std::vector<_Iterator> sorted_greaters = _sort(greaters);
sorted_lessers.push_back(first);
sorted_lessers.insert(sorted_lessers.end(), sorted_greaters.begin(), sorted_greaters.end());
return sorted_lessers;
}
template <typename _Iterator>
std::vector<_Iterator> sort(_Iterator begin, _Iterator end)
{
std::vector<_Iterator> iters;
for (; begin != end; ++begin) {
iters.push_back(begin);
}
return _sort(iters);
}
const 修饰的. 此外 std::sort 要求传入的是 random access iterator.