0

実装 1: (for ループを使用しますが、while ループでシフトします)

public class Insertionsort{
public static void main(String[] args) {
    int a[] = {10,9,8,7,6,5,4,3,2,1};
    for (int i = 1; i < a.length; i++){
        int j = i;
        int B = a[i];
        while ((j > 0) && (a[j-1] > B)){
            a[j] = a[j-1];
            j--;
        }
        a[j] = B;
    }
    for(int i = 0; i <a.length; i++)
          System.out.print(a[i]+"  ");
    }
}

実装 2: 3 つの for ループを使用

public class InsertionSort {
    public static void main(String[] args) {
       int a[] = {10,9,8,7,6,5,4,3,2,1};

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

最も内側のループの反復回数は間違いなく少ないですが、両方のアルゴリズムがまったく同じか、最初のアルゴリズムの方が優れているかはわかりません。判断にお役立てください。

4

1 に答える 1

1

結局、これらの実装はどちらも配列をソートし、挿入ソートです (ただし、2 番目の実装はバブル ソートといくつかの類似点を共有しています)。

最初の実装は、2 番目の実装よりも優れています。最初のものはO（N ^ 2）時間実行されますが、2番目のものはO（N ^ 3）です。より賢明な選択は、最初の実装を使用することです

于 2013-02-27T04:54:09.773 に答える