3ウェイエクスプレス実装コード(C++)

3つの速い列は、分割ごとに配列を3つの部分に分割し、左から右にかけてkeyより小さい部分であり、keyに等しい部分であり、keyより大きい部分である.次のサブレンジでソート関数を再帰的に呼び出す場合は、左右の2つの部分をソートするだけです.2つの高速配列が重複要素が多い場合に存在する効率の問題を解決した.
ソート対象データC++乱数クラスdefault_random_Engine生成
less<=moreは、ソートがまだ完了していないことを示します.less,more位置要素はいずれも処理しようとするがまだ処理されていない要素である.
2つの高速列において,[L,...,less-1]の範囲内の要素は,いずれもkey未満を満たす要素である.[more+1,...,R]はいずれもkeyより大きい要素を満たす.
速列選択keyをランダムに選択するたびに,配列秩序O(n^2)の最悪の場合を回避できる.
コードは次のとおりです.

#include 
#include 
#include 
#include 
using namespace std;
using iv_it = vector::iterator;

vector sortData(20,0);
int choice = 3;//choice         ，  3 (   2 or 3)
default_random_engine e;

void Qsort(vector& iv, int L, int R);
int Partition(vector& iv, int L, int R);
void Partition(vector& iv, int L, int R, int border[]);


void swap(vector& iv, int i, int j)
{
	int temp = iv[j];
	iv[j] = iv[i];
	iv[i] = temp;
}

void generateData(vector& iv)
{
	e.seed(time(0));
	for (auto i = iv.begin(); i != iv.end(); ++i)
		*i = e() % 100;
	cout << "    :" << endl;
	for (auto i = iv.begin(); i != iv.end(); ++i)
		cout << *i << " ";
	cout << endl;
}

void QuickSort(vector& iv)
{
	if (iv.empty()||iv.size()==1)
		return;
	Qsort(iv, 0, iv.size() - 1);
}

void Qsort(vector& iv, int L, int R)
{
	if (R - L <= 0)
		return;
	swap(iv, L, L + e() % (R-L+1));	//   

	if (choice == 2)
	{
		int p = Partition(iv, L, R);
		Qsort(iv, L, p-1);	
		Qsort(iv, p + 1, R);
	}
	else if (choice == 3)
	{
		int border[] = { 0,0 };
		Partition(iv, L, R, border);
		Qsort(iv, L, border[0] - 1);
		Qsort(iv, border[1] + 1, R);
	}

}

//  
void Partition(vector& iv, int L, int R, int border[])
{
	int key = iv[L], less = L + 1, more = R, k = L;
	while (true)
	{
		while (less <= more)
		{
			if (iv[less] < key)	swap(iv, k++, less++);
			else if (iv[less]==key)	less++;
			else break;
		}
		while (more >= less)
		{
			if (iv[more] > key) --more;
			else if (iv[more] == key)swap(iv, more, less++);
			else break;
		}
		if (less > more) break;
		swap(iv, less, more); //     More--，   more    ，  key     less++ ，  less         
	}
	border[0] = k;
	border[1] = less - 1;
}

//  
int Partition(vector& iv,  int L, int R)
{
	int key = iv[L];
	int less = L + 1, more = R;
	while (1)
	{
		while (less<=more && iv[less] < key) ++less;
		while (less<=more && iv[more] > key) --more;
		if (more < less) break;
		swap(iv, less++, more--);
	}
	swap(iv, L, more);
	return more;
}

int main()
{
	cout << "  0  ， 0  :
" << endl;
	int i;
	while (cin >> i)
	{
		if (i == 0) break;
		generateData(sortData);
		QuickSort(sortData);
		cout << "      :" << endl;
		for (auto i = sortData.begin(); i != sortData.end(); ++i)
			cout << *i << " ";
		cout <