一个可以并行化的取取数组中第K大元素的算法

一个无序的数组A,长度是N,想要取出其中的第K大的元素.

1. 如果数组长度够小,那么对数组整体排序,取第K个
2. 如果数组长度太长,那么对数组做切分,对切分的每个部分排序,取出这个部分的中间元素.
3. 在中间元素中递归的取中间值,直到取出整个数组A中间值M.
4. 将整个数组A跟据这个中间值M划分为三个部分,大于M的,小于M的,和等于M的.
5. 根据这三个部分的大小来判断第k大的元素在哪个部分,对该部分递归的做上面的操作.

--
caosuwei <caosuwei@gmail.com>