javaデータ構造並べ替えアルゴリズムのツリー形選択順序詳細
本明細書の例は、Javaデータ構造並び替えアルゴリズムのツリー形選択順序付けを説明する。皆さんに参考にしてあげます。具体的には以下の通りです。
ここでは、選択の順序の一つについて説明します。ツリーの形の選択順序です。
簡単な選択順序では、比較のたびに前回の比較結果を使っていませんので、比較作業の時間の複雑さはO（N^2）です。比較の回数を下げたいなら、比較中のサイズ関係を保存してください。ツリーの選択順序は、簡単な選択順序の改善です。
ツリーの形の選択順位：また選手権の順序とも言われています。選手権の思想によって順位を選ぶ方法です。まずn個の記録のキーワードを二つの比較して、n／2個の小さい者の間で二つの比較を行い、最小の記録を選ぶまでこのように繰り返します。
アルゴリズム実装コードは以下の通りです。
ツリーの選択順序においては、最小のキーワードを除いて、選出された最小のキーワードは、葉っぱの結点からノードとの比較過程を行っています。n個の葉っぱの結点を含む完全な二叉樹の深さlogl 2 n＋1であるため、樹形の選択順序において、小さいキーワードを選ぶごとにlog 2 nを比較する必要があります。その時間の複雑度はO（nlogl 2 n 2 n）です。移動記録回数は比較回数を超えないので、合計アルゴリズム時間の複雑度はO（nlog 2 n）であり、単純な選択順序付けアルゴリズムと比較して、比較回数の数段が減少し、n−1個の追加的な記憶空間保存中間比較結果が増加した。
追加:
ここでは，樹形の選択秩序化のための改良アルゴリズム，すなわち，スタック並び替えアルゴリズムを紹介します。
積み上げ順序は、ツリー形の選択順序付けアルゴリズムが空間の多くを占めることの欠陥を補っている。ヒープ並べ替えを使用する場合は、サイズを記録する補助空間だけが必要です。
アルゴリズムの思想は:
並べ替え記録されるキーワードを配列r[1...n]に格納し、rを完全二叉樹と見なす順序は、各結点は記録を表し、最初の記録r[1]は二叉樹の根とし、以下の各記録r[2...n]は順に左から右へ並べ、意結点r[i]の左の子供はr[2*i]であり、右の子供はr[i＋1]である。両親はr[i/2]]です。
ヒープ定義：各結点のキーワード値は以下の条件を満たす：
r[i].key=r[2 i].key且r[i].key=r[2 i+1].key (i=1,2，…[i/2]
上の条件を満たす完全な二叉の木を大根山と呼びます。逆に、この完全な二叉の木の中の任意の結点のキーワードが左の子供と右の子供のキーワードより小さい場合、対応する山は小根の山と呼ばれます。
積み上げ順序の過程は主に二つの問題を解決する必要があります。一つ目は、積み上げの定義に従って、最初の山を建てることです。二つ目は、最大元を取り除いて再構築し、次の大元を得ることです。
ヒープ並べ替えとは、ヒープの特性を利用して記録シーケンスを並べ替えることであり、プロセスは以下の通りである。
1、所与のシーケンスに対してヒープを構築する。
2、出力スタックトップ；（最初の要素と最後の要素の交換）
3、残存元素の再構築炉；（フィルタの最初の要素)
4、すべての要素が出力されるまで、2、3を繰り返します。
注意：「スクリーニング」は、「n/2」の結点から始まり、層ごとに上に後退し、ルートの結点までとする。
アルゴリズム解析:
1.深さがkの山に対して、「スクリーニング」に必要なキーワードを比較する回数はせいぜい2（k-1）である。
2.n個のキーワードの山の深さは [log 2 n++1,最初にヒープを構築するために必要なキーワードの比較回数は、n*[log 2 n]が最も多いです。
3.スタックn-1を再構築し、必要なキーワードの比較の回数は超えない：（n-1）*2[log 2 n]
したがって、ヒープ順序付けは最悪の場合、その時間の複雑さはO（nlog 2 n）であり、これはヒープ順序付けの最大の利点である。
javaアルゴリズムに関する詳細について興味がある読者は、当駅のテーマを見ることができます。「Javaデータ構造とアルゴリズム教程」、「Java操作DOMノード技術のまとめ」、「Javaファイルとディレクトリの操作テクニックのまとめ」、「Javaキャッシュ操作テクニックのまとめ」
本論文で述べたように、皆さんのjavaプログラムの設計に役に立ちます。
ここでは、選択の順序の一つについて説明します。ツリーの形の選択順序です。
簡単な選択順序では、比較のたびに前回の比較結果を使っていませんので、比較作業の時間の複雑さはO（N^2）です。比較の回数を下げたいなら、比較中のサイズ関係を保存してください。ツリーの選択順序は、簡単な選択順序の改善です。
ツリーの形の選択順位：また選手権の順序とも言われています。選手権の思想によって順位を選ぶ方法です。まずn個の記録のキーワードを二つの比較して、n／2個の小さい者の間で二つの比較を行い、最小の記録を選ぶまでこのように繰り返します。
アルゴリズム実装コードは以下の通りです。
package exp_sort;
public class TreeSelectSort {
public static int[] TreeSelectionSort(int[] mData) {
int TreeLong = mData.length * 4;
int MinValue = -10000;
int[] tree = new int[TreeLong]; //
int baseSize;
int i;
int n = mData.length;
int max;
int maxIndex;
int treeSize;
baseSize = 1;
while (baseSize < n) {
baseSize *= 2;
}
treeSize = baseSize * 2 - 1;
for (i = 0; i < n; i++) {
tree[treeSize - i] = mData[i];
}
for (; i < baseSize; i++) {
tree[treeSize - i] = MinValue;
}
//
for (i = treeSize; i > 1; i -= 2) {
tree[i / 2] = (tree[i] > tree[i - 1] ? tree[i] : tree[i - 1]);
}
n -= 1;
while (n != -1) {
max = tree[1];
mData[n--] = max;
maxIndex = treeSize;
while (tree[maxIndex] != max) {
maxIndex--;
}
tree[maxIndex] = MinValue;
while (maxIndex > 1) {
if (maxIndex % 2 == 0) {
tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex + 1] ? tree[maxIndex]
: tree[maxIndex + 1]);
} else {
tree[maxIndex / 2] = (tree[maxIndex] > tree[maxIndex - 1] ? tree[maxIndex]
: tree[maxIndex - 1]);
}
maxIndex /= 2;
}
}
return mData;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
TreeSelectionSort(array);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("
");
}
}
ツリーの選択順序においては、最小のキーワードを除いて、選出された最小のキーワードは、葉っぱの結点からノードとの比較過程を行っています。n個の葉っぱの結点を含む完全な二叉樹の深さlogl 2 n＋1であるため、樹形の選択順序において、小さいキーワードを選ぶごとにlog 2 nを比較する必要があります。その時間の複雑度はO（nlogl 2 n 2 n）です。移動記録回数は比較回数を超えないので、合計アルゴリズム時間の複雑度はO（nlog 2 n）であり、単純な選択順序付けアルゴリズムと比較して、比較回数の数段が減少し、n−1個の追加的な記憶空間保存中間比較結果が増加した。
追加:
ここでは，樹形の選択秩序化のための改良アルゴリズム，すなわち，スタック並び替えアルゴリズムを紹介します。
積み上げ順序は、ツリー形の選択順序付けアルゴリズムが空間の多くを占めることの欠陥を補っている。ヒープ並べ替えを使用する場合は、サイズを記録する補助空間だけが必要です。
アルゴリズムの思想は:
並べ替え記録されるキーワードを配列r[1...n]に格納し、rを完全二叉樹と見なす順序は、各結点は記録を表し、最初の記録r[1]は二叉樹の根とし、以下の各記録r[2...n]は順に左から右へ並べ、意結点r[i]の左の子供はr[2*i]であり、右の子供はr[i＋1]である。両親はr[i/2]]です。
ヒープ定義：各結点のキーワード値は以下の条件を満たす：
r[i].key=r[2 i].key且r[i].key=r[2 i+1].key (i=1,2，…[i/2]
上の条件を満たす完全な二叉の木を大根山と呼びます。逆に、この完全な二叉の木の中の任意の結点のキーワードが左の子供と右の子供のキーワードより小さい場合、対応する山は小根の山と呼ばれます。
積み上げ順序の過程は主に二つの問題を解決する必要があります。一つ目は、積み上げの定義に従って、最初の山を建てることです。二つ目は、最大元を取り除いて再構築し、次の大元を得ることです。
ヒープ並べ替えとは、ヒープの特性を利用して記録シーケンスを並べ替えることであり、プロセスは以下の通りである。
1、所与のシーケンスに対してヒープを構築する。
2、出力スタックトップ；（最初の要素と最後の要素の交換）
3、残存元素の再構築炉；（フィルタの最初の要素)
4、すべての要素が出力されるまで、2、3を繰り返します。
注意：「スクリーニング」は、「n/2」の結点から始まり、層ごとに上に後退し、ルートの結点までとする。
アルゴリズム解析:
1.深さがkの山に対して、「スクリーニング」に必要なキーワードを比較する回数はせいぜい2（k-1）である。
2.n個のキーワードの山の深さは [log 2 n++1,最初にヒープを構築するために必要なキーワードの比較回数は、n*[log 2 n]が最も多いです。
3.スタックn-1を再構築し、必要なキーワードの比較の回数は超えない：（n-1）*2[log 2 n]
したがって、ヒープ順序付けは最悪の場合、その時間の複雑さはO（nlog 2 n）であり、これはヒープ順序付けの最大の利点である。
javaアルゴリズムに関する詳細について興味がある読者は、当駅のテーマを見ることができます。「Javaデータ構造とアルゴリズム教程」、「Java操作DOMノード技術のまとめ」、「Javaファイルとディレクトリの操作テクニックのまとめ」、「Javaキャッシュ操作テクニックのまとめ」
本論文で述べたように、皆さんのjavaプログラムの設計に役に立ちます。