在java排序算法比較記錄元素

Question

您好我正在使用下面的插入排序算法，我想記錄被比較的元素。基本上我想比較存儲在兩個數組列表，arrList1和arrList2。如果一個元素在它的正確位置，那麼這兩個數組列表將具有相同的元素。如果不是，那麼arrList1將具有所選元素，而arrayList2將具有其自身比較的元素。我目前正在努力做到這一點，所以我想知道有沒有人可以幫忙？由於

public static ArrayList<Integer> arrList1 = new ArrayList<Integer>(); 
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>(); 
... 
     public static void insertSort(int[] A){ 
     for(int i = 1; i < A.length; i++){ 
     int value = A[i]; 
     int j = i - 1; 
     while(j >= 0 && A[j] > value){ 
      A[j + 1] = A[j]; 
      j = j - 1; 
     } 
     A[j + 1] = value; 
     } 
    } 

編輯： 例如：如果進行比較時，我的數組有數字1,3,2,4,6,5那麼，這是我多麼希望我的兩個數組列表看：

 arrList1 arrList2 
#1  1   1 
#2  3   3 
#3  2   3 (As 2 goes before 3 then it must be compared to 3) 
#4  4   4 
#5  6   6 
#6  5   6 (As 5 is lower then 6 then it must be compared to 6) 

排序後的數組：1，2，3，4，5，6

正如你可以看到，arrList1基本輸入陣列，同時arrList2的順序是比較它如果它不是在正確的位置上的元素。如果它在正確的位置，那麼arrList 2將是相同的值。

Answer 1

有你有...

public class Test { 
    public static List<Integer> arrList1; 
    public static ArrayList<Integer> arrList2 = new ArrayList<Integer>(); 

    public static void main (String... args){ 
     Integer[] toSort = {1, 3, 2, 4, 6, 5}; 


     arrList1 = Arrays.asList(Arrays.copyOf(toSort, toSort.length)); 
     insertSort(toSort); 

     List<Integer> sortedArray = new ArrayList<Integer>(); 
     for(int aux: toSort){ 
      sortedArray.add(aux); 
     } 

     System.out.println("Array list 1: " + arrList1); 
     System.out.println("Array list 2: " + arrList2); 
     System.out.println("Sorted array: " + sortedArray); 
    } 

    public static void insertSort(Integer[] A){ 
     arrList2.add(arrList1.get(0)); 
     for(int i = 1; i < A.length; i++){ 
      int value = A[i]; 
      int j = i - 1; 
      if ((j >= 0 && A[j] > value)){ 
       arrList2.add(A[j]); 
      }else{ 
       arrList2.add(A[i]); 
      } 
      while(j >= 0 && A[j] > value){ 
       A[j + 1] = A[j]; 
       j = j - 1; 
      } 

      A[j + 1] = value; 
     } 
    } 
} 

此代碼爲我的輸出是：

數組列表1：[1,3，2，4，6，5] Array list 2：[1,3,4,6,6] Sorted array：[1,2,3,4,5,6]

Answer 2

編輯：現在，我明白這裏的問題是我的建議。首先要注意的是，插入排序具有sqare（O（n^2））複雜度，所以相同複雜度的另一個計算不會改變算法的整體複雜度。所以這裏是你做的 - 首先你通過遍歷當前元素左邊的所有值並搜索第一個大於當前元素的值來計算arrList2中的值。第二個階段就是排序算法 - 正如你已經指出的那樣，arrList1保存了排序的A.整個事情可以用更好的複雜性實現，但不能使用插入排序。

public static ArrayList<Integer> arrList1 = new ArrayList<Integer>(); 
public static ArrayList<Integer> arrList2 = new ArrayList<Integer>(); 
... 
public static void insertSort(int[] A){ 
    for (int i = 0; i < A.length; ++i) { 
    boolean found_greater = false; 
    for (int j = i - 1; j >= 0; --j) { 
     if (A[j] > A[i]) { 
     found_greater = true; 
     arrList2.add(A[j]); 
     break; 
     } 
    } 
    if (!found_greater) { 
     arrList2.add(A[i]); 
    } 
    } 

    for(int i = 1; i < A.length; i++){ 
    int value = A[i]; 
    int j = i - 1; 
    while(j >= 0 && A[j] > value){ 
     A[j + 1] = A[j]; 
     j = j - 1; 
    } 

    arrList1.add(A[i]); 
    A[j + 1] = value; 
    } 
}