posts - 12,  comments - 54,  trackbacks - 0
写了个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-173 ) << 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 阅读(6972) 评论(32)  编辑 收藏 引用 所属分类: Numerical C++

FeedBack:
# re: nth_element ---- 比较优美的代码[未登录]
2008-11-06 17:38 | Kevin
有点小意见
个人不太喜欢得地方就加空格,例如:if ( a == b ) return;
不过LZ在运算符前后又省掉了空格,例如:arr+size

比较喜欢这样写:
if (a == b) a = a + b;

每个人写代码的习惯不同,所以LZ别介意啊  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-06 17:50 | Wang Feng
copy( arr, arr+size, ostream_iterator<int>( cout, " " ) );
我觉得这样写,看起来容易一点
因为逗号运算符优先级最低,于是arr+size中的加号在逗号之前;
我的习惯是先运行的更紧密一些;
如你比较喜欢的这个
if (a == b) a = a + b;
我会写成
if (a == b) a = a+b;
或者
if (a == b)
{
a = a+b;
}
或者
if (a == b)
++a;
或者
if (a == b)
{
++a;
}
  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-06 18:10 | 空明流转
如果不需要处理异常,不需要用户提示,不需要安全机制,不需要照顾性能,
那么,
所有的代码都可以很优美。  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-06 18:11 | fish_autumn
效率有待提高  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-06 18:12 | Wang Feng
@空明流转
@fish_autumn
请求指点  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-06 20:05 | cdy20
换位 很漂亮

这样就行了
a^=b^=a^=b;  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-06 20:55 | Wang Feng
@cdy20
这样写的话,用g++编译后交换失败;
用icpc编译后交换成功,非常奇怪
可有人给出更多测试?
我的编译器:
$ g++ -v
Using built-in specs.
Target: x86_64-unknown-linux-gnu
Configured with: ../configure --prefix=/usr --enable-shared --enable-languages=c,c++,fortran,objc,obj-c++,treelang --enable-threads=posix --mandir=/usr/share/man --infodir=/usr/share/info --enable-__cxa_atexit --disable-multilib --libdir=/usr/lib --libexecdir=/usr/lib --enable-clocale=gnu --disable-libstdcxx-pch --with-tune=generic
Thread model: posix
gcc version 4.3.2 (GCC)
$ icpc -v
Version 10.1
  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-07 10:50 | zuhd
能说说这个函数的作用吗?
int partation( int* arr, int low, int high )
没看明白  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-07 13:50 | Wang Feng
@zuhd
你可以这样理解:
1) 找到一个arbitrary value A(这个数值应该是任意的,我图写起来利落,直接指定为数组的最后一个元素----比较好的做法是,执行之前,在数组中任意寻找一个元素与数组最后一个元素交换)
2)一个指针指向数组的第一个元素,往向后扫描,找到第一个大于A的元素,标记为arr[a];
3)另外一个指针指向数组的最后一个元素,向前扫面,找到第一个小于A的元素arr[b];
4)交换arr[a] arr[b]
5)若两个指针没有重合,转到2)
6)将A与两个指针重合地点的元素交换
这样以来,以A为界,把数组分为两个部分,前边部分数值都是不大于A的,后边的部分的数值都是不小于A的  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-08 18:17 | 雷长炎
这就是堆排序的实现了,一趟排序而已。要完整实现堆排序,需要反复调用该函数了。  回复  更多评论
  
# re: nth_element ---- 比较优美的代码[未登录]
2008-11-09 20:58 | cepvoggg
void swap( int& a, int& b )
2 {
3 if ( a == b ) return;
4 a ^= b;
5 b ^= a;
6 a ^= b;
7 }
这个代码是你自己写的吗,这个好像是错的噢
  回复  更多评论
  
# re: nth_element ---- 比较优美的代码[未登录]
2008-11-09 21:02 | cepvoggg
在C语言编程专家里面有说过这个代码是错的  回复  更多评论
  
