java - 什么算法更有效地移动 java 数组中的每个元素？

Question

这是我做的第一个算法:

int tmp = null;
for (int i = arr.length-1; i > 0; i--){
    tmp = arr[i];
    arr[i] = arr[i-1];
    arr[i-1] = tmp;
}

这是我的计算机老师对我说的第二个算法:

int tmp = null;
for (int i = arr.length-1; i > 0; i--){
    for(int j = 0; j < arr.length; j++){
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    }
}

帮我看看哪个更有效率。在我的实验中使用

System.currentTimeMillis();

这个方法有一个包含 100000 个数据的数组，第一个算法更快，但我的老师说第二个算法在包含各种事物的更大数据库中会更快。我知道 LinkedList 会很好，但我想知道这个问题。

Answer 1

算法 do different things :

Input: [1, 2, 3, 4, 5]
First: [5, 1, 2, 3, 4]
Second: [3, 4, 1, 2, 5]

因此，任何关于它们相对效率的讨论都是无关紧要的，因为它们在功能上并不相同。

---

但是，就某事所花费的时间而言，第一个算法是O(n)，而第二个是O(n^ 2)。因此，随着输入大小的增长，执行第一个所花费的时间将比第二个增长得更慢，所以你的老师错了。

---

请注意，第一个做了很多不必要的工作:它反复交换数组的最后一个元素，一直到数组的开头。因此，它可以像这样更快地完成:

int tmp = arr[arr.length - 1];
for (int i = arr.length - 1; i > 0; --i) {
  arr[i] = arr[i - 1];
}
arr[0] = tmp;