问题与插入排序代码
问题描述:
我正在写一个插入排序法,我碰到了一些麻烦 -问题与插入排序代码
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方法。
答
是的你的问题在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);
你应该学习如何使用调试器。 –