热爱互联网

nth_element

算法用处:
用来从一个无序的数列中找出第 M 个最小的元素,并且找出 前 M 个最小的元素(无序状态)。
当然,如果要 将前 M 个最小的元素排序输出,那么就应该使用 partial_sort(),如果不要求排序后输出,那么用
nth_element()效率会高很多。
时间复杂度计算:
(1) s = 1 + 1/2 + (1/2)^2 + (1/2)^3 + … + (1/2)^n
(2) 2s = 2 + 1 + 1/2 + (1/2)^2 + …. + (1/2)^(n-1)

(2)-(1) –> 2s – s = s = 2 – (1/2)^n
所以时间复杂度为 O( (2-(1/2)^n) * n ) ,约等于 O(2n) ,即 O(n).

这个算法会重新排列 [first,last),使迭代器 nth 所指的元素,与“整个[first,last)完整排序后,同一位置的元素”同值。此外并保证
[nth,last)内的元素 大于等于 *nth, [first,nth)内的元素小于等于 *nth.
但对于[first,nth)和[nth,last)两个子区间内的元素次序则无任何保证 —- 这一点也是它与 partial_sort 很大的不同处。以此观之,
nth_element 比较近似 partition 而非 sort 或 partial_sort 。

由于 nth_element 比 partial_sort 的保证更少(是的,它不保证两个子序列的任何次序),所以它当然应该比 partial_sort 较快。

nth_element 有两个版本,其差异在于如何定义某个元素小于另一个元素,第一个版本使用 operator< (也就是 less-than) 操作符进行比较,第二个版本使用仿函数(函数对象)进行比较。注意: 这个算法只接受 RandomAccessIterator 。
nth_element 的做法是,不断地以 median-of-3 partitioning(以首,尾,中央三点中值为枢轴之分割法,见sort函数源码)将整个序列分割为更小的左(L),右(R)子序列。如果 nth 迭代器落于左子序列,就再对左子序列进行分割,否则就再对右子序列进行分割。以此类推,直到分割后的子序列长度不大于3(够小了),便对最后这个待分割的子序列做 Insertion Sort,大功告成。

关于 nth_element()的用法的一个实例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<iterator>
#include<functional>
using namespace std;
int main(){
    int a[]={5,6,4,8,7,9,1,2,4,6,7,9,8};
    vector<int>v(a,a+sizeof(a)/sizeof(int));
 
    nth_element(v.begin(),v.begin()+5,v.end());
 
    cout<<*(v.begin()+5)<<endl; //输出 v 中 第 6 个 最小的元素
 
    copy(v.begin(),v.begin()+6,ostream_iterator<int>(cout," ")); //输出 v 中 前6个最小的元素,不保证任何次序
    cout<<endl;
 
    copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //输出 v 中所有的元素
    cout<<endl;
 
    nth_element(a,a+5,a+sizeof(a)/sizeof(int),greater<int>());
 
    cout<<*(a+5)<<endl; // 输出 a 中第 6 个最大 的元素
 
    copy(a,a+6,ostream_iterator<int>(cout," ")); //输出 a 中前 6 个最大的元素,不保证任何次序
    cout<<endl;
 
    copy(a,a+sizeof(a)/sizeof(int),ostream_iterator<int>(cout," ")); //输出 a 中所有的元素
    cout<<endl;
 
 
    system("pause");
    return 0;
}

下面是 nth_element的源代码,只写出第一个版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename RandomAccessIterator>
inline void nth_element(RandomAccessIterator first,
                        RandomAccessIterator nth,
                        RandomAccessIterator last){
       _nth_element(first,nth,last,value_type(first));
 
}
 
//版本一辅助函数
template<typename RandomAccessIterator,typename T>
void _nth_element(RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last, T*){
     while(last - first > 3){ //长度超过3
          //采用meidian-of-3 partitioning.参数:(first,last,pivot), pivot为枢轴
          //返回一个迭代器,指向分割后的右段第一个元素
          RandomAccessIterator cut = _unguarded_partition(first,last,T(_median(*first,*(first + (last-first)/2),*(last-1))));
          if(cut <= nth) //如果右段起点 <= 指定位置(nth落于右段)
              first = cut; //再对右段实施分割(partitioning)
          else   //否则 (nth 落于左段)
              last = cut;  //对左段实施分割(partioning)
     }
     _insertion_sort(first,last);
}

