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

Question

Q#1

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

Q#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. A nice illustration can be found here and a more entertaining one here。

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

另请注意，您的 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? 了解有关该主题的更多信息。

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

What is the name of this sorting method, how does it work and how does it compare to Arrays.sort()?

java

sorting

linear-search

Q#1

Q#2

#1

#2