寫了個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 閱讀(7159)
評論(32) 編輯 收藏 引用 所屬分類:
Numerical C++