nth_element 算法注解.pdf

nth_element nth_element nntthh__eelleemmeenntt 算法注解 nth_element 是STL 提供的一个算法，用于找出序列中 的第n大元素。这个算法涉及下面4个辅助函数： • _Nth_element • _Unguarded_partition • _Median • _Med3 下面是我对STL 源代码的注释。 /********************************************* ********************************************** * _Nth_element 使序列中第n大的元素位于第n个位子上，使用 比 较元素。 基本思想： (1) 找到一个包含n的足够小的区间[a,b)，使得[a,b) 作为一个大粒度的元素处于序列的有序位置。 (2) 对[a,b)部分进行排序。 nth_element 查找区间的方式体现了二分（折半）查找 的思想。它的核心是 ungarded_partition 算法， ungarded_partition 算法能够找出随机序列的近似的位 置中间值。 ********************************************** ********************************************** */ templateclass _RanItinline void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last) { //orderNthelement,usingoperator _DEBUG_RANGE(_First, _Last); /* 逐步缩小[_First, _Last)的区间，直至尺寸小到可 以直接对局部进行排序。 _ISORT_MAX 是一个阀值，在algorithm中被定 义为32，表示适于插入法排序的序列的最大长度。*/ for(; _ISORT_MAX _Last-_First; ) { // divide andconquer,orderingpartition containing Nth /* 把序列的当前部分划分为有序的三份。*/ pair_RanIt,_RanIt_Mid = _Unguarded_partition(_First, _Last); /* 确定下一步有哪些信誉好的足球投注网站区间。*/ if (_Mid.second=_Nth) _First = _Mid.second; else if (_Mid.first =_Nth) return; //Nthinside fatpivot,done else _Last= _Mid.first; } /* 对[_First, _Last)排序，第n大元素就到了第n个 位置上。*/ _Insertion_sort(_First, _Last); // sort anyremainder } /********************************************* ********************************************** * _Unguarded_partition 把序列划分为有序的三份：[_First, Mid.First), [Mid.First, Mid.Second), [Mid.Second, _Last)，其中 [Mid.First, Mid.Second)内的元素相等。 注意，不是等分： (1) 不保证[Mid.First, Mid.Second)在位置上处于序列 的中间。 (2) 不保证[Mid.First, Mid.Second)在元素值上处于序 列的中间。 (3)[_First, Mid.First)和[Mid.Second, _Last)的长度有可 能为0。 (4) [_First, Mid.First)中的所有元素（若有）小于 [Mid.First, Mid.Second)中的任一元素。[Mid.Second, _Last)中的则大于。 ********************************************** *****