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; 
     } 
    } 
}