# re: nth_element ---- 比较优美的代码[未登录]
2008-11-09 21:31 | feng
@cepvoggg
是我自己写的;
敢问错在哪里?
我手里没有C语言编程专家这本书,你说的是不是C expert programming?  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-10 09:41 | zuhd
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 }
==========================================
觉得你上面这段代码好奇怪啊,这个函数的目的是“找到第一个比最后一个数大的数"吗?如果是这样,我觉得没有必要这么写,我想功能可能不只是这些  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-10 13:11 | Wang Feng
@zuhd
不是,这段代码目的是:以A为界,把数组分为两个部分,前边部分数值都是不大于A的,后边的部分的数值都是不小于A的  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-11 09:55 | zuhd
@Wang Feng
我有个疑问,就是如果仅满足“以ans为界,把数组分为两个部分,前边部分数值都是不大于arr[ans]的,后边的部分的数值都是不小于arr[ans]的”,程序的运行结果可以有很多种啊,你的给出的结果的依据是什么呢?  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-11 15:34 | 天策魂之音
@cepvoggg
请问这个错在哪里?

有没考虑到的状况还是?  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-11 15:38 | Wang Feng
@zuhd
"程序的运行结果可以有很多种啊"里边的程序是指 partation还是nth?  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-11 15:39 | Wang Feng
@天策魂之音
我用随机数测试过42忆次,没有出错过;
不知道错误是什么  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-12 09:35 | zuhd
@Wang Feng
我说的是partation这个函数,如果要求程序输出“以ans为界,把数组分为两个部分,前边部分数值都是不大于arr[ans]的,后边的部分的数值都是不小于arr[ans]的”,那么结果不是唯一的  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-12 21:22 | Wang Feng
@zuhd
如果arr已经给定不可更改,那么这个结果就是唯一的  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-13 09:47 | zuhd
比如:
输入:3,5,7,4,0,1
我可以得到这样的数组3,4,0,1,5,7返回4,即在第4个位子的‘5’把数组分为两部分。同时我也可以返回3,0,1,4,5,7返回3,即在第3个位子的‘4’把数组分为这样的两部分。等等
这样的返回值都能满足你的需求啊  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-13 14:56 | Wang Feng
@zuhd
3,5,7,4,0,1
第一次调用partation(arr, 0, 5)是以1为界分的;
结果数组被排成
0 1 7 4 3 5
返回1  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-14 13:05 | zwp
人各有好,不打击楼主对代码形式的追求。
但就从实际角度来说,好的设计就会带来赏心悦目的代码。  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2008-11-14 16:13 | 阿尔法
楼主的最后一行代码明显错了:
return
28 ( mid < index ) ?
29 nth(arr, mid+1, high, index) : 应该index改为index-mid吧
30 nth(arr, low, mid-1, index);
  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2009-01-07 01:23 | guest
这样递归的话,如果原数组有正序,不用很长,比如1万,是会溢出的!  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2009-01-08 10:42 | Wang Feng
@guest
确实是这样的,要解决的话也不是很困难,只要partation时候把数组random shuffle一下就可以了:)  回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2009-08-15 12:58 | guest
个人认为partition跟快排中的partition实现同样的功能,不过LZ这样写不容易让人看明白。
lZ的应该是从最前面开始找,找到一个比最后一个小的数,则和从0位置开始的数想交换,执行一次后,ans前面是比它小的数后面是比它大的数。

另外效率是在不敢恭维。寻找最大或最小比较次数太多。  回复  更多评论
  
# re: nth_element ---- 比较优美的代码[未登录]
2009-08-15 16:06 | feng
@guest
其实无论从前边还是后边开始寻找,都是可以的
不过重要的是寻找之前把数列打乱一下,以避免在碰到有序数列的时候时间复杂度飙升的尴尬。

我觉得效率上没有什么问题了,绝对是 O(n)。   回复  更多评论
  
# re: nth_element ---- 比较优美的代码
2010-12-31 11:21 | pkuoliver
@feng
很明显,时间复杂度不是O(N),最坏情况下时间复杂度是O(N^2),最好时间复杂度是O(N),平均时间复杂度是O(N*logN)。这是个典型的分治算法。  回复  更多评论
  
# re: nth_element ---- 比较优美的代码[未登录]
2011-04-21 22:58 | feng
是的  回复  更多评论
  
# re: nth_element ---- 比较优美的代码[未登录]
2011-08-13 15:04 | xxx
@雷长炎
是quicksort的一遍实现,不是heapsort。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(4)

随笔分类

随笔档案

Link List

搜索

  •  

最新评论

阅读排行榜

评论排行榜