对数据集多次使用不稳定排序会产生相同的结果吗？

Question

堆排序是一种不稳定的排序。在具有相同数据集的不同机器上使用它是否可以保证结果数据集中的顺序相同，即使它是不稳定的？

编辑:实现是运行在不同机器上的C++ STL heap_sort。

Answer 1

如果您为相同的实现提供相同的输入，它将输出相同的结果。这被称为“决定论”。

唯一的例外是，如果算法是随机化的(即采样/混洗算法或bogosort)。您也可以通过向(伪)随机数生成器提供相同的种子来缓解这种情况，但Heapsort无论如何都不是随机化算法，因此结果应该是相同的。

排序的稳定性指的是这样的保证:如果您对所有属性的子集进行排序，您将始终获得关于所有属性的相同排序。I found the example on Wikipedia quite intuitive:

对某些类型的数据进行排序时，在确定排序顺序时只检查数据的一部分。例如，在右侧的卡片排序示例中，卡片是按它们的等级排序的，而它们的花色被忽略。结果是可以有多个不同的、正确排序的原始列表版本。稳定的排序算法根据以下规则选择其中之一:如果两个项目进行相等比较，如两张5张卡片，则它们的相对顺序将被保留，因此如果一个在输入中出现在另一个之前，它也将在输出中出现在另一个之前。

总而言之:如果相同确定性算法的输入保持不变，您肯定会得到相同的结果。

只是为了给“相同的输入”添加一个小的定义。输入的顺序必须保持不变。示例：

 Input 1: 2 1 3 5 4 3
 Input 2: 5 4 3 2 1 3

对这两个列表进行排序将在它们的主要属性中得到相同的结果：

 Result: 1 2 3 3 4 5

然而，在不稳定的情况下，不能保证3在之后是相同的序列(当查看附加的其他属性时)。

Answer 2

只要算法是确定性的(堆排序或任何这样的算法)，在不同的机器上运行它就能保证相同的输出。

Answer 3

问题的答案是：“对数据集多次使用不稳定排序是否会产生相同的结果？”在一般情况下是一个明确的“不”。考虑一个随机数中位数3的快速排序实现。这将为您提供每次不同的分区，因此很可能对相同的数据集运行两次将为相同的值提供不同的排序。

堆排序可能应该是确定性的。但我不会指望它，除非它被记录在案。