問題與插入排序代碼

Question

我正在寫一個插入排序法，我碰到了一些麻煩 -

private int getInsertionPosition(int currPos){ 
    int val = this.toSort.get(currPos); 
    int index = currPos; 
    for(int i = 0; i < currPos; i++){ 
     if(val < this.toSort.get(i)){ 
      index = i; 
     } 
    } 
    return index; 
} 
private void move(int from, int to){ 
    int num = toSort.get(from); 
    toSort.remove(from); 
    toSort.add(to, num); 
    System.out.println("Moved " + from + " to " + to); 
} 
public void performSort(){ 
    for(int i = 1; i < original.length; i++){ 
     move(i,getInsertionPosition(i)); 
     System.out.println(this.toSort.toString()); 
    } 

} 

我在那裏有一對夫婦調試線，打印出什麼指數它的移動的元素陣列列表從/到。

不過，我得到怪異操作，其中有時它的移動看似任意值到錯誤的索引，即

「 [7，18，29，3，2，4，24，18，18，13] 移至3比2 [7，18，3，29，2，4，24，18，18，13] 「

任何幫助？我99％確定問題出在getInsertionPosition方法。

Answer 1

是的你的問題在getInsertionPoint。您需要返回值大於該值的第一個索引。目前您正在返回大於該值的最後一個索引。

嘗試：

private int getInsertionPosition(int currPos) { 
    for (int i = 0; i < currPos; i++) { 
     if (toSort.get(currPos) < this.toSort.get(i)) { 
      return i; 
     } 
    } 
    return currPos; 
} 

另外，如果您熟悉Java 8流：

return IntStream.range(0, currPos) 
    .filter(i -> toSort.get(currPos) < toSort.get(i)) 
    .findFirst().orElse(currPos);