Java中高效地交换数组元素

Question

我想知道有没有比这种方法更有效的交换数组中两个元素的方式：

String temp = arr[1];
arr[1] = arr[2];
arr[2] = temp;

嗯，这显然不是坏事，甚至也不是错的，但我需要经常交换，所以我想知道是否有任何库或其他东西可以提供更高效的方法来做到这一点？

- Robin

---

对于字符串？不是真的。如果您需要经常这样做，最好自己编写一个函数，然后就不会麻烦了。 - Grambot

如果您可以使用List而不是Array，您可以使用Collections.swap(List, i, j)。 - Sergio Nakanishi

@Sergio Nakanishi：有趣的观点，也许我能够转向集合，但我不确定纯数组使用是否更快？ - Robin

@Robin：我通常更喜欢使用ArrayList而不是数组。ArrayList在内部使用一个数组，调用方法来操作数组的开销并不显著。《Effective Java》一书有更完整的理由来选择List而不是数组。 - Sergio Nakanishi

@SergioNakanishi 谢谢你的书籍推荐。我刚刚搜索了一下，看起来非常不错。 - Robin

这是最有效的方法之一。不同的替代方案在可读性上存在差异。在假设任何效率差异之前，先进行测量（使用适当的微基准测试框架）。 - greybeard

Answer 1

不行。您可以在使用它的每个地方都有一个函数使其更简洁，但最终完成的工作将是相同的（加上函数调用的开销，直到/除非HotSpot将其内联 - 为了帮助它，将函数设置为 static final）。

- T.J. Crowder

---

仅供记录，使用static final相比仅使用static或者不使用的好处是什么？ - Robin

@Robin: static 告诉编译器和虚拟机（记住，HotSpot 是虚拟机，它可以进行很多运行时优化）不需要担心设置 this，这使得函数更容易内联。final 表示它不会在子类中被覆盖。我可能对 HotSpot 对它们关注的程度有误解，实际情况可能有所不同，因为我不太了解 HotSpot 的最新技巧。 :-) - T.J. Crowder

我认为你无法重写一个静态方法。 - Sergio Nakanishi

@Sergio："我认为你不能覆盖一个静态方法。" 除了它是 "final" 之外，你是可以的，但这与覆盖实例方法非常不同。注意此错误覆盖static final(http://ideone.com/NuMyv4): "error: foo() in Derived cannot override foo() in Base...overridden method is static,final"。如果它不是“final”，则该错误将消失(http://ideone.com/vnuAk6)。只有在通过*实例引用*调用静态方法时才会出现这个错误，这是一件奇怪的事情。调用的方法从引用类型在编译时就已经确定：http://ideone.com/yXDgpa。 - T.J. Crowder

从技术上讲，子类中的静态方法并没有被覆盖，而是被隐藏了。 - Denis Nikolaenko

Answer 2

这应该会使它无缝：

public static final <T> void swap (T[] a, int i, int j) {
  T t = a[i];
  a[i] = a[j];
  a[j] = t;
}

public static final <T> void swap (List<T> l, int i, int j) {
  Collections.<T>swap(l, i, j);
}

private void test() {
  String [] a = {"Hello", "Goodbye"};
  swap(a, 0, 1);
  System.out.println("a:"+Arrays.toString(a));
  List<String> l = new ArrayList<String>(Arrays.asList(a));
  swap(l, 0, 1);
  System.out.println("l:"+l);
}

- OldCurmudgeon

---

这个很好用，谢谢。请注意，这需要一个对象数组，所以如果你遇到一些奇怪的编译错误，请确保使用 Integer[] array 而不是 int[] array。 - LostNomad311

Answer 3

如果你在交换数字并且想以简洁的方式书写代码，而不必创建单独的函数或使用令人困惑的异或运算符技巧，我认为下面这种方法更容易理解，而且只需要一行代码。

public static void swap(int[] arr, int i, int j) {
    arr[i] = (arr[i] + arr[j]) - (arr[j] = arr[i]);
}

从一些基本的基准测试结果来看，性能差异基本可以忽略不计。

这是交换数组元素而不使用临时变量的标准方法之一，至少对于整数来说如此。

- kmecpp

---

但是 arr[i] + arr[j] 可能会导致溢出。 - lin

@ChaojunZhong 这不应该是个问题。当另一个数字被减去时，新的 [i] 将被正确计算。在 IDE 中尝试一下。 - kmecpp

Answer 4

如果你想交换字符串，那么现在已经有了高效的方法。

然而，如果你想要交换整数，可以使用异或来更加高效地交换两个整数，像这样：

int a = 1; int b = 2; a ^= b; b ^= a; a ^= b;

- bhuang3

---

你用了哪些测试来对这个进行基准测试，速度有多大提升？ - djechlin

@bhuang3 - 请修改您的帖子，解释为什么Java编译器不执行此优化。我当然怀疑它会执行，因此提出了DV。 - djechlin

@djechlin 我并不考虑编译器优化.. 我只是在谈论编程。 - bhuang3

那样的代码更长、更混乱、更难读，而且需要更多的代码行。我想这在堆栈上声明变量的资源方面可能更有效率，但没有理由认为 OP 是在寻求这种资源的优化，所以 DV 就不必要了... - djechlin

@Robin，欢迎您，但是正如“djechlin”所说，这种方式很难理解和阅读，它只是一种编程技巧。另外，如果两个整数指向同一个地址，可能会有一些问题，但在Java中，内存分配由JVM处理，因此很难说这种方式是否实用。 - bhuang3

Answer 5

使用 Collections.swap 和 Arrays.asList：

Collections.swap(Arrays.asList(arr), i, j);

- ZhekaKozlov

---

如果数组中的类型是基本类型，那么这将无法起作用。Arrays.asList(int[])会将其转换为int[]列表。 - jeffery.yuan

我能知道为什么它不能使用原始类型吗？实际上，对我来说它不起作用，需要知道原因。 - Akhil kumar Amarneni

Answer 6

原地交换（如果您还不知道）可以通过不创建临时变量来节省一些空间。

arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];

