首页 > 代码库 > 【算法】第 n 小数 nth_element

【算法】第 n 小数 nth_element

STL 中取第 n 小数的算法 nth_element 的函数原型如下

template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

算法说明:

1、功能:执行 nth_element 后,nth 所指位置的元素将是整个区间有序时在该处的元素。对 [first, nth) 中的任意迭代器 i 和 [nth, last) 中的任意迭代器 j,满足 !(*i > *j)。

2、要求:RandomAccessIterator 必须满足 ValueSwappable。*first 的类型必须满足 MoveConstructible 和 MoveAssignable。

3、复杂度:平均为线性。

源码如下:

template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) {
	while (last - first > 3) {
		RandomAccessIterator cut = unguarded_partition(first, last, Type(median(
			*first,
			*(first + (last - first) / 2),
			*(last - 1))));
		if (cut <= nth) {
			first = cut;
		} else {
			last = cut;
		}
	}
	insertion_sort(first, last);
}
其中的 unguarded_partition 和 insertion_sort 在之前介绍过,这里不再列出它们的源码。

函数中的 first 和 last 可能改变,当 [first, last) 区间大于3时就一直划分,划分是采用三者取中的方式以缓解输入时的糟糕情况,每次划分后产生两段,若右段起点 cut <= nth,则再对右段划分,否则对左段划分。直到区间长度小于等于3时,索性对这个小区间进行插入排序,注意 nth 始终在 [first, last) 中。