Java直接挿入ソートの例-＆＃＆チュートリアル-php.cn

Java直接挿入ソートの例

高洛峰

リリース： 2016-12-29 15:57:08

オリジナル

1417 人が閲覧しました

ソート効率に影響を与える要素は、一般に、データ比較の数、データの移動数、占有されるメモリ領域の量の 3 つの側面から比較されます。
バブルソート、選択ソート、挿入ソート、クイックソートの一般的な比較をしてみましょう。バブルソートアルゴリズムは、数あるソートアルゴリズムの中で比較回数や移動回数が最も多いため、一般的には使用されません。唯一の利点は、アルゴリズムがシンプルで理解しやすいため、データ量が少ない場合に使用できることです。何らかのアプリケーション値になります。選択ソートはバブルソートと同じn乗の比較回数ですが、交換回数が最小限に抑えられるため、データ量が少なく、比較よりもデータの交換に時間がかかる場合に適用できます。データの並べ替えを選択します。
ほとんどの場合、データの量が比較的少ない場合、または基本的に順序付けされている場合は、挿入ソートアルゴリズムが最適な選択です。大量のデータを並べ替えるには、通常、クイックソートが最適な方法です。
上記の並べ替えアルゴリズムはメモリ領域をほとんど消費せず、交換中にデータ項目を一時的に保存するための追加の変数のみが必要です。したがって、占有されるメモリ空間のサイズは比較できません。

挿入ソートの比較回数は依然として n 乗ですが、一般にバブルソートの 2 倍、選択ソートよりもわずかに高速です。これは、クイックソートなどの複雑な並べ替えアルゴリズムの最終段階でよく使用されます。

アルゴリズム: i-1 処理後、L[1..i-1] がソートされています。 i 番目の処理パスでは、L[i] を L[1..i-1] の適切な位置に挿入するだけで、L[1..i] が再びソートされたシーケンスになります。この目標を達成するには、逐次比較を使用します。
まず、L[i] と L[i-1] を比較します。L[i-1] それ以外の場合は、L[i] と L[i-1] の位置を交換し、特定の位置 j (1≤j≤i-1) になるまで L[i-1] と L[i-2] の比較を続けます。 ) が見つかるまで
L[j] ≤L[j+1] まで
利点: 移動する要素が少なく、必要な補助スペースは 1 つだけ
時間計算量 n*n
ソートするレコードの数 n が小さい場合、これは素晴らしい並べ替え方法です。ただし、n が非常に大きい場合は適切ではありません。例: int[] 値 = {5, 2, 4, 1, 3}; 2 回目: 2,4,5,1,3
3 回目: 1,2,4,5,3

4 回目: 1,2,3,4,5

Java コード:

public class InsertSort {
   public static void main(String[] args) {
       int[] values = { 5, 2, 4, 1, 3 };
       sort(values);
       for (int i = 0; i < values.length; ++i) {
           System.out.println(values[i]);
       }
   }
   public static void sort(int[] values) {
       int temp;
       int j = 0;
       for (int i = 1; i < values.length; i++) {
           if(values[i]<values[i-1])//此处的判断很重要，这里体现了插入排序比冒泡排序和选择排序快的原因。
           {
               temp = values[i];
               //数据往后移动
               for (j=i-1; j>=0 && temp<values[j]; j--)
               {
                   values[j+1] =values[j];
               }
               //将数据插入到j+1位置
               values[j+1] =temp;
               System.out.print("第" + (i + 1) + "次：");
               for (int k = 0; k < values.length; k++) {
                   System.out.print(values[k]+",");
               }
               System.out.println("");
           }
       }
   }
}

ログイン後にコピー

回 2 つの例

package cn.cqu.coce.xutao;
public class zhijiecharu {

 public static void main(String args[]){

 int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
 int i,j,k;
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"\t");
 System.out.println();
 for(i=1;i<a.length;i++){

  for(j=i-1;j>=0;j--)
   if(a[i]>a[j])
    break;

  if(j!=i-1){
   int temp;
   temp=a[i];
   for(k=i-1;k>j;k--)
    a[k+1]=a[k];
   a[k+1]=temp;  
  }  
 }
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"\t");
 System.out.println();
  }
}

ログイン後にコピー

その他の Java 直接挿入ソートの例についてはおよび関連記事については、PHP 中国語 Web サイトにご注目ください。

Java直接挿入ソートの例