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

この記事では、主に Java データ構造とアルゴリズム選択ソートの単純さを紹介し、サンプルの形で選択ソートの原理、実装方法、および関連する操作テクニックを分析します。 Java データと例 単純な選択ソートの構造とアルゴリズム。参考のために皆さんと共有してください。詳細は次のとおりです。

前の記事で、交換クラスのソート アルゴリズムについて説明しました。このセクションでは、選択クラスのソート アルゴリズムについて説明します。まず、選択ソートのアルゴリズムのアイデアを見てみましょう。 +1 (i=1,2,3,...,n-1) レコードは、シーケンス内の i 番目のレコードとして記録されます。

単純な選択ソート: ソートされたシーケンス内のレコードの数が n であると仮定します。 i は 1,2,…,n-1 をとり、n-i+1 個のすべてのレコード (Ri、Ri+1、…、Rn) からソート コードが最も小さいレコードを見つけて、それを i 番目のレコードと交換します。 n-1回実行すると、レコード列のソートが完了します。

アルゴリズムの実装コードは次のとおりです:

package exp_sort;
public class SimpleSelectSort {
  static int i;
  static int temp;
  public static void selectSort(int array[]) {
    for (i = 0; i < array.length; i++) {
      int k = i;  //记录当前位置
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[k]) {   //找出最小的数，并用k指向最小数的位置
          k = j;
        }
      }
            //交换最小数array[k]与第i位上的数
      if (k != i) {
        temp = array[i];
        array[i] = array[k];
        array[k] = temp;
      }
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    selectSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
}

アルゴリズム分析:

この並べ替えプロセスでは、移動する必要があるレコードの数は比較的少ないです。最良の場合、つまり、ソートされるレコードの初期状態がすでに正の順序になっている場合、最悪の場合、つまり、ソートされるレコードの初期状態が正の順序になっている場合、レコードを移動する必要はありません。逆の順序では、必要な最大手数は 3 ( n-1) です。ソート処理の際に必要な比較回数は、初期状態でのソート対象のレコード列の並びとは無関係である。 i=1 の場合、n-1 回の比較が必要です。i=n の場合、必要な比較の合計数は n(n-1)/2、つまり比較演算の時間計算量は O( n^ 2)、移動操作の時間計算量は O(n) です。このソートは

不安定なソート

です。 【関連おすすめ】1.

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

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

3.

選択ソートの詳細説明Java (選択ソート_java) サンプルチュートリアル

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

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