java - 这是插入排序算法的可接受实现吗？

Question

以下插入排序算法的 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 在同一页上解释的那样:

A linked list is very efficient in adding elements in the middle of the list, simply by rearranging the pointers of the nodes in the list. If an ArrayList had been used, adding elements to the middle would be expensive. An ArrayList is backed by an array, so inserting at the front or middle of the list means that all subsequent elements must be shifted along by one to a new slot in the array. This can be very expensive if you have a list with several million rows, especially if you are inserting early in the list.

这是一个可以接受的实现吗？

Answer 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

来源:http://en.wikipedia.org/wiki/Insertion_sort

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

2) 该算法的工作原理是逐个元素交换，而不是将元素恰好插入到它应该位于的位置。注意:- 每次交换都是 o(1)。

3) 因此，在这种形式下，如果您使用列表，则需要执行 2 个操作，连接前一个元素和当前元素，反之亦然以及相邻元素。另一方面，排序数组只需要一个步骤。

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

Now, if the approach of insertion sort was directly inserting the current element at the place where it is fitting, a linked list would have worked better.

注意:- 排序数组或排序链表，整体过程是相同的，与排序不同的是中间步骤。