ソートの効率は一般に、データの比較回数、データの移動回数、メモリ占有量の 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[1..i] はソートされており、i 回目の処理が終了します。
それ以外の場合は、L[i] と L[i-1] の位置を交換し、特定の位置 j (1≤j≤i-1) が一致するまで L[i-1] と L[i-2] の比較を続けます。見つかった。
L[j] ≤L[j+1] になるまで
利点: 移動する要素が少なく、補助スペースのみが必要です
時間計算量 n*n
これは、並べ替えるレコードの数 n が小さい場合に適した並べ替え方法です。ただし、n が非常に大きい場合は不適切です
例: int[] 値 = { 5, 2, 4, 1, 3 };
選別プロセス:
1回目：2,5,4,1,3
2回目：2,4,5,1,3
3回目：1,2,4,5,3
4回目：1,2,3,4,5
Javaコード:
次のようにコードをコピーします。
パブリック クラス InsertSort {
public static void main(String[] args) {
int[] 値 = { 5, 2, 4, 1, 3 };
並べ替え(値);
for (int i = 0; i < 値.length; ++i) {
System.out.println(values[i]);
}
}
public static void sort(int[] 値) {
内部温度;
int j = 0;
for (int i = 1; i < 値.length; i++) {
if(values[i]<values[i-1])//ここでの判断は非常に重要であり、挿入ソートがバブル ソートや選択ソートよりも高速である理由を反映しています。
{
temp = 値[i];
//データを後方に移動します
for (j=i-1; j>=0 && temp<values[j]; j--)
{
値[j+1] = 値[j];
}
//位置 j+1 にデータを挿入
値[j+1] = 温度;
System.out.print("th" + (i + 1) + "th:");
for (int k = 0; k < value.length; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}
2番目の例
次のようにコードをコピーします。
パッケージ cn.cqu.coce.xutao;
パブリッククラス zhijiecaru {
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])
壊す;
if(j!=i-1){
内部温度;
temp=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=温度;
}
}
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
}
}