问题与插入排序代码

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