考虑以下伪代码进行插入排序：

for i ← 1 to length(A) - 1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

1）所以，在这个过程中，你持有每个元素，并将其与以前的元素进行比较，如果以前的元素大于当前元素，则交换，并且这种情况一直发生，直到条件不满足。

2）该算法的工作原理是逐个元素交换元素，而不是在应该的位置插入元素。注意：-每个交换都是 o（1）。

3）因此，在这种形式下，如果你使用一个列表，你有 2 个操作要做，连接前任和当前元素，反之亦然以及相邻的元素。

4）因此，在这种方法中，排序数组比列表更有意义。

现在，如果插入排序的方法是直接插入当前元素在它适合的地方，链表会更好。

注意：-一个排序的数组或排序的链表，整个过程将是相同的，它是中间步骤，使比排序的区别。

从理论上讲，Markham 的状态可能是很好的常识：在链表中插入不应该花费太多（分配一个新节点，一些引用分配），甚至在列表末尾插入是便宜的，因为LinkedList实际上是一个双链表，并在最后一个元素上保留一个引用。

插入一个新节点（对于LinkedList）和移动数组的一部分（对于ArrayList）之间的参数至少要进行测试，因为ArrayList#add(int i, E)使用System.arrayCopy()应该真正针对这种工作进行优化。

你可以在任何地方听到 / 看到“当心微基准”。嗯,我会说,当你想对正在发生的事情有一个粗略的了解时,微基准测试可以给你一些提示...

注意插入排序是平均O(N^2)，与tim 排序的Collections是O(Nlog(N))。

在插入排序的建议实现中，我只是传递排序列表实现，以便对两个测试使用相同的功能。

public static List<Integer> insertSort(final List<Integer> numbers,
                                       final List<Integer> sortedList) {
    //final List<Integer> sortedList = new ArrayList<>();
    originalList: for (Integer number : numbers) {
        for (int i = 0; i < sortedList.size(); i++) {
            if (number < sortedList.get(i)) {
                sortedList.add(i, number);
                continue originalList;
            }
        }
        sortedList.add(sortedList.size(), number);
    }
    return sortedList;
}

然后下面是一种方法，将测量排序随机整数列表所花费的时间并打印它：

public static List<Integer> bench(List<Integer> ints, String tag,
                                  Function<List<Integer>, List<Integer>> sortf) {
    long start = System.nanoTime();
    List<Integer> sortedInts = sortf.apply(ints);
    long end = System.nanoTime();
    System.out.println(String.format("type: %6s size: %7d time(ms): %5d", 
                                     tag, ints.size(), (end-start)/1000000));
    return sortedInts;
}

函数microBench()将循环增加数组大小，并用 3 种方法对相同的随机数组进行排序，并比较排序列表。

public static void microBench(int start, int end, int step) {
    for (int m = start; m <= end; m+=step) {
        List<Integer> ints = new Random()
             .ints(m, 0, m).boxed()
             .collect(Collectors.toList());
        List<Integer> l1 = bench(ints, "coll", (List<Integer> l) -> { 
            List<Integer> list = new ArrayList<>(l);
            Collections.sort(list);
            return list;
        });
        List<Integer> l2 = bench(ints, "array", (List<Integer> l) ->
            insertSort(l, new ArrayList<Integer>()));
        if (!l1.equals(l2)) {
            System.out.println("Oooops array");
        }
        List<Integer> l3 = bench(ints, "linked", (List<Integer> l) -> 
            insertSort(l, new LinkedList<Integer>()));
        if (!l1.equals(l3)) {
            System.out.println("Oooops linked");
        }
    }
}

所有这些都是从main调用的。从 500 的数组开始，然后增加大小直到5,000（确实很小！）。执行 env。是 MBP 2,5 GHz Intel Core i7。

public static void main(String[] args) {
    microBench(1000, 5000, 1000);
}
type:   coll size:    1000 time(ms):     1
type:  array size:    1000 time(ms):     8
type: linked size:    1000 time(ms):    66
type:   coll size:    2000 time(ms):     1
type:  array size:    2000 time(ms):     2
type: linked size:    2000 time(ms):   507
type:   coll size:    3000 time(ms):     2
type:  array size:    3000 time(ms):     4
type: linked size:    3000 time(ms):  2283
type:   coll size:    4000 time(ms):     1
type:  array size:    4000 time(ms):     9
type: linked size:    4000 time(ms):  6866
type:   coll size:    5000 time(ms):     1
type:  array size:    5000 time(ms):    13
type: linked size:    5000 time(ms): 14842

无需画图即可了解插入排序与LinkedList不是赢家！14 秒即可对 5000 个整数进行排序。但是插入排序与ArrayList并不是那么糟糕。

我卸下了LinkedList上的工作台，并以100,000的最大数组大小推了一下。

    microBench(10000, 100000, 10000);
type:  array size:   10000 time(ms):    70
type:   coll size:   20000 time(ms):     6
type:  array size:   20000 time(ms):   290
type:   coll size:   30000 time(ms):     8
type:  array size:   30000 time(ms):   382
type:   coll size:   40000 time(ms):     6
type:  array size:   40000 time(ms):   667
type:   coll size:   50000 time(ms):     7
type:  array size:   50000 time(ms):   984
type:   coll size:   60000 time(ms):     8
type:  array size:   60000 time(ms):  1521
type:   coll size:   70000 time(ms):    10
type:  array size:   70000 time(ms):  2172
type:   coll size:   80000 time(ms):    12
type:  array size:   80000 time(ms):  2729
type:   coll size:   90000 time(ms):    13
type:  array size:   90000 time(ms):  3587
type:   coll size:  100000 time(ms):    15
type:  array size:  100000 time(ms):  4528

4.5 秒 vs 15 毫秒。这并不奇怪，与 tim 排序 / 合并排序 O（NlogN）相比，插入排序仍然是 O（N ^ 2）...

由于 Markham 编写了大约 1,000,000 个元素数组，我只是在唯一的实现（从 3 个测试）上使用了长凳，它可以体面地做到这一点，并删除了插入排序ArrayList

    microBench(100000, 1000000, 100000);
type:   coll size:  100000 time(ms):    41
type:   coll size:  200000 time(ms):    36
type:   coll size:  300000 time(ms):    58
type:   coll size:  400000 time(ms):    82
type:   coll size:  500000 time(ms):   108
type:   coll size:  600000 time(ms):   126
type:   coll size:  700000 time(ms):   152
type:   coll size:  800000 time(ms):   178
type:   coll size:  900000 time(ms):   199
type:   coll size: 1000000 time(ms):   223

223 毫秒为 1,000,000。

结论，当心人们可以写什么，并在可以完成的时候测试自己！-顺便说一句，你的同事是对的。而且，如果你必须排序，插入排序，是通常不是要走的路。

您必须在内部循环性迭代链表，而不是get(i)，因为LinkedList不支持RandomAccess。否则，每个元素访问都需要i步骤来查找相应的元素和基准，因为在将实现与ArrayList进行比较时，另一个答案会产生误导性结果。

public static List<Integer> insertSort(final List<Integer> numbers) {
    final LinkedList<Integer> sortedList = new LinkedList<>();
    originalList: for (Integer number : numbers) {
        int i = 0;
        for (Integer compare : sortedList) {
            if (number < compare) {
                sortedList.add(i, number);
                continue originalList;
            }
            ++i;
        }
        sortedList.addLast(number);
    }
    return sortedList;
}