algorithm - 确定比较和交换指令列表是否会对长度为 N 的列表进行排序

Question

假设我有一个长度为 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 元素列表的所有排列。有没有更快的方法？如果有，那是什么？这叫什么？它是否可以证明是最快的解决方案？

Answer 1

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

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

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

希望这对您有所帮助!