Java 中 Arrays.sort 和 Arrays.parallelSort 哪個更快？

英文原文地址：Arrays.sort vs Arrays.parallelSort[1]

翻譯：高行行

小結：

當我們要排序的數據集很大時，parallelSort() 可能是更好的選擇。但是，在數組較小的情況下，最好使用 sort()，因為它可以提供更好的性能

1. 概述

我們都使用過 Arrays.sort() 對對象或原始數據類型數組（byte，short，int，long，char，float，double和boolean）進行排序。在 JDK 8 中，創造者增強了 API 以提供一種新方法：Arrays.parallelSort()。

在本教程中，我們將對 sort() 和 parallelSort() 方法進行比較。

2. Arrays.sort()

Arrays.sort() 方法對對象或原始數據類型的數組進行排序。此方法中使用的排序算法是 Dual-Pivot Quicksort[3]。 換句話說，它是快速排序算法的自定義實現，以實現更好的性能。

此方法是單線程的 ，有兩種變體：

• sort(array)–將整個數組按升序排序
• sort(array, fromIndex, toIndex)–僅將從 fromIndex 到 toIndex 的元素排序

讓我們看一下兩種變體的例子：

<code>@Test
public void givenArrayOfIntegers_whenUsingArraysSortMethod_thenSortFullArrayInAscendingOrder() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    Arrays.sort(array); 


    assertArrayEquals(expected, array);

}

@Test
public void givenArrayOfIntegers_whenUsingArraysSortMethodWithRange_thenSortRangeOfArrayInAscendingOrder() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 10, 4, 1, 2, 6, 7, 8, 9, 3, 5 };

    Arrays.sort(array, 2, 8);

    assertArrayEquals(expected, array);
}/<code>

讓我們總結一下這種方法的優缺點：

3. Arrays.parallelSort()

此方法對對象或原始數據類型的數組進行排序。與 sort() 類似，它也有兩個變體來對完整數組和部分數組進行排序：

<code>@Test
public void givenArrayOfIntegers_whenUsingArraysParallelSortMethod_thenSortFullArrayInAscendingOrder() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    Arrays.parallelSort(array);

    assertArrayEquals(expected, array);
}

@Test
public void givenArrayOfIntegers_whenUsingArraysParallelSortMethodWithRange_thenSortRangeOfArrayInAscendingOrder() {
    int[] array = { 10, 4, 6, 2, 1, 9, 7, 8, 3, 5 };
    int[] expected = { 10, 4, 1, 2, 6, 7, 8, 9, 3, 5 };

    Arrays.parallelSort(array, 2, 8);

    assertArrayEquals(expected, array);
}/<code>

parallelSort() 在功能上有所不同。與 sort() 使用單個線程對數據進行順序排序不同，它使用並行排序-合併排序算法。它將數組分成子數組，這些子數組本身先進行排序然後合併。

為了執行並行任務，它使用 ForkJoin 池。

但是我們需要知道，只有在滿足某些條件時，它才會使用並行性。如果數組大小小於或等於 8192，或者處理器只有一個核心，則它將使用順序的 Dual-Pivot Quicksort 算法。否則，它使用並行排序。

讓我們總結一下使用它的優缺點：

優缺點

4.比較

現在，讓我們看看在不同大小的數據集上兩種方法怎樣執行。以下數字是使用JMH 基準測試[4]得出的。測試環境使用 AMD A10 PRO 2.1Ghz 四核處理器和 JDK 1.8.0_221：

5.結論

在這篇短篇文章中，我們看到了 sort() 和 parallelSort() 的不同之處。

根據性能結果，我們可以得出結論，當我們要排序的數據集很大時，parallelSort() 可能是更好的選擇。但是，在數組較小的情況下，最好使用 sort()，因為它可以提供更好的性能。

與往常一樣，完整的源代碼可以在

[1] Arrays.sort vs Arrays.parallelSort: https://www.baeldung.com/java-arrays-sort-vs-parallelsort

[2] baeldung: https://www.baeldung.com/author/baeldung/

[3] Quicksort: https://www.baeldung.com/algorithm-quicksort

[4] JMH基準測試: https://www.baeldung.com/java-microbenchmark-harness

[5] GitHub: https://github.com/eugenp/tutorials/tree/master/core-java-modules/core-java-arrays-2

閱讀更多 駭客與畫家 的文章

關鍵字: 哪個 Java