用 ListIterator 写插入排序

Question

我正在尝试编写一个插入排序方法，该方法接受一个整数列表并使用 ListIterator 对其进行升序排序。我在我的主要方法上尝试了运行方法以查看它是否有效，但我最终遇到了一堆错误。我想知道我犯了哪些错误以及您将如何编写代码。方法如下：

public static void insertionsort(LinkedList<Integer> arr){
ListIterator<Integer> it = arr.listIterator();
while(it.hasNext()){
  while(it.hasPrevious()){
    Integer curr = it.next();
    it.previous();
    Integer prev = it.previous();
    if(curr<prev){
      it.set(curr);
      it.next();
      it.next();
      it.set(prev);
    }
  }
  it.next();
}

}

这里是主要方法：

public static void main(String[] args){
LinkedList<Integer> a = new LinkedList<Integer>();
a.add(40);
a.add(30);
a.add(20);
a.add(10);
a.add(5);
insertionsort(a);
ListIterator<Integer> i = a.listIterator();
while(i.hasNext()){
  System.out.println(i.next());
}

}

Answer 1

当这个条件

curr<prev

不满足你进入无限循环，因为你正在离开光标 at the same place。

你可以这样做虽然效率不是很高（但仍然是插入排序），但很容易理解：

    ListIterator<Integer> iter = arr.listIterator();
    Integer current = iter.next();
    Integer next = null;
    while (iter.hasNext()) {
        if (!iter.hasPrevious() && next != null) {
            //insertion into sorted sublist
            while (iter.hasNext() && iter.next() < next) ;
            iter.previous();
            iter.add(next);
        }
        next = iter.next();
        //nothing to do, keep going
        if (next >= current) {
            current = next;
        } else {
            //remove misplaced element, and check where to put it
            iter.remove();
            //we can go backwards and check or move to the beginning and keep checking
            iter = arr.listIterator();
            current = next;
        }
    }

用 ListIterator 写插入排序

Writing Insertion Sort with ListIterator

java

sorting

iterator

list

insertion