以下插入排序算法的 Java 实现出现在 Noel Markham 的Java Programming Interviews Exposed的第 28 页：
public static List<Integer> insertSort(final List<Integer> numbers) {
final List<Integer> sortedList = new LinkedList<>();
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;
}
我的一个同事了这个代码,发现它作为对“请实现插入排序算法”提出的面试问题的回应是不可接受的。他觉得数组将是排序列表的更合适的数据结构。但是,正如 Markham 在同一页上解释的那样:
链表在列表中间添加元素时非常有效，只需重新排列列表中节点的指针即可。如果使用了 ArrayList，则将元素添加到中间会很昂贵。ArrayList 由数组支持，因此在列表的前面或中间插入意味着所有后续元素必须移动一个到数组中的新插槽。如果您在列表中有几百万行，这可能非常昂贵
这是一个可以接受的实现吗？
1
考虑以下伪代码进行插入排序：
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）因此，在这种方法中，排序数组比列表更有意义。
现在，如果插入排序的方法是直接插入当前元素在它适合的地方，链表会更好。
注意：-一个排序的数组或排序的链表，整个过程将是相同的，它是中间步骤，使比排序的区别。
1
从理论上讲，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。
结论，当心人们可以写什么，并在可以完成的时候测试自己！-顺便说一句，你的同事是对的。而且，如果你必须排序，插入排序，是通常不是要走的路。
0
您必须在内部循环性迭代链表，而不是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;
}
本站系公益性非盈利分享网址，本文来自用户投稿，不代表码文网立场，如若转载，请注明出处
评论列表（42条）