尽管有 array.sort，排序算法的作用

Question

当我们有 array.sort 时，为什么我们需要这么多排序算法来对整数数组进行排序？
排序与查找数组中的最大数有区别吗？
哪种排序算法对数组排序最好？

Answer 1

1> 当我们有 array.sort 时，为什么我们需要这么多排序算法来对整数数组进行排序...

不同的排序算法用于不同类型的用例。所以例如Arrays.sort 使用快速排序，而如果数组中的元素数少于 7，则使用插入排序。

2> 排序和查找数组中的最大数是否不同？我的意思是如果一个数组显然是排序的，最大的数字将在末尾结束

是的，你是对的。对数据进行排序有不同的目的。如果你想要最大的元素，你总是可以用 o(n) 找到它，而如果你的数据集已经排序，你可以用 o(1) 找到它。

3> 对数组进行排序的最佳排序算法是什么？

这取决于用例与用例。 time/space 等各种因素出现。

Answer 2

没有排序算法就无法实现 array.sort。就好像在说超市都能买到牛肉干嘛还需要牛
要找到最大值，您不需要移动集合中的元素。要对它们进行排序，您需要移动它们。
没有"best"排序算法。这完全取决于您的用例。

更多：https://en.wikipedia.org/wiki/Sorting_algorithm

Answer 3

不同的问题需要不同的解决方案。哪种算法最适合排序取决于数组的性质。
查找最大数只需要遍历数组一次，这比任何真正的排序算法都更有效。
见 1.

Answer 4

Why do we need so many sorting algorithms to sort an array of integers when we have array.sort which already does the same?

大多数编程语言在其标准库中都带有某种排序算法。大多数时候，你可以只使用这个默认的排序算法，你会没事的。

也就是说，不同的排序算法具有不同的性能特征和不同的权衡。大多数排序算法的库实现都使用比较排序，如快速排序、timsort 或 introsort。这些算法可用于对任何可以相互比较的对象进行排序，因此它们是很好的通用排序。对于某些情况——例如对整数进行排序——有专门的算法可以利用您正在对整数数据进行排序的事实。例如，如果您要对其中包含许多小数字的数组进行排序，无论是在理论上还是在实践中，使用计数排序或基数排序可能比快速排序更快。

还有其他注意事项需要考虑。例如，快速排序平均速度很快，但有退化的情况。您可能拥有绝对无法满足这些情况的应用程序，在这种情况下，使用自定义排序算法可能是合适的。

Is sorting and finding the largest number in an array different ? i mean if an array is sorted obviously the largest number will end up at the end

是的，这些是不同的问题。通过简单地记录到目前为止您看到的最大值，您可以一次性找到数组的最大元素。这需要时间 O(n)，使用 space O(1)，并且非常高效。排序算法需要比这花费更多的时间和精力，因为它们还必须找到 second-最大的元素，third-最大的元素等. 从这个意义上说，排序是一个根本性的 "harder" 问题，而不是寻找数组最大元素的问题。

which is the best sorting algorithm to sort an array ?

正如我之前提到的，没有一种 "best" 算法可以对数组进行排序。这取决于许多因素，例如数组中存储的元素种类、这些元素的分布情况、您想要的是最坏情况还是平均情况的效率、您要使用多少内存等。软件工程的大多数方面，都需要做出许多不同的权衡，由您来选择您认为最好的。

希望对您有所帮助！

Answer 5

Why do we need so many sorting algorithms to sort an array of integers when we have array.sort?

每种排序算法都有其优点和缺点，其效率，无论是时间还是 space，都会因上下文而异。

我建议您看一下 Big-O Cheat sheet，它为您总结了每种排序算法的效率（如果您不了解这些算法，则 link）。

您的示例 Arrays.sort() 在幕后使用了快速排序。在大多数情况下它都很好，但在最坏的情况下可能会很糟糕 (O(n^2))。

Is sorting different from finding the largest number in an array?

查找最大数不同于对数组进行排序。如果您的数组已经排序，那么最后一个数字是最大的，这很酷。但是如果你只需要最大的，你不必重新排列数组并按正确的顺序移动所有元素，你可以直接读取它。读取数组元素和移动其元素的复杂性不同！
以下代码搜索最大元素，space 复杂度为 O(1)，时间复杂度为 O(n)。它比排序数组更容易。

int biggest = array[0];
for (int i = 0; i < array.length; i++) {
    if (array[i] > biggest) {
        biggest = array[i];
    }
}

Which is the best sorting algorithm to sort an array ?

没有最好的排序算法，全看上下文。我建议您阅读 Sorting Algorithm wikipedia entry 并遵循 link 以更好地理解每个排序算法的行为，time/space 复杂性的重要性...

Answer 6

谢谢大家的回答。我现在明白 array.sort 也使用其中一种 排序方法 并且没有 "best" 排序方法，这取决于在上下文中。

尽管有 array.sort，排序算法的作用

Role of sorting algorithms in spite of having array.sort

java

sorting

algorithm