【C++】——クイックソート(前後ポインタ、ピット掘り、クイックスローポインタ)

一、前後指針法
基本構想:1.配列の最初の数a[left]を基準数keyとする.2.パーティション化プロセス:rightはkeyより小さい数を前方に探し始める(endは小さい).配列の最初の要素leftはkeyより大きい数を後ろに探し始めた(beginは大きい).見つかったら、begin>=endがループを終了するまで、両者を交換します(swap).最後にbeginと最後の数を交換する(このときendは最後の位置ではない)、すなわちkeyを中間数(左区間ともkeyより小さい数、右区間ともkeyより大きい数)3.各区間が1つになるまで左右区間に対して2歩目を繰り返す.

 void QuickSort(int* a, int begin, int end)
{
	if (begin < end)
	{
		int left = begin;
		int right = end;
		int temp = a[left];
		while (left != right)
		{
			while (left < right&&a[right] >= temp)
				right--;
			while (left < right&&a[left] <= temp)
				left++;
			swap(a[left], a[right]); 
		}
		swap(a[left], a[begin]);
		QuickSort(a, begin, left-1);
		QuickSort(a, left + 1, end);
	}
}
void print(int* a)
{
	for (int i = 0; i < 6; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	int a[6] = { 9,5,7,6,8,0 };
	cout << "     ：" << endl;
	QuickSort(a, 0, 5);

	print(a);
	system("pause");
	return 0;
}

二、掘削方法
ピット掘削法の速い列は前後のポインタ法とよく似た基本構想である:2つのポインタleftが開始位置を指すことを定義し、rightが最後の要素の位置を指すことを定義し、それから1つの基数key(right)を指定し、ピットleftとして基数(key)より大きい数字を探し、見つけたらleftのデータをrightに与え、leftがピットになり、rightは基数(key)より小さい数字を探し、rightのデータをleftに割り当て、rightは新しいピットとなり、beginポインタがendポインタと出会うまでこのプロセスをループし、keyをそのピットに戻し(最終:keyの左側はkeyより小さい数であり、keyの右側はkeyより大きい数である)、再帰操作を行う.

//      
void partSort(int* arr, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		int temp = arr[end];  //    

		while (begin != end)
		{
			while (begin < end&&arr[begin] <= temp)
				begin++;
			if (begin < end)
				arr[end] = arr[begin];  //begin     
			while (begin < end&&arr[end] >= temp)
				end--;
			if (begin < end)
				arr[begin] = arr[end];
		}
 		arr[begin] = temp;
		partSort(arr, left, begin-1);
		partSort(arr, begin + 1, right);
	}
	
}
void print(int* a)
{
	for (int i = 0; i < 6; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	int a[6] = { 2,5,1,6,8,0 };
	cout << "        :" << endl;
	partSort(a, 0, 5);
	print(a);
	system("pause");
	return 0;
}

三、前後指針法
基本構想:2つのポインタを定義し、1つ前の後、cur(前)は開始位置を指し、prev(後)はcurの前の位置を指す.配列の最後の要素をkey(right)実装プロセスとして選択する:curはkeyより小さい数を探し、prevはcurが見つからない場合、ずっと動かない(すなわちprevがkeyより大きい数を指していることを保証する).curがkeyより小さい数(++prev&&prev!=cur)を見つけてから++curになるまでprevは動かない.curがrightの前の位置に着くまでループを終了します.最後の++prev、prevとrightの値を交換

//     
void PartSort3(int* a, int begin, int end)
{
	if (begin <= end)
	{
		int temp = a[end];
		int cur = begin;
		int prev = begin - 1;
		while (cur < end)
		{
			if (a[cur] < temp&&++prev != cur)
			{
				swap(a[cur], a[prev]);
			}
			++cur;
		}
		prev++;
		swap(a[cur], a[prev]);
		PartSort3(a, begin, prev - 1);
		PartSort3(a, prev+1, end);
	}
}
void print(int* a)
{
	for (int i = 0; i < 6; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}
int main()
{
	int a[6] = { 9,5,7,6,8,0 };
	cout << "     ：" << endl;
	PartSort3(a, 0, 5);

	print(a);
	system("pause");
	return 0;
}

クイックソートで使用されるシーンは、データ量が多く乱雑なシーケンスであり、最悪の場合を避ける(効率を高めるために三数取中法を用い、数字サイズが10未満の場合は、直接挿入ソートでスタックフレームを減らす)
次のようになります.

クイックソートが最適な場合:キーワードがシーケンスの真ん中にあるとき

クイックソートが最悪の場合:秩序化されたシーケンスをソート

時間複雑度:O(N^2)最悪、O(N*lgN)最良

空間複雑度:O(1)

安定性:不安定