老师写的程序

template<typename Bitr>
Bitr partition(Bitr first, Bitr last)
{   //simple version, *first as pivot, guarded
	//precondition:[first, last) not empty
	Bitr ppivot = first;
	while(true)
	{
		while(*ppivot < *--last)
			;
		while((first != last)&&!(*ppivot < *++first))
			//while(first != last && *++first <= *ppivot)
			//*++first <= *ppivot
			;
		if(first == last)
		{
			std::swap(*ppivot, *last);
			return last;
		}
		else
			std::swap(*first, *last);
	}
}//~partition(Ritr first, Ritr last)
//qsort
template<typename Bitr>
void qsort(Bitr first, Bitr last)
{
	if(first == last)
		return;
	Bitr ppivot = partition<Bitr>(first, last);
	qsort(first, ppivot);
	qsort(++ppivot, last);
}//qsort(Bitr first, Bitr last) 
template<typename Bitr>
void qsort_v1r2(Bitr first, Bitr last)
{ //tail recursion removed
	while(first != last)
	{
		Bitr ppivot = partition(first, last);
		qsort_v1r2(first, ppivot);
		first = ++ppivot;
	}
}//~qsort_v1r2(Bitr first, Bitr last)
template<typename Ritr>
void qsort_v2(Ritr first, Ritr last)
{
	while(first != last)
	{
		Ritr ppivot = partition(first, last);
		if(ppivot - first < last - ppivot)
		{ //short long
			qsort_v2(first, ppivot);
			first = ppivot+1;
		}
		else
		{ //long short
			qsort_v2(ppivot+1, last);
			last = ppivot;
		}
	}//~while
}//~qsort_v2(Ritr first, Ritr last)