[ Median-of-Medians Algorithm ] 中位數演算法

這是一個可以在保證線性時間(c++ std::nth_element是隨機演算法)找出一個序列中第k大元素的演算法，網路上已經有不少教學，但是很多人都認為常數太大因此缺乏實作。

教學文在此：http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median

其實我高中時就想要試著去時做看看，但是因為那時的程式能力太差的關係，做出來的東西一直有bug，後來去忙其他事情後就被我忘掉了。最近因為學長面試有被問到一樣的問題跑來問我，才慢慢想起來有一份沒寫完的code，於是今天抱著不管怎樣都要寫出來的精神把他寫完了：

	#include<algorithm>
	template<typename IT,typename CMP>
	inline IT find_mid(const IT first,const IT last,CMP cmp){
	std::sort(first,last,cmp);
	return first+(last-first)/2;
	}
	template<typename IT,typename CMP>
	inline IT partition(IT first,IT last,IT pivot,CMP cmp){
	if(last-first<1)return pivot;
	std::iter_swap(--last,pivot);
	pivot=last;
	for(;;){
	while(cmp(*first,*pivot))++first;
	--last;
	while(cmp(*pivot,*last))--last;
	if(!(first<last)){
	std::iter_swap(first,pivot);
	return first;
	}
	std::iter_swap(first,last);
	++first;
	}
	}
	template<typename IT,typename CMP>
	IT kth(const IT first,const IT last,int k,CMP cmp){
	if(k==0||k>last-first) return last;
	IT mid_e=first,i=first;
	for(;i+5<last;i+=5){
	std::iter_swap(mid_e++,find_mid(i,i+5,cmp));
	}
	std::iter_swap(mid_e++,find_mid(i,last,cmp));
	int five_mid=mid_e-first;
	mid_e=(five_mid==1)?first:kth(first,mid_e,five_mid/2,cmp);
	IT pos=partition(first,last,mid_e,cmp);
	if(pos-first==k-1) return pos;
	if(pos-first<k) return kth(pos+1,last,k-(pos-first+1),cmp);
	return kth(first,pos,k,cmp);
	}

view raw kth.cpp hosted with ❤ by GitHub

	template<typename IT,typename CMP>
	void SM_sort(IT first,IT last,CMP cmp){ // 幫他寫了一個sort做測試
	if(last-first<=1)return;
	IT mid=kth(first,last,(last-first)/2,cmp);
	SM_sort(first,mid,cmp);
	SM_sort(mid+1,last,cmp);
	}

view raw SM_sort.cpp hosted with ❤ by GitHub