Java插入排序 - 向下複製值

Question

我需要使此插入排序函數實質上將元素向右複製，直到需要移動的值位於正確的位置，但是，使用我正在使用的代碼通常最終會出現垃圾，並嘗試多次迭代獲得相同的結果。我無法理解爲什麼這不應該起作用。

public static void Sort(Comparable[] a) { 
    int n = a.length; 
    Comparable temp = 0; 
    int x; 
    // Starting with the element at index 1... 
    for (int i = 1; i < n; i++) { 
     // ...move to the left until we find one less 
     // than the current element. 
     for (int j = i; j > 0; j--) { 
      if (less(a[j], a[j - 1])) 
      { 
       temp = a[j]; 
       for(x = j; x > 0 && less(temp, a[x]); x--) 
       { 
        a[x] = a[x - 1]; 
       } 

       a[x] = temp; 
       //exch(a, j, j - 1); 
      } 
      else 
       break; 
     } 
    } 
} 

減（a，b）順便檢查一下< b。

Answer 1

在最內層循環的第一次迭代中，在這種情況下：x > 0 && less(temp, a[x])您正在檢查剛剛存儲在temp中的值是否小於剛剛存儲在temp中的值，用另一個名稱引用。這將始終返回false，導致循環永遠不會啓動。最終的結果是整個方法是一個昂貴的無操作。如果你正在通過隨機混亂的數組發送來測試它，那麼當數組完成時，數組仍會隨機混亂。

要解決這個問題，只需從該條件中的索引中減去1，使其成爲x > 0 && less(temp, a[x - 1])。

其餘的代碼看起來是正確的，我認爲，儘管與j循環是多餘的，可以刪除。

Answer 2

這應該做的伎倆

public static void Sort(Comparable[] a) { 
    int n = a.length; 
    Comparable temp = 0; 
    int x; 
    // Starting with the element at index 1... 
    for (int i = 1; i < n; i++) { 
     // ...move to the left until we find one less 
     // than the current element. 
     for (int j = i; j > 0; j--) { 
      if (less(a[j], a[j - 1])) 
      { 
       temp = a[j]; 
       for(x = j; x > 0 && less(temp, a[x-1]); x--) 
       { 
        a[x] = a[x - 1]; 
       } 

       a[x] = temp; 
       //exch(a, j, j - 1); 
      } 
      else 
       break; 
     } 
    } 
}