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

最后，这两种实现都对数组进行排序并且都是插入排序（尽管第二种实现与冒泡排序有一些相似之处）。

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

于 2013-02-27T04:54:09.773 回答