热爱互联网

partial_sort

算法的用处:
从一个无序数列(假设总共有 N 个元素)中选择前 M 个最小的元素 排序输出。
复杂度 O( N log M )

本算法接受一个middle 迭代器(位于序列[first,last)之内),然后重新安排 [first,last),使序列中的 middle-first个最小元素以递增顺序排列,
置于 [first,middle)内。其余 last-middle 个元素安置于 [middle,last)中,不保证有任何特定顺序。

使用 sort 算法,同样可以保证 较小的 M 个元素以递增顺序置于 [first,first+N)之内。选择 partial_sort 而非 sort 的唯一理由是效率。是的,
如果只是 挑出 前 M 个最小元素来排序,当然比对整个序列排序快上许多。

partial_sort有两个版本,其差别在于如何定义某个元素小于另一个元素。第一个版本使用 less-than 操作符,第二个版本使用仿函数 comp。算法内部采用 heap sort 来完成任务,简述如下:
partial_sort 的任务是找出 middle-first 个最小元素,因此,首先界定出区间 [first,middle),并利用 make_heap()将它组织成一个max-heap,然后就可以将 [middle,last)中的每一个元素拿来与 max-heap的最大值比较(max-heap的最大值就在第一个元素身上):如果小于该最大值,就互换位置并重新保持 max-heap 的状态。如此一来,当我们走遍整个[middle,last)时,较大的元素都已经被抽离出[first,middle),这时候再以 sort_heap() 将 [first,middle)做一次排序,即功德圆满。
partial_sort使用的一个例子如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<string>
#include<algorithm>
#include<iterator>
using namespace std;
int main(){
    int a[]={8,9,8,4,3,2,1,6,7};
 
    partial_sort(a,a+3,a+sizeof(a)/sizeof(int) );
 
    copy(a,a+sizeof(a)/sizeof(int),ostream_iterator<int>(cout," "));
 
    cout<<endl;
 
    system("pause");
    return 0;
}

下面是 partial_sort的实现细节,我只列出第一个版本。请注意:partial_sort只接受 RandomAccessIterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
                         RandomAccessIterator middle,
                         RandomAccessIterator last){
       _partial_sort(first,middle,last,value_type(first));
}
 
template<typename RandomAccessIterator,typename T>
void _partial_sort(RandomAccessIterator first,
                   RandomAccessIterator middle,
                   RandomAccessIterator last, T*){
     make_heap(first,middle);
     //注意,以下的 i<last 判断操作,只适合 random iterator
     for(RandomAccessIterator i = middle, i < last; ++i)
         if( *i < *first)
             _pop_heap(first,middle,i,T(*i), distance_type(first));
     sort_heap(first,middle);
}

关于 heap ,请看 http://www.darkswordzone.com/?p=1691

Post a Comment

Your email is kept private. Required fields are marked *