ソートアルゴリズム(七):スタックソート

一、アルゴリズム原理スタック並べ替え(Heap sort)スタックのようなデータ構造を用いてデータ管理を行い、それは集計並べ替えと同じであるが挿入並べ替えとは異なる時間複雑度がO(nlogn)である.挿入ソートと同じですが、集計ソートとは異なり、空間的なアドレス性があります(任意の場合、一時的なデータを格納するために定数の追加の要素空間しか必要ありません).従って,スタックソートは,この2つのソートアルゴリズムの利点を組み合わせた.スタック(二叉スタック)は配列であり、最下層を除いて完全に満たされ、左から右に充填された完全な二叉木と見なすことができる.ノードの下付きi(下付き1から0は適用されません)を指定すると、親ノード、左子供、右子供の下付きを簡単に計算できます.
ノード
下付き文字
親ノード
i/2
左の子
2 * i
右の子
2 * i + 1
スタックソートアルゴリズムでは、最大スタック(スタックの各ノードが子供ノードより大きい)を使用して、ソート時にスタックトップ要素を最後の要素と交換し、スタックの規模を1つ減らしてスタックの性質を回復します.二、アルゴリズムは主な三つの方法の呼び出しを説明する.

MaxHeapifyメソッド:最も多くの性質を維持し、A[i]の値を最上位に「段階的に下げる」ことにより、iをルートノードとするサブツリーが最上位になるようにする.具体的には、ノードA[i]の左右のサブツリーが最大スタックであると仮定し、各関数呼び出しにおいて、A[i]、A[Left(i)]とA[Right(i)]の間から最大の1つを決定し、その下付きラベルをlargestに保存する.A[i]最大であり、iをルートノードとするサブツリーはすでに最大のスタックである.最大要素が子供ノードである場合、A[i]とA[largest]の値を交換し、iとその子供ノードを最も多くの性質に保つ.交換後、largestとラベルされたノードがルートノードであるサブツリーは、最大スタック特性に違反する可能性があるため、maxHeapifyメソッドを再帰的に呼び出す.

BuildMaxHeap法:maxHeapify法を用いてn=A.length規模の配列A[1...n]を最大スタックに変換する.リーフノードはA[n/2+1...n]であり,各リーフノードは1つの要素のみを含むスタックと見なすことができる.buildMaxHeapメソッドは、他のノードごとにmaxHeapifyメソッドを1回呼び出すことです.

HeapSortメソッド:まずBuildMaxHeapメソッドを使用して入力配列を最大スタックにします.配列中の最大要素はルートノードA[1]にあるため、配列末尾要素A[n]と交換することで、その要素を正しい位置に置くことができます.次に、スタックからノードnを除去し、残りのノードでは、新しいルートノードが最も大きな性質に反する可能性がある.最上位クラスの性質を維持するために,MaxHeapify法を再呼び出し,ルートノードを沈め,A［1…n−1］に新たな最大クラスのスタックを再構築した.スタックソートアルゴリズムは、スタックのサイズがnから2に下がるまで、このプロセスを繰り返します.

配列を降順に並べ替える必要がある場合は、上記のスタック並べ替えアルゴリズムとは逆の方法で、スタック並べ替えに使用される最小スタックを維持できます.
三、アルゴリズム複雑度スタック並べ替えアルゴリズムの時間複雑度最悪はT(n)=O(nlogn)、最適はT(n)=O(nlogn)、平均はT(n)=O(nlogn)である.
四、サンプルコード

//          
void exchange(int * a, int * b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

//        
void MaxHeapify(int A[], int size, int index)
{
	int left = 2 * index;         //     
	int right = 2 * index + 1;    //     
	int largest = index;          //            
	
	//    index                 
	if(left <= size && A[left] > A[largest])
		largest = left;
	if(right <= size && A[right] > A[largest])
		largest = right;
	
	//          ，       ，         
	if(largest != index)
	{
		exchange(&A[index], &A[largest]);
		MaxHeapify(A, size, largest);    
	}
}

//     ，     A[1]  
void BuildMaxHeap(int A[], int length)
{
	int size = length;
	//    ， A[size/2]    
	for (int i = size / 2; i >= 1; i--)
	{
		MaxHeapify(A, size, i);
	}
}

//   
void HeapSort(int A[], int length)
{
	BuildMaxHeap(A, length);
	
	int size = length;
	while (size > 1)
	{
		exchange(&A[1], &A[size]);  //                 
		size--;                     //     
		MaxHeapify(A, size, 1);     //        
	}		
}