データ構造とアルゴリズム16のスタックソート
本文はブロガーのオリジナル文章で、転載は出典を明記してください:http://blog.csdn.net/eson_15/article/details/51193399
スタック・ソートとは、その名の通り、スタックというデータ構造を利用してデータ・アイテムをソートすることであり、前述したように、スタック・データ構造では、ノードが自分のサブノード以上である.ソートするデータ項目をスタックに順次追加し、ルートノードを順次取り出すことができます.スタックから取り出したデータ項目は、大きいものから小さいものまで並べられています.ルートノードは常に最大であり、スタック内は常にルートノードであるためです.スタックというデータ構造をよく知らない場合は、まずこのブログを見ることができます.データ構造とアルゴリズムのスタックです.ここでは説明しません.
次に、スタックソートの実装を見てみましょう(プログラムに不明な点があれば、上記のブログを参考にすることもできます).
アルゴリズム解析:スタック内の挿入と取り出しの時間的複雑度はいずれもO(logn)であるため、スタックソートアルゴリズムの時間的複雑度はO(Nlogn)であるが、スタックソートにはソート対象シーケンスと同じサイズの追加の記憶空間が必要である.空間的複雑度はO(N)である.
_____________________________________________________________________________________________________________________________________________________
---分かち合い、共に進歩することを喜ぶ!
------詳細は以下を参照してください.http://blog.csdn.net/eson_15
スタック・ソートとは、その名の通り、スタックというデータ構造を利用してデータ・アイテムをソートすることであり、前述したように、スタック・データ構造では、ノードが自分のサブノード以上である.ソートするデータ項目をスタックに順次追加し、ルートノードを順次取り出すことができます.スタックから取り出したデータ項目は、大きいものから小さいものまで並べられています.ルートノードは常に最大であり、スタック内は常にルートノードであるためです.スタックというデータ構造をよく知らない場合は、まずこのブログを見ることができます.データ構造とアルゴリズムのスタックです.ここでは説明しません.
次に、スタックソートの実装を見てみましょう(プログラムに不明な点があれば、上記のブログを参考にすることもできます).
public class HeapSort {
private int[] array;
private int currentIndex;
private int maxSize;
public HeapSort(int size) {
maxSize = size;
array = new int[maxSize];
currentIndex = 0;
}
// ,
public void insertSort(int[] source) {
for(int i = 0; i < source.length; i++) {
array[currentIndex] = source[i]; //
tickedUp(currentIndex++); // ,
}
}
private void tickedUp(int index) {
int parentIndex = (index - 1) / 2; //
int temp = array[index]; // temp
while(index > 0 && array[parentIndex] < temp) {
array[index] = array[parentIndex];
index = parentIndex;
parentIndex = (index - 1) / 2;
}
array[index] = temp;
}
//
public int getMax() {
int maxNum = array[0];
array[0] = array[--currentIndex];
trickleDown(0);
return maxNum;
}
private void trickleDown(int index) {
int top = array[index];
int largeChildIndex;
while(index < currentIndex/2) { //while node has at least one child
int leftChildIndex = 2 * index + 1;
int rightChildIndex = leftChildIndex + 1;
//find larger child
if(rightChildIndex < currentIndex && //rightChild exists?
array[leftChildIndex] < array[rightChildIndex]) {
largeChildIndex = rightChildIndex;
}
else {
largeChildIndex = leftChildIndex;
}
if(top >= array[largeChildIndex]) {
break;
}
array[index] = array[largeChildIndex];
index = largeChildIndex;
}
array[index] = top;
}
}
アルゴリズム解析:スタック内の挿入と取り出しの時間的複雑度はいずれもO(logn)であるため、スタックソートアルゴリズムの時間的複雑度はO(Nlogn)であるが、スタックソートにはソート対象シーケンスと同じサイズの追加の記憶空間が必要である.空間的複雑度はO(N)である.
_____________________________________________________________________________________________________________________________________________________
---分かち合い、共に進歩することを喜ぶ!
------詳細は以下を参照してください.http://blog.csdn.net/eson_15