写了个nth_element的函数，觉得比较pp，就贴上来了 －－ 注意，跟库函数那个有点差别
1 void swap( int& a, int& b )
2 {
3
4 a ^= b;
5 b ^= a;
6 a ^= b;
7 }
8
9 int partation( int* arr, int low, int high )
10 {
11 int ans = low - 1;
12 for ( int i = low; i < high; ++i )
13 {
14 if ( arr[i] < arr[high] )
15 {
16 swap( arr[i], arr[++ans] );
17 }
18 }
19 swap( arr[++ans], arr[high] );
20 return ans;
21 }
22
23 int nth( int* arr, int low, int high, int index )
24 {
25 int mid = partation(arr, low, high);
26 if ( mid == index ) return arr[mid];
27 return
28 ( mid < index ) ?
29 nth(arr, mid+1, high, index) :
30 nth(arr, low, mid-1, index);
31 }
然后呢，在某人的新贴下发现这样的评论：
真要命，就怕碰见上来就贴一大堆代码的。
有比这还可怕的吗？——有！贴一大堆代码还没注释！不管了，反正只是觉得代码漂亮，没有想到要解释什么
一段测试代码如下：
1 #include <iostream>
2 #include <iterator>
3 #include <algorithm>
4 #include <ctime>
5 using namespace std;
6
7 int main()
8 {
9 const int size = 99;
10 int arr[size];
11 for ( int index = 0; index < size; ++index )
12 arr[index] = index;
13
14 srand( time(0) );
15
16 random_shuffle( arr, arr+size );
17
18 copy( arr, arr+size, ostream_iterator<int>( cout, " " ) );
19 cout << endl;
20
21 cout << "the 73th element is " << nth( arr, 0, size-1, 73 ) << endl;
22
23 copy( arr, arr+size, ostream_iterator<int>( cout, " " ) );
24 cout << endl;
25
26 return 0;
27 }
28
由于当序列有序程度很高时候， 这种算法效率比较差，最好在调用之前把目标序列随机打乱一下，也就是上式random_shuffle( arr, arr+size );的由来。
P.S: 感谢
xxgamexx
posted on 2008-11-06 16:47
Wang Feng 阅读(7026)
评论(32) 编辑 收藏 引用 所属分类:
Numerical C++