スタックソートアルゴリズムの詳細

1764 ワード

アルゴリズム積み上げ順序

ターゲット:配列を小さいものから大きいものに並べる
アルゴリズム記述:スタックソートでは、ソート対象配列を完全二叉木と見なし、ソート対象シーケンス数はA[1...n]に格納され、A[0]から始まるのではなく、完全二叉木におけるノード番号の関係を利用するため、iと表記されたノードの左右の子供ノードの下に2 iと2 i+1と表記される.大きなルートスタックA[i]>=A[2 i]およびA[i]>=A[2 i+1]の場合、最大要素はルートノードに格納され(小さなルートスタックA[i]<=A[2 i]、A[i]<=A[2 i+1)、最小要素はルートノードに格納される).スタックソートでは、まず初期スタックを確立し、その後、スタックトップ要素A[1](n個の要素の最大値)をスタックベース要素A[n]と交換し、残りのA[1...n-1]を再び大きなスタックになるように調整し、スタックトップ要素A[1](n-1個の要素の最大値)をスタックベース要素A[n-1]と交換し、スタックに1つの要素しか残っていないまで繰り返す必要がある.
アルゴリズム実装(テスト実行済み):

/*    ：   
**    ：A   ，len      ，   A    1
*/
void HeapSort(int A[], int len)
{
	BuildMaxHeap(A, len); //    
	for (int i = 0; i < 8; i++){ cout << A[i] << endl; }
	for (int i = len; i>1; i--)
	{
		int tmp = A[i];
		A[i] = A[1];
		A[1] = tmp;

		AdjustDown(A, 1, i - 1); // A[1]      ，    i-1         
	}
}

/*    ：     
*/
void BuildMaxHeap(int A[], int len)
{
	for (int i = len / 2; i>0; i--)  // len/2         ，     A[1]
	{
		AdjustDown(A, i, len);
	}
}

/*    ：    ，    i                  
**    ：A   ，i        
*/
void AdjustDown(int A[], int i, int len)
{
	A[0] = A[i];  //  
	for (int j = 2 * i; j <= len;j*=2)
	{
		if (j= A[j])
			break;    //              ，    
		else
		{
			A[i] = A[j];
			i = j;
		}
	}
	A[i] = A[0]; //              i
}

アルゴリズムパフォーマンス
時間の複雑さ:最良の場合、O(nlogn)
最悪、O(nlogn)
平均、O(nlogn)
初期スタックの時間的複雑度:O(n)
空間複雑度:定数個の補助ユニットのみを用い,O(1)
安定性あんていせい:不安定
拡張:
1000 W個の数の中で最小の1000個の数を探し出し,1000個のノードの大きなルートスタックを構築する.1001番目の数が現れると、まずスタックトップ(最大要素)と比較し、スタックトップよりも大きい場合、1001番目の数は必ず最小の1000個の数の列になく、捨てられる.スタックトップより小さい場合は、スタックトップ要素を置き換え、下に調整して、大きなスタックに再構築します.1000 W個の処理が完了するまで.
同様に,1000 W個の数の中で最大の1000個の数を見つけるには,1000個のノードの小根スタックを構築する必要がある.

ネットワークフローの詳細

アルゴリズム----水仙の数