_median()的源码如下:
//返回 a,b,c之居中者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename T>
inline const T& _median(const  T& a,const T& b,const T& c){
       if(a<b){
           if(b<c) // a < b < c
              return b;
           else if(a<c) // a < b, b >= c, a < c
               return c;
           else
               return a;
       }
       else if(a<c) // c > a >= b
           return a;
       else if(b<c) // a >= b, a >=c, b <c
           return c;
       else
           return b;
}

_unguarded_partition()源码如下:
//返回值是为分割后的右段第一个位置(枢轴)

1
2
3
4
5
6
7
8
9
10
11
12
template<typename RandomAccessIterator,typename T>
RandomAccessIterator _unguarded_partition(RandomAccessIterator first,RandomAccessIterator last,T pivot){
                     while(true){
                          while(*first < pivot) ++first; //first 找到 >= pivot 的元素就停下来
                          --last;  //调整
                          while(pivot < *last) --last; //last 找到 <= pivot 的元素就停下来
                          //注意,以下 first < last 判断操作,只适合于 random iterator
                          if( !(first < last) ) return first; //交错,结束循环
                          iter_swap(first,last); //大小值交换
                          ++first; //调整
                     }
}

Insertion Sort 源码如下,由于 STL 规格并不开放 Insertion Sort,所以 SGI 将以下函数的名称都加上双下划线,表示内部使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//版本一
template<typename RandomAccessIterator>
void _insertion_sort(RandomAccessIterator first,RandomAccessIterator last){
     if(first == last) return ;
     for( RandomAccessIterator i = first+1; i != last; ++i) //外循环
         _linear_insert(first,i,value_type(first));
         //以上,[first,i)形成一个子区间
}
//版本一辅助函数
template<typename RandomAccessIterator,typename T>
inline void _linear_insert(RandomAccessIterator first,RandomAccessIterator last,T*){
       T value = *last; //记录尾元素
       if( value < *first ){ //尾比头还小(注意,头端必为最小元素)
           copy_backward(first,last,last+1); //将整个区间向右递移一个位置
           *first = value; // 令头元素等于原先的尾元素值
       }
       else //尾不小于头
           _unguarded_linear_insert(last,value);
}
//版本一辅助函数
template<typename RandomAccessIterator,typename T>
void _unguarded_linear_insert(RandomAccessIterator last,T value){
     RandomAccessIterator next = last;
     --next;
     //insertion sort的内循环
     //注意,一旦不再出现逆转对(inversion),循环就可以结束了
     while(value < *next){
         *last = *next;
         last = next;
         --next;
     }
     *last = value; //value的正确落脚处
}

简单实现 nth_element()函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<iostream>
#include<string>
#include<vector>
#include<iterator>
#include<functional>
using namespace std;
 
// _median(),返回 a,b,c之居中者
/******************************************************/
template<typename T>
inline const T& _median(const  T& a,const T& b,const T& c){
	   if(a<b){
		   if(b<c) // a < b < c
			  return b;
		   else if(a<c) // a < b, b >= c, a < c
			   return c;
		   else
			   return a;
	   }
	   else if(a<c) // c > a >= b
		   return a;
	   else if(b<c) // a >= b, a >=c, b <c
		   return c;
	   else
		   return b;
}
/*********************************************************/
// _unguarded_partition(),返回值是为分割后的右段第一个位置(枢轴)
template<typename RandomAccessIterator,typename T>
RandomAccessIterator _unguarded_partition(RandomAccessIterator first,RandomAccessIterator last,T pivot){
					 while(true){
						  while(*first < pivot) ++first; //first 找到 >= pivot 的元素就停下来
						  --last;  //调整
						  while(pivot < *last) --last; //last 找到 <= pivot 的元素就停下来
						  //注意,以下 first < last 判断操作,只适合于 random iterator
						  if( !(first < last) ) return first; //交错,结束循环
						  iter_swap(first,last); //大小值交换
						  ++first; //调整
					 }
}
 
