c++ヒルソートの実現

ヒルソート(Shell Sort)は、インクリメンタルソートアルゴリズムとも呼ばれ、ソートを挿入する高速で安定した改良バージョンです.ヒルソートは、挿入ソートの以下の2点の性質に基づいて改善方法を提案する:1.挿入ソートは、ほぼ並べ替えられたデータに対して操作する場合、効率が高く、すなわち線形ソートの効率を達成することができる.2.しかし、挿入ソートは一般的に非効率です.挿入ソートは毎回データを1ビットしか移動できないからです.
ヒルソートの一般的な手順は:1.まずnより小さい整数d 1を最初のインクリメントとして取り,ファイルの全記録をd 1グループに分ける.すべての距離がdlの倍数のレコードは同じグループに配置され,各グループ内で直接挿入ソートが行われる.2.第2のインクリメンタルd 2ステップの選択は、ヒルソートの重要な部分である.最終ステップ長が1であれば、どのステップ長シリアルでも動作します.アルゴリズムは最初に一定のステップでソートされます.その後、一定のステップでソートされ続け、最終アルゴリズムはステップ長1でソートされます.ステップ長が1の場合、アルゴリズムはソートを挿入し、データが必ずソートされることを保証します.
平均時間複雑度:O(nlogn)安定性:不安定

//              ，          ，   2 shell           θ(n 3/2  )，        θ(n 7/6  )，   θ(n)。
//              ，            。
#include 
using namespace std;
void ShellSort(int array[], int n)
{
	int i, j;
	int increment = n;
	do
	{
		increment = increment / 3 + 1;//    
		for (i = increment + 1; i <= n; i++)
		{
			if (array[i] < array[i - increment])
			{
				array[0] = array[i];
				for (j = i - increment; j>0 && array[0] < array[j]; j -= increment)
					array[j + increment] = array[j];
				array[j + increment] = array[0];
			}
		}
	} 
	while (increment>1);
}
void main()
{
	int arr[10];
	cout << "         ：" << endl;
	for (int i = 0; i < 10; i++)
	{
		cin >> arr[i];
	}
	//cout << "          " << arr[i] << endl;
	ShellSort(arr, 10);
	cout << "        " << endl;
	for (int i = 0; i < 10; i++)
	{
		cout << arr[i] << endl;
	}
	system("pause");
}