使用ListIterator编写插入排序

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class InsertionSort {
    public static void insertionSort(List<Integer> list) {
        ListIterator<Integer> iterator = list.listIterator();
        if (!iterator.hasNext()) {
            return;
        }
        iterator.next(); // Skip the first element as it is already considered sorted

        while (iterator.hasNext()) {
            int current = iterator.next();
            ListIterator<Integer> sortedIterator = list.listIterator(iterator.previousIndex());

            while (sortedIterator.hasPrevious() && sortedIterator.previous() > current) {
                // Move the elements greater than the current element one position to the right
                sortedIterator.next();
                sortedIterator.set(sortedIterator.previous());
            }
            sortedIterator.next(); // Move the iterator back to the correct position
            sortedIterator.set(current); // Insert the current element at the correct position
        }
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(5);
        list.add(2);
        list.add(8);
        list.add(1);
        list.add(9);

        System.out.println("Before sorting: " + list);
        insertionSort(list);
        System.out.println("After sorting: " + list);
    }
}