基于循环移位与首尾交换的最优排序是否为NP难？及相关问题问询

操作定义 #

仅允许以下三种操作对序列进行排序，移位操作每次仅移动1位，k次移位计为k次操作：

• 左循环移位
• 右循环移位
• 交换第1位和第2位（转置）

核心问题1 #

寻找操作次数最少的最优排序序列是否为NP难？

诸多最优排序问题为NP难，例如著名的煎饼排序问题，比尔·盖茨曾参与相关研究。

附加问题 #

问题2 #

当前已知的此类场景下，最坏情况操作次数最少的排序算法有哪些？

显然可通过类冒泡排序实现O(N³)复杂度，但已知O(N²)复杂度即可满足需求。

问题3 #

关于最坏情况操作次数已有哪些研究结论？其应为c*N²+低阶项形式，其中系数c取值是多少？（即该凯莱图的直径估计问题）

内容的提问来源于stack exchange，提问作者Alexander Chervov