java - 以下插入排序实现之间的区别

Question

实现 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]+" ");
        }
    }
}

最内层循环的迭代次数肯定较少，但我不确定这两种算法是否完全相同，还是第一种更好。请帮助决定。

Answer 1

最后，这两种实现方式都是对数组进行排序，而且都是插入排序(虽然第二种实现方式与冒泡排序有一些相似之处)。

第一个实现比第二个好。第一个运行 O(N^2) 时间，而第二个运行 O(N^3)。更明智的选择是使用第一个实现