Java 挿入ソートの簡単な例

この記事では主に Java の単純な挿入ソートの例を詳しく紹介します。興味のある方は参考にしてください

1. 基本概念

挿入ソートの基本的な操作は、ソートされたデータにデータを挿入することです。このアルゴリズムは、少量のデータを並べ替えるのに適しており、時間計算量は O(n^2) です。安定した選別方法です。挿入アルゴリズムは、ソートされる配列を 2 つの部分に分割します。最初の部分には、最後の要素を除く配列のすべての要素が含まれます (配列に挿入位置を確保するためのスペースが 1 つ増えます)。2 番目の部分には、この要素のみが含まれます。要素 (つまり、挿入される要素)。最初の部分がソートされた後、この最後の要素がソートされた最初の部分に挿入されます。

2. Java コードの実装

public class InsertSort {
  public static void inserSort(int[] array){
    if (array==null||array.length<2){
      return;
    }

    for (int i=1;i<array.length;i++){ //默认第一个元素为有序队列，从第二个元素开始循环插入
      int position=array[i];     //设置第二个元素为要插入的数据
      int j=i-1;
      while (j>=0&&position<array[j]){
        array[j+1]=array[j];   //如果插入发数小于第j个元素，将第j个数向后移
        j--;
      }
      array[j+1]=position;     //插入
    }
  }

  public static void main(String ags[]){
    int[] array={2,6,4,7,3,-1};
    inserSort(array);
    for (int i=0;i<array.length;i++){
      System.out.print(array[i]+" ");
    }
  }
}

3. パフォーマンス分析

安定

空間計算量 O(1)
時間計算量 O(n2)
最悪の場合: n* を移動する必要がある(n-1)/2 要素
ベストケース: 正の順序、要素を移動する必要はありません

以上がJava 挿入ソートの簡単な例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。