平时用惯了全排序np.sort
,复杂度在到之间。如果待排序的数组特别大的话,时间开销不小。但通常特别大的数组排序不需要进行全排,可能仅仅需要取Top K。此时就可以使用部分排序,比如numpy.partition
和numpy.argpartition
。
partition
函数的功能如下:给定一个array
,将其中的元素重新整理使得第k位的元素刚好是全排序第k位的元素。所有比第k位元素小的元素都被放在它前面,所有比第k位元素大的元素都放在它后面。也就是说,这个第k位元素就将整个数组分成了两个部分,前面比它小,后面比它大。但是每个部分内部的元素并没有进行排序。