3

假设我有一个长度为 N 的数组中的索引对列表。我想确定一个任意排序的列表是否在执行后排序

for pair in pairs:
  if list_to_sort[pair.first] > list_to_sort[pair.second]:
    swap(
      element_a_index=pair.first,
      element_b_index=pair.second,
      list=list_to_sort
    )

显然，我可以测试 N 元素列表的所有排列。有更快的方法吗？如果有，它是什么？这叫什么？它可以证明是最快的解决方案吗？

4

1 回答 1

9

您所描述的是一种称为排序网络的算法。不幸的是，众所周知，确定一系列交换是否产生有效排序网络的问题是co-NP-complete，这意味着除非 P = NP ，否则没有多项式时间算法来检查您的特定对选择是否正确工作.

不过，有趣的是，您不需要尝试所有可能的输入排列。有一个称为零一原则的结果表明，只要您的排序网络正确排序 0 和 1 列表，它就会正确排序任何输入序列。因此，与其尝试所有 n! 输入的可能排列，您可以检查所有 2 n 个可能的 0 和 1 序列。如果 n 非常大，这仍然是不可行的，但如果您选择的 n 很小，这可能会很有用。

至于建立排序网络的最佳方法 - 这是一个悬而未决的问题！有许多好的排序网络可以在大多数输入上快速运行，也有一些已知的排序网络是最优的。搜索“最佳排序网络”可能会找到一些有用的链接。

希望这可以帮助！

于 2013-05-13T16:45:12.480 回答