首页 > 代码库 > 标准库 之 nth_element

标准库 之 nth_element

STL库中实现了nth_element函数,实现的功能是 “返回n个元素中的第k小的元素”。


首先,头脑风暴一下“返回n个元素中的第k小的元素”的算法:


1    排序 ,首选快排  O(n*logn),取出第k个即可。

2其次,是维护一个大小为k的数组,找出数组中的最大值kmax,然后依次遍历剩下的 n-k 个元素,如果小雨kmax,则替换掉kmax

元素,然后再找出其中的最大值,重复上述过程,时间复杂度为 O(n*k)。

3对2的改进,使用大小为k个大顶堆,时间复杂度为 O(n*logk),代码实现如下。

<script src="https://code.csdn.net/snippets/337766.js" type="text/javascript"></script>

上述函数实现的是返回前k小的元素。


4便是此处要提到的STL库中的nth_element函数的实现了。

原理:

在STL库中,nth_element的实现是基于快速排序的partition的过程。

0)分两种,第一,如果处理的元素的个数小于某一个阈值(此处为3)。那么使用插入排序,否则,转1)

1)选出pivot,使用的是first,last,以及中间元素的中间值,(其实,在快速排序中,这样选择pivot可能导致最坏时间复杂度的

概率已经是可以忽略不计了),根据该pivot的值将数组进行划分,得到A[ first ,.... ,cut] , 与 A[cut  ... last]

2) 如果小于pivot的元素个数已经是K,直接返回。

3) 如果小于pivot的元素小于K,那么在 大于pivot的部分寻找第K - ( cut - first +1 ) 大的元素。转入1),递归即可。

4) 如果小于pivot的元素大于K,那么在 小于pivot的部分继续寻找第 K大 的 元素。转入1),转入1),递归即可。


模拟实现:

下面是自己实现的代码:


<script src="https://code.csdn.net/snippets/337809.js" type="text/javascript"></script>


上述函数只想完成之后,返回的数组的前K个元素就是最小的K个元素,并且第K小的元素在其位置上。


源码剖析:

代码为:

<script src="https://code.csdn.net/snippets/337823.js" type="text/javascript"></script>

上述的STL库中的代码,显得很繁琐,其实主要是都是模板函数。原理其实很简单。


其实,归根结底,就以下几点:

如果元素个数比较多的时候,那么利用快排的partition的思想,就可以将问题的规模降低。

如果元素个数比较少的时候,那么直接使用插入排序,是很好的选择, 在数组元素个数比较少或者是数字基本有序的时候,插入排

序是很好的选择。