java - 这个排序方法的名称是什么，它是如何工作的以及它与 Arrays.sort() 相比如何？

Question

问题#1

我正在寻找一种按升序顺序对数组进行排序的方法。我发现了这个并且它有效，但我不明白它是如何工作的。

问题#2

对于大O表示法，哪种方法更好(在我的例子中n会很小)，下面的方法还是Arrays.sort()？

<小时/>

for (int i = 0; i < array; i++) {
   for (int j = 0; j < array; j++) {
      if (arr[i] < arr[j]) {
         order = arr[j];
         arr[j] = arr[i];
         arr[i] = order;
      }
    }
}

注意: array 等于 arr.length。

Answer 1

#1

您使用的方法最接近所谓的Selection Sort 。可以找到一个很好的插图here还有一个更有趣的here .

选择排序的正确实现将在 j = i + 1 处启动内循环，并在外循环的每次迭代中最多交换一个元素(最小值 或数组未排序部分中第 i 个元素的最大元素数)。就目前情况而言，数组仍然可以正确排序，但是您正在进行大量冗余比较和交换。

另请注意，您的 if 逻辑按降序顺序对数组进行排序(而不是像您声称的那样按升序)。

#2

选择排序的时间复杂度为 O(n^2)，而 Arrays.sort() 使用 Dual Pivot Quicksort时间复杂度为 O(nlogn)。 JDK 的排序算法中还内置了一项优化，该优化在较小的数组上使用插入排序，因此您实际上没有理由担心性能。

<小时/>

编辑:为什么使用此方法比使用 Arrays.sort() 排序时间更快？

而API docs状态:

Implementation Note:

The sorting algorithm is a Dual-Pivot Quicksort...

actual implementation涉及的内容更多，并且包含各种优化。

当然，在特定情况下，您的排序方法可能更快，但我会坚持使用 JDK 的排序算法。它已经过彻底的测试和改进，以确保正确性和最佳性能。

正如 @GhostCat 所指出的，另一件需要考虑的事情是您的基准测试可能存在缺陷。检查How do I write a correct micro-benchmark in Java?了解有关该主题的更多信息。