- Neel Alex

Answer 7

非常晚才到场（抱歉），但是比这里提供的更通用的解决方案可以实现（适用于原始数据类型和非原始数据类型）。

public static void swap(final Object array, final int i, final int j) {
    final Object atI = Array.get(array, i);
    Array.set(array, i, Array.get(array, j));
    Array.set(array, j, atI);
}

你会失去编译时安全性，但这应该可以解决问题。

注意1：如果给定的数组为 null，则会出现 NullPointerException；如果给定的array不是一个数组，则会出现 IllegalArgumentException；如果任一索引对于给定的array无效，则会出现 ArrayIndexOutOfBoundsException。

注意2：为每种数组类型（Object[]和所有原始类型）单独设置此方法将更加高效（使用此处提供的其他方法），因为这需要一些装箱/拆箱。但也需要编写/维护大量代码。

- BeUndead

Answer 8

public static final void swap (int[] a, int i, int j) {
    a[i] = a[i] + a[j];
    a[j] = a[i] - a[j];
    a[i] = a[i] - a[j];
}

- Anil

---

与Neel Alex的回答相比，有什么区别细节？ - greybeard

Answer 9

试试这个：

    int lowIndex = 0;
    int highIndex = elements.length-1;

    while(lowIndex < highIndex) {
        T lowVal = elements[lowIndex];
        T highVal = elements[highIndex];
        elements[lowIndex] = highVal;
        elements[highIndex] = lowVal;

        lowIndex += 1;
        highIndex -=1;
    }

- J.user94

---

这个问题试图回答什么？为什么这会更可取？ - greybeard

Answer 10

首先，你不应该写成for (int k = 0; k **<** data.length **- 1**; k++)，因为<是直到k小于长度-1的时候才会停止循环，这将导致循环到数组的最后一个位置而无法得到最后一个位置的元素； 你可以通过两种方式解决： 1：for (int k = 0; k <= data.length - 1; k++) 2：for (int k = 0; k < data.length; k++)，这样就可以正常工作了！ 要交换，你可以使用：将其中一个整数放在另一个位置，然后进行替换。

int x = data[k]
data[k] = data[data.length - 1]
data[data.length - 1] = x;

因为你不想丢失其中一个整数！！

- viper-zero

---

这个问题试图回答什么？ - greybeard