不覆盖原有数组的最快排序方法

Question

我想在Java中对一个int[] 数组进行排序，但是将排序后的数组存储为新数组而不是覆盖原数组。

最明显的方法似乎是创建该数组的副本，然后对该新数组进行排序，如下所示：

int[] a2 = new int[a.length];

for (int i = 0; i < this.length; i++) {
    a2[i] = a[i];
}

Arrays.sort(a2);

然而，是否有更快的方法？我们能否在将旧数组元素复制到新数组的同时进行排序呢？

- hcaulf

Answer 1

你可以使用

int[] a2 = IntStream.of(a).sorted().toArray();

但我怀疑它不会比这个更快

int[] a2 = a.clone();
Arrays.sort(a2);

不管怎样，它的复杂度是相同的，因此不要期望速度提高超过一个常数因子。

- aioobe

Answer 2

在迭代旧数组时对新数组进行排序不会更快。为此，您可以使用System.arraycopy()而不是创建自己的排序或复制函数。

从指定的源数组开始位置复制到目标数组的指定位置的数组。

示例：

int[] a1 = new int[]{1,2,3,4,5};  // I suppose a1...
int[] a2 = new int[a1.length];

System.arraycopy( a1, 0, a2, 0, a1.length );

Arrays.sort(a2);

---

更新： 只要你在寻求对数组进行排序的更快方法，正如你所看到的，关于复制还是实时排序哪种更好的讨论很长。因此，您可以尝试进行一些基准测试。但是，如果您使用复制来进行排序，您将发现这取决于数组的大小和元素的全部。

- Jordi Castilla

---

好的，但问题是如何避免首次复制。如果你打算复制，那么更简洁的方法是使用int[] a2 = Arrays.copyOf(a1, a1.length)。 - Thilo

有没有更快的方法在迭代时进行排序？这是OP的问题，你可以猜测如何实现更快的方式。 - Jordi Castilla

我们在将旧数组的元素复制到新数组时，可以同时进行排序吗？ - T.J. Crowder

但要更快！OP询问是否有更快的方法，猜测在迭代时进行排序可能会更快... - Jordi Castilla

Answer 3

int[] a2 = IntStream.of(a).sorted().toArray();

将数组a进行排序，并将结果存储在新的数组a2中。

- Milap Jethwa

Answer 4

如果您倾向于使用TreeSet，以下代码可能会达到目的：

TreeSet<Integer> copied = new TreeSet<>();
for (int i = 0; i < array.length; i++) {
    copied.add(i);
}

我尝试测试差异，实际上这取决于数据的大小以及数组中的数据。

然而，我无法评论此方法的确定性，但我肯定会运行几个实验并在此发布我的发现。

更新：

我使用以下代码测试了TreeSet的性能。

import java.util.Arrays;
import java.util.Random;
import java.util.TreeSet;

class TestArrayCopy {

    public static void main(String[] arg) throws java.io.IOException {
        for (int i = 1; i <= 10; i++) {
            int arr[] = randomArray();
            System.out.println("Array Size: " + arr.length + ". Results for case #" + i);
            System.out.println("Using Array Copy:");
            copyAndSort(arr);
            System.out.println("Using Tree Set:");
            useTreeSet(arr);
            System.out.println("----------------------------");
        }
    }

    public static void copyAndSort(int array[]) {
        long start = System.nanoTime();
        for (int j = 0; j < 100; j++) {
            int copied[] = Arrays.copyOf(array, array.length);
            Arrays.sort(copied);
        }
        long end = System.nanoTime();
        System.out.println(end - start);
    }

    public static void useTreeSet(int array[]) {
        long start = System.nanoTime();
        for (int j = 0; j < 100; j++) {
            TreeSet<Integer> copied = new TreeSet<>();
            for (int i = 0; i < array.length; i++) {
                copied.add(i);
            }
        }
        long end = System.nanoTime();
        System.out.println(end - start);
    }

    public static int[] randomArray() {
        Random random = new Random();
        int len = 100000 + random.nextInt(1000000);
        int arr[] = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = random.nextInt(1000000);
        }
        return arr;
    }

}

以下是在搭载Java 8的Core-i7 64位系统上获得的结果：

数组大小：616568。第1个案例的结果
使用数组复制：
7692926921
使用Tree Set：
16336650396
----------------------------
数组大小：390270。第2个案例的结果
使用数组复制：
4441066232
使用Tree Set：
9306742954
----------------------------
数组大小：658410。第3个案例的结果
使用数组复制：
8534144532
使用Tree Set：
17721764026
----------------------------
数组大小：1021396。第4个案例的结果
使用数组复制：
13573512678
使用Tree Set：
31341152398
----------------------------
数组大小：1034872。第5个案例的结果
使用数组复制：
13298690836
使用Tree Set：
30950793986
----------------------------
数组大小：466014。第6个案例的结果
使用数组复制：
5501196272
使用Tree Set：
11704757934
----------------------------
数组大小：190231。第7个案例的结果
使用数组复制：
1662270714
使用Tree Set：
4465174267
----------------------------
数组大小：681150。第8个案例的结果
使用数组复制：
8262756493
使用Tree Set：
19079310588
----------------------------
数组大小：627257。第9个案例的结果
使用数组复制：
6725984653
使用Tree Set：
14468898852
----------------------------
数组大小：397189。第10个案例的结果
使用数组复制：
3122214311
使用Tree Set：
7356182877
----------------------------
从这些结果可以看出，TreeSet 比排序重复数组要慢得多。对我来说是一个很好的练习。

- Bhoot

---

这个基准测试存在许多问题。您需要进行适当的预热（在测量运行时间之前，对两种算法都进行紧密循环，例如每个算法运行10,000-100,000次），并且应该使用nanoTime而不是currentTimeMillis。 - aioobe

此外，您需要执行 copied.toArray(...) 以获取实际结果。 - aioobe

我正在更新我的代码以进行基准测试，这只是一个快速检查。关于 TreeSet 上的 copied.toArray()，出于测试的目的，我想在没有它的情况下测量性能。 - Bhoot

很不幸，你用的基准测试方法存在许多问题。这个测量中包括了许多与实际代码无关的因素。例如预热时间和来自先前运行的CPU缓存预热。为了得出一个误差不超过半秒钟的测量结果，唯一的方法是使用基准测试框架。 - Zabuzard