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)，代码实现如下。

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），递归即可。

模拟实现：

下面是自己实现的代码：

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

源码剖析：

代码为:

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

其实，归根结底，就以下几点：

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

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

序是很好的选择。