// Insertion Sort函数如下:
/*************************************************/
//版本一辅助函数
template<typename RandomAccessIterator,typename T>
void _unguarded_linear_insert(RandomAccessIterator last,T value){
	 RandomAccessIterator next = last;
	 --next;
	 //insertion sort的内循环
	 //注意,一旦不再出现逆转对(inversion),循环就可以结束了
	 while(value < *next){
		 *last = *next;
		 last = next;
		 --next;
	 }
	 *last = value; //value的正确落脚处
}
//版本一辅助函数
template<typename RandomAccessIterator>
inline void _linear_insert(RandomAccessIterator first,RandomAccessIterator last){
       /************************ 类型榨取 *********************/
	   typename iterator_traits<randomAccessIterator>::value_type value= *last; //记录尾元素
	   if( value < *first ){ //尾比头还小(注意,头端必为最小元素)
		   copy_backward(first,last,last+1); //将整个区间向右递移一个位置
		   *first = value; // 令头元素等于原先的尾元素值
	   }
	   else //尾不小于头
		   _unguarded_linear_insert(last,value);
}
//Insertion Sort 版本一
template<typename RandomAccessIterator>
void _insertion_sort(RandomAccessIterator first,RandomAccessIterator last){
	 if(first == last) return ;
	 for( RandomAccessIterator i = first+1; i != last; ++i) //外循环
		 _linear_insert(first,i);
		 //以上,[first,i)形成一个子区间
}
/**********************************************************************/
// nth_element 版本一辅助函数
template<typename RandomAccessIterator>
void _nth_element(RandomAccessIterator first,
				  RandomAccessIterator nth,
				  RandomAccessIterator last){
	 while(last - first > 3){ //长度超过3
		  //采用meidian-of-3 partitioning.参数:(first,last,pivot), pivot为枢轴
		  //返回一个迭代器,指向分割后的右段第一个元素
		  RandomAccessIterator cut = _unguarded_partition(first,last,_median(*first,*(first + (last-first)/2),*(last-1)));
		  if(cut <= nth) //如果右段起点 <= 指定位置(nth落于右段)
			  first = cut; //再对右段实施分割(partitioning)
		  else   //否则 (nth 落于左段)
			  last = cut;  //对左段实施分割(partioning)
	 }
	 _insertion_sort(first,last);
}
// nth_element 函数
template<typename RandomAccessIterator>
inline void my_nth_element(RandomAccessIterator first,
						RandomAccessIterator nth,
						RandomAccessIterator last){
	   _nth_element(first,nth,last);
 
}
/*********************************************************/
int main(){
	int a[]={5,6,4,8,7,9,1,2,4,6,7,9,8};
	vector<int>v(a,a+sizeof(a)/sizeof(int));
 
	my_nth_element(v.begin(),v.begin()+5,v.end());
 
	cout<<*(v.begin()+5)<<endl; //输出 v 中 第5个 最小的元素
 
	copy(v.begin(),v.begin()+5,ostream_iterator<int>(cout," ")); //输出 v 中 前5个最小的元素,不保证任何次序
	cout<<endl;
 
	copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //输出 v 中所有的元素
	cout<<endl;
 
	my_nth_element(a,a+5,a+sizeof(a)/sizeof(int));
 
	cout<<*(a+5)<<endl; // 输出 a 中第 5 个最小 的元素
 
	copy(a,a+5,ostream_iterator<int>(cout," ")); //输出 a 中前 5个最小的元素,不保证任何次序
	cout<<endl;
 
	copy(a,a+sizeof(a)/sizeof(int),ostream_iterator<int>(cout," ")); //输出 a 中所有的元素
	cout<<endl;
 
 
	system("pause");
	return 0;
}

One Comment

  • Posted 01/08/2019 at 15:58 | Permalink

    I have noticed you don’t monetize lijieblog.com, don’t waste
    your traffic, you can earn additional cash every month with new monetization method.
    This is the best adsense alternative for any type of website (they approve all websites), for more info simply
    search in gooogle: murgrabia’s tools

Post a Comment

Your email is kept private. Required fields are marked *