古典的なソートアルゴリズムの高速ソート

高速ソートはソートアルゴリズムの中で最も把握すべきものであり、そのソート戦略はバブルソートと同様に交換ソートに属する.基本的な手順は、次のように要約できます.
1、入力パラメータの合法性を判断する;
2、配列の最初(または最後)に記録されたキーワードを比較基準とし、そのキーワードより小さいレコードを左側に並べ、そのキーワードより大きいレコードを右側に並べます.
3、手順2の方法で、左の配列と右の配列をそれぞれ手順(2)のように操作します.
高速ソートc++実装、参照コードは以下の通りである(コードではステップ2で最後のレコードのキーワードを比較基準とする):

//     
#include <iostream>
using namespace std;

void swap(int &fir, int &sec)
{
	int temp = fir;
	fir = sec;
	sec = temp;
}

void print(int *input, int len)
{
	for (int i = 0; i < len; ++i)
	{
		cout << input[i] << " ";
	}
	cout << endl;
}

/////////////////////////////////////////////////////////////////
//           
int getPartitionPos(int *input, int start, int end)
{
	int temp = input[end];
	int j = start - 1;
	for (int i = start; i < end; ++i)
	{
		if (input[i] <= temp)
		{
			j++;
			if (i != j)
			{
				swap(input[i], input[j]);
			}
		}
	}
	swap(input[j + 1], input[end]);
	return (j + 1);
}

void quick_sort(int *input, int start, int end)
{
	if (start>=end) return;
	int middle; //      
	middle = getPartitionPos(input, start, end);
	quick_sort(input, start, middle - 1);
	quick_sort(input, middle + 1, end);
}

void QuickSort(int *input, int len)
{
	if (input == nullptr || 0 == len)return;
	quick_sort(input, 0, len-1);
}

/////////////////////////////////////////////////////////////////

int main(int argc, char *argv[])
{
	int input[] = { 72, 13, 8, 94, 24, 50, 2, 28, 62, 75, 49 };
	int len = 11;
	print(input, len);
	QuickSort(input, len);
	print(input, len);

	system("pause");
	return 0;
}

アルゴリズム解析:
1、上記コードの最も重要な部分は、分割点における位置インデックスを得ることである.より明確に理解するために、自分で紙の上でコンピュータの実現過程をシミュレートしたり、ブレークポイントを追加した後、単一のステップでデバッグを追跡したりすることができます(または参考:http://www.cnblogs.com/pugang/archive/2012/06/27/2565093.html);
2、平均時間複雑度:O(n log n);
3、安定性:不安定;このステップを実行すると、要素の安定性を乱す可能性があります.

swap(input[j + 1], input[end]);

4、相応の改善:快速はすでに相対的に完備しており、具体的に実現する時、主にgetPartitionPos()関数の実現方法は異なる.その後、いくつかの相応の改善構想には、1)比較基準(ピボットとも呼ばれる)の選択に対する最適化;本例ではinput[end]を選択し、その他には三数取中、九数取中、ランダム選択などがあり、もちろん対応する実現コードには対応調整が必要である.2)並べ替え待ち記録数が小さい場合、直接挿入して並べ替える;総記録が小さい場合、高速ソートでは効率が必ずしも高くなく、大材小用の疑いがあり、実際に使用するときにソートされる記録数のしきい値を設定することができ、すなわち、そのしきい値を超えて高速ソートを使用し、そうでなければ直接ソートを挿入することができる.3)他の交換と逆帰の面での最適化(興味のあるものは自分で研究することができる).