在这种情况下，我应该使用哪种排序算法？

Question

在这种情况下，我应该使用哪种排序算法？

javaalgorithmsorting

4

一个研究人员有一个包含一亿条人员记录的数据库。该研究人员想要研究按照其他标准（如星座、出生年份等）分布的名字，因此希望按名称排序并具有进一步排序的选项。

应该使用哪种排序方法？

A. 选择排序
B. 快速排序
C. 堆排序
D. 插入排序
E. 归并排序

谢谢！

- thatbennyguy

3

答案的关键在于“稍后进一步排序的选项”部分。这意味着第二个（或第三个或第四个）排序应该尊重第一个排序为相等的项目所施加的顺序。这给你什么提示？此外，“1亿”部分可以立即排除一些排序方式（也就是说，“超出你想知道的范围”——确切的数字并不重要）。 - Jon

2

@thatbennyguy：不，不是适应性。适应性指的是算法在某种程度上已经排序的情况下更快地排序的能力。这仅适用于我们谈论相同的排序标准的情况下 - 在这里，您被要求使用不同的标准进一步排序。 - Jon

2

@thatbennyguy：无论如何，从最容易的入手。哪两个答案可以立即排除掉？为什么？ - Jon

所以，为了尊重顺序，它需要是稳定的。然后它将保持相等成员的顺序不变。因此，堆排序和选择排序被排除在外，因为它们是不稳定的？快速排序也有点不稳定。由于插入排序在平均情况下表现不佳，我们说它是归并排序？归并排序有什么做不到的吗？ :) - thatbennyguy

1

@thatbennyguy：对的，但理由并不完美。选择和插入排序可以排除掉，因为它们的平均运行时间是O(n*n)，对于1亿个项目来说是不够快的。然后堆排序和快速排序也被排除掉了，因为它们不稳定（不存在"有点"不稳定）。这只留下了归并排序。干得好！ :) - Jon

显示剩余5条评论

5个回答

4

建议您将需求与 http://en.wikipedia.org/wiki/Sort_algorithms#Comparison_of_algorithms 上的比较表格进行对照。

- Oliver Charlesworth

哎呀！这是一道过去的考试题。它们应该有直截了当的答案，对吧？:S - thatbennyguy

1

@thatbennyguy：这个问题确实有一个非常直接的答案。你最多可以用三句话回答并证明答案的正确性。 - Jon

1

有人发布了一个重复的帖子，这本来是我的答案。既然我已经花了力气打出了这些，那么我也可以分享给未来的读者。

每个排序算法都有其最佳和最差的使用情况。这是我尝试思考它的方式：

选择排序：我很少/从不使用选择排序，因为几乎总是插入排序表现更好。这在小数据集和几乎排序好的列表上效果最佳
快速排序：寻找最佳平均情况
堆排序：最好的最坏情况
插入排序：(见选择)
归并排序：归并排序比快速排序稍慢，但保证了O(n log n)的行为。关键点在于归并排序比快速排序更加稳定。

显然这只是一个非常简要的概述。您可以在维基百科和通过Google搜索“何时使用[插入算法]”等方式中找到更多信息。

希望这有所帮助！

- Swift

归并排序的性能与快速排序完全不同：在大多数情况下，它的平均速度略慢，但是它具有保证的O(N*log(N))行为，而快速排序则没有。此外，值得注意的是，归并排序是稳定的，而快速排序则不是。 - Gilles 'SO- stop being evil'

排序算法意味着如果数据包含相等的条目，则它们保持原来的顺序。稳定性是一个绝对属性，说某个算法比另一个“更稳定”是没有意义的。请阅读维基百科文章。我也建议您进一步阅读。 - Gilles 'SO- stop being evil'

0

如果你想得到一个直方图，我不会对数据进行排序。我只会遍历所有数据，计算出所有感兴趣的组合。这是一个O(N)的操作。

首先对数据进行排序不太可能提高速度。这是一个O(N*log(N))的操作。

如果想要对所有记录进行排序，我会使用一个带有自定义比较器的Collection.sort()方法，其中包含您需要比较的所有字段。您必须将所有记录加载到内存中，这将占用几个GB的空间，但一旦完成后，速度应该相当快。

使这个过程更快的唯一方法是筛选条件。如果这样做，我会创建一个Collection，其中包含感兴趣的记录的副本，并对其进行排序。

- Peter Lawrey

0

最有效的排序算法，不会是传统的那种。

由于您是基于出生年份和星座等标准进行排序，我会使用“堆栈排序”（我刚刚想出来的）。

它的工作方式如下。

为每个可能的排序值创建一个数据结构。让我们以出生年份为例。在出生年份中，只会有大约100个不同的值。

为出生年份的每个可能值声明一个数据结构（100个指针数组，每个年份一个）
循环遍历每个记录，并将指向该记录的指针放入该数组中。

当您完成遍历每个记录时，现在您已经拥有了100个数组，每个数组都填充有具有特定出生年份的记录。这个方法的好处在于，您已经在O（n）时间内完成了它，因此比任何其他排序算法都要快得多。这也适用于星座等...

打破常规思维。当对具有可能值（m）的大型数据集（n）进行排序时，此方法非常有用，其中m << n。

- Localghost

1

这被称为计数排序。 - Charles

谢谢，我不知道它有名字。 - Localghost

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jon · Accepted Answer

这并不是我的答案，因为您已经自己得出了结论，但为了更好地展示，以下是答案：

1. 选择和插入可以被排除，因为它们的平均运行时间为O(n^2)，对于100M个项目来说不够快。

2. 堆排序和快速排序被排除，因为它们不稳定。这个问题需要一个稳定的排序，因为问题定义意味着在进一步排序时，原始顺序（按名称）需要保持不变。

3. 这只留下归并排序作为合适的候选。

更新：考试相关建议

我必须承认，上述第2点（按名称保留排序）并不完全清楚。然而，这是一道考试题，必须有一些方法将选项缩减到一个。即使措辞不是铁板钉钉的，要求稳定的排序也是必要的。

这种实用思维方式让我觉得对某些类型的考试问题更容易得出明确的答案。