java - 文本中是否存在插入排序错误？

Question

我正在通读下面引用的教科书，发现以下插入排序代码对我来说似乎有缺陷，但我想在报告之前征求第二意见，因为这本书已经出版一段时间了，我没有看到一份报告。

插入排序应该是有序集合上的 O(n)，但是这个看起来像是有序集合上的 O(n^2)，因为它遍历了外循环中除第一个元素之外的所有元素，然后所有直到外循环的元素在内循环中计数。

这样说是否应该修改内部循环以从右到左检查以便在输入排序时只比较最右边的元素？

// Sort an array using a simple insertion sort.
public void insertionSort(int[] data) {
    for (int which = 1; which < data.length; ++which) {
        int val = data[which];
        for (int i = 0; i < which; ++i) {
            if (data[i] > val) {
                System.arraycopy(data, i, data, i + 1, which - i);
                data[i] = val;
                break;
            }
        }
    }
}

约翰·蒙根 (2012-11-14)。公开的编程面试:找到下一份工作的 secret (Kindle 位置 3460-3464)。威利。 Kindle版。

Answer 1

内循环应该在reversed检查。插入排序只处理数组中从已排序元素末尾开始的已排序元素。要获得视觉和代码解释....检查此 http://visualgo.net/sorting.html