1

我阅读了 Cormen&Co 的“算法简介”并在 java 上实现了算法。我想知道在最终方法中写入插入排序代码 if 语句是否有意义set()？如果可能的话，我想让代码更快。

public static void insertion(List<Integer> a) {
    List<Integer> aList = a;
    int temp;
    int previousIndex;

    for (int i = 1; i < aList.size(); i++) {
        temp = aList.get(i);
        previousIndex = i - 1;
        while ((previousIndex >= 0) && aList.get(previousIndex) > temp) {
            aList.set(previousIndex + 1, a.get(previousIndex));
            previousIndex--;
        }

        //if(aList.get(previousIndex + 1) > temp){
            aList.set(previousIndex + 1, temp);
        //}

    }
}

对不起，如果它是初级的。我非常初学者。

4

1 回答 1

3

这看起来像是在尝试优化代码，使其更快。显而易见的想法是对数据进行测试以避免设置它。仅当 (1) 读取和测试值比设置值更快并且 (2) 有足够多的情况下测试将避免设置值时，这才会使执行更快。

IMO（1）是可疑的，（2）需要经常进行才能节省很多时间，我认为情况并非如此。

通过测试 (previousIndex + 1 != i) 而不是 (aList.get(previousIndex + 1) > temp) 可以实现更好更快的测试，如果列表对象的复制量很大，这可能是一个很好的优化更耗时，例如复制复杂的对象结构。但是，在这种情况下，我们谈论的是整数对象，所以我认为添加测试只会在所有情况下减慢速度。

当然，正如所有优化的情况一样，只有现实生活中的测量才能说明什么是有效的，这就是为什么优化总是最后要做的事情，而且只有在必要时才做。

于 2012-08-26T19:05:56.023 回答