Java データ構造ソート アルゴリズム (1) ツリー選択ソート

この記事では、Java データ構造ソート アルゴリズムのツリー 選択ソート を主に紹介し、具体的な例に基づいて Java ツリー選択ソートの原理、実装テクニック、および関連する注意事項を分析します。例では、Java データ構造のツリー選択ソート アルゴリズムを説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

ここでは選択ソートの 1 つについて説明します: ツリー選択ソート

単純な選択ソートでは、各比較は前の比較を使用しません。比較演算の時間計算量は

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");
 }
}

アルゴリズム分析: ツリー選択ソートでは、最小のキーワードを除き、選択された最小のキーワードはすべて葉で区切られます。 n 個のリーフ ノードを含む完全なバイナリ ツリーの深さは log2n+1 であるため、ツリー選択の並べ替えでは、より小さいキーワードが選択されるたびに log2n の比較が必要になるため、時間は複雑度 O(nlog2n) になります。 、移動レコードの数は比較の数を超えないため、アルゴリズムの合計時間計算量は O(nlog2n) となり、単純な選択ソート アルゴリズムと比較すると、比較の数が n-1 桁減少します。追加のストレージスペースに中間比較結果が保存されます。

補足: ここでは、ツリー選択ソートの改良されたアルゴリズム、すなわち

ヒープソート

アルゴリズムを紹介します。 ヒープソートは、多くのスペースを占有するツリー選択ソートアルゴリズムの欠点を補います。ヒープ・ソートを使用する場合、必要な補助スペースはレコード・サイズの 1 つだけです。

アルゴリズムの考え方は次のとおりです:

ソートするレコードのキーワードを

配列

r[1...n]に格納し、rを完全なバイナリツリーの逐次表現とみなします各ノードは A レコードを表し、最初のレコード r[1] がバイナリ ツリーのルートとして使用され、各レコード r[2...n] が層ごとに順番に配置されます。任意のノード r[i] の左の子は r[2*i]、右の子は r[2*i+1]、親は r[[i/2]] です。

ヒープ定義:

各ノードのキー値は次の条件を満たします: r[i].key >= r[2i].key および r[i].key >= r[2i+1] ].key (i=1,2,…[i/2])

上記の条件を満たす完全なバイナリ ツリーは、逆に、この完全なバイナリ ツリー内のいずれかのノードのキーが大規模ルート ヒープと呼ばれます。左の値以下である 子および右の子のキーワードに対応するヒープは、小さなルート ヒープと呼ばれます。

ヒープのソートのプロセスでは、主に 2 つの問題を解決する必要があります。1 つ目は、ヒープ定義に従って初期ヒープを構築することです。2 つ目は、最大要素を削除して次の最大要素を取得した後にヒープを再構築することです。

ヒープのソートは、ヒープの特性を使用してレコード シーケンスをソートします。

1. ヒープの先頭を出力します。要素と最後の要素)

3. 残りの要素の再構築ヒープを実行します (最初の要素をフィルターします)

4. すべての要素が出力されるまで、手順 2 と 3 を繰り返します。


注:

「フィルタリング」は、[n/2] 番目のノードから開始し、ルート ノードまでレイヤーごとに逆方向に進む必要があります。

アルゴリズム分析:

1. 深さ k のヒープの場合、「フィルタリング」に必要なキーワード比較の数は最大 2 (k-1) です。n 個のキーワードのヒープ深さは次のとおりです。 [log2n]+1 の場合、最初にヒープを構築するために必要なキーワード比較の数は最大でも n* [log2n];3 です。ヒープを n-1 回再構築するために必要なキーワード比較の数は次を超えません: ( n-1)*2 [log2n];

したがって、ヒープソートの時間計算量は最悪の場合でも O(nlog2n) となり、これがヒープソートの最大の利点です。

【関連する推奨事項】

1.

Java での Selection Sort_java の詳細なサンプル チュートリアル

2. Java データ構造ソート アルゴリズム (2) マージ ソート

3. Java データ構造ソート アルゴリズム (3)選択ソート

4. Javaデータ構造ソートアルゴリズム (4) 選択ソート

以上がJava データ構造ソート アルゴリズム (1) ツリー選択ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。