不如先看一个简单的问题 荷兰国旗问题 Google Search Result
话从此处说起，学到了一个一直遗漏的简单算法叫quickselect
然后试着用一下呗：
int main() {
int a[]={6,1,2,6,7,8,6};
nth_element(a,a+3,a+7);
for (int i=0;i<sizeof(a)/sizeof(int);i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}系统MacOS X 10.12
版本1: Clang++
1 2 6 6 6 7 8
版本2: gnu cpp v7
2 1 6 6 7 8 6
函数返回第k大的数，并且保证第k位之前的数都比他小，k位之后的数都比他大。关键在处理相等上面，样例中所求位a+3 = 6
虽然说上面版本1版本2都达到了要求“第4大的数在第4个位置上，为6”
上文中有三个6，那么这三个6必须放在一起吗？
顺便学习一下这个算法:wiki上面说使用The_median_of_medians可以时间最坏控制在O(n)
来解密
看代码，gnu的stdlibc++ stl_algo.h line4750 -> line4765
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
_RandomAccessIterator __last, _Size __depth_limit,
_Compare __comp)
{
while (__last - __first > 3)
{
if (__depth_limit == 0)
{
std::__heap_select(__first, __nth + 1, __last, __comp);
// Place the nth largest element in its final position.
std::iter_swap(__first, __nth);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
if (__cut <= __nth)
__first = __cut;
else
__last = __cut;
}
std::__insertion_sort(__first, __last, __comp);
}
/// This is a helper function...
template<typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_RandomAccessIterator __pivot, _Compare __comp)
{
while (true)
{
while (__comp(__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, __last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
以上发现gnu cpp的quickselect显然对于文章开头的例子，不能保证666在一起（在中间）出现，下面看clang++的库
有点长。。不贴了，点链接搜索nth_element
http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm
这个就可以让666在一块儿
接下来
下面就说自己写怎么保证上文提到的3个6能在一起，网上没有提到太多啊。。
这样可以实现有重复数字的quickselect。。。。。并且能把'kth-number'都放一起。function unguarded_partition()可以参考文章开头的那个荷兰国旗问题。
/*
* first 和 last 变量均为数组下标
* 而baseNum是一个在array[first->last]这一段中，取的一个数。
*/
int unguarded_partition(int first, int last, int baseNum) {
int leftsave=first,rightsave=last;
int searchpos=first;//标明处理到了哪一位
while (searchpos<=rightsave) { //在first到last之间还有没找的position
if (array[searchpos] < baseNum)
swap(array[leftsave++],array[searchpos++]);//比他小的放前面
else if (array[searchpos] > baseNum)
swap(array[rightsave--],array[searchpos]);//比他大的往后甩
else
searchpos++;//相等的，跳过，继续处理下一个。
}
//最后换来换去，就把和fnum相等的数字换到array中间了。
//Update:错误写法 return leftsave+1 or rightsave-1 or searchpos
//更正一下，最后结束时候，和baseNum相同的会聚集在中间，我们可以酌情返回
//leftsave=和fnum相同的第一个位置
//rightsave=和fnum相同的最后一个位置
return rightsave;
}
/* 随机找一个数，注意，如果要保证最坏复杂度Theta(n)，需要在此使用The_median_of_medians方法！ */
int find_a_number_from_array(int left, int right) {
return array[ rand()%(right-left)+left ];
}
void nth_element(int[] array, int kth) {
//left是第一个
//right是最后一个, 不是iterator.end()
int left=0, right=array.size()-1;
while (left<right) {
baseNumber = find_a_number_from_array(left,right);//随机找一个数做compare base line.
//这个函数确保cut_position左边的肯定小，右边肯定大，但左右两侧无序。
cut_position = unguarded_partition(first, last, baseNumber);
if (cut_position == kth)
return cut_position; // finish.
if (cut_position < kth)
left = cut_position+1;
else {
//由于存在相等的元素，我们返回的是相等元素的末尾，因此这有可能已经是答案了。
right = cut_position-1;
}
}
}