def recsort(l, sort):
if sorted(l2):
if min>cost:
cost=min
bestsort=sort
if(len(sort) > len(l)*len(l)): //or some other criteria
return
for p1 in (0,len(l)):
for p2 in (0,len(l)):
cost += l[p1] + l[p2]
l2 = swap(l, p1,p2)
if cost<min:
recsort(l2, append sort (p1,p2))
4 回答
交换2和1，然后是1和4，然后是1和8？或者这是一般性问题？
对于更通用的方法，您可以尝试：
交换每对2个元素（具有最高总和），如果它们是完美的交换（即交换它们将使它们都在它们的正确位置） . 钍
使用最低元素作为交换的枢轴（通过交换其占据的点的元素），直到它到达其最终点
然后，您有两种可能性：
重复步骤2：使用不在其最终位置的最低元素作为枢轴，直到它到达最终点，然后返回到步骤3
或者将最终点（l2）中的最低元素与最低元素（l1）交换，重复步骤2直到l1到达l2的最终点 . 然后：
再次交换l1和l2，转到步骤3.1
或者再次转到步骤3.2，下一个最低元素不在其最终位置 .
完成所有这些操作后，如果一个相反的交换一个接一个地执行（例如，从步骤2到步骤3.2可能会发生），请将它们删除 .
还有一些事情需要注意，但这已经是一个非常好的近似值 . 第一步和第二步应该总是有效，第三步是在一些边缘情况下改进的步骤 .
正在使用的算法示例：
With {8 4 5 3 2 7}: (target array {2 3 4 5 7 8})
步骤2：2 <> 7,2 <> 8
数组现在是{2,4,5,3,7,8}
3.1和3.2之间的选择：
3.1给出3 <> 5,3 <> 4
3.2给出2 <> 3,2 <> 5,2 <> 4,2 <> 3
3 <> 5,3 <> 4是更好的结果
结论：2 <> 7,2 <> 8,3 <> 5,3 <> 4是最佳答案 .
With {1 8 9 7 6} (resulting array {1 6 7 8 9})
你已经开始在第三步了
3.1和3.2之间的选择：
3.1给出6 <> 9,6 <> 7,6 <> 8（总数：42）
3.2给出1 <> 6,1 <> 9,1 <> 7,1 <> 8,1 <> 6（总数：41）
所以1 <> 6,1 <> 9,1 <> 7,1 <> 8,1 <> 6是最好的结果
这闻起来像家庭作业 . 您需要做的是对数组进行排序，但这样做可以最大限度地降低交换成本 . 所以，这是一个优化问题而不是排序问题 .
一个贪婪的算法尽管有这个工作，但你要做的就是通过先交换最便宜的算法来解决问题（找出它所属的列表中的位置） . 然而，这不一定是最佳的 .
只要你从不交换相同的元素两次，贪婪算法应该是最佳的 .
无论如何，回到动态编程的东西，只需使用递归构建解决方案树，然后在找到更优化的解决方案时修剪树 . 这是非常基本的递归 .
如果你是一个更复杂的排序算法，你将会遇到更多困难，这与动态编程一起令人费解，所以我建议你从简单，慢的
O(n^2)排序开始 . 并 Build 在此之上 .我想解释一下动态编程是如何工作的，而不是为您提供解决方案 .
您需要做的第一件事是找出一种能够探索所有可能解决方案的算法（这可能是一个非常愚蠢的强力算法） .
然后使用递归实现它，因为动态编程基于能够快速找出重叠的子问题，ergo递归 .
在每次递归调用时，您都会查找解决方案中的位置并检查解决方案树的这一部分的位置，如果已经完成此操作，则可以测试当前解决方案是否更优，如果是你继续，否则你已经完成了这个问题的分支 .
当您到达最终解决方案时，您将解决问题 .
将每个递归调用视为部分解决方案的快照 . 您的工作是确定每个递归调用如何在最终的最优解决方案中组合在一起 .
我建议你这样做：
编写递归排序算法
为您的参数添加参数在对数组进行排序时，维护此执行路径成本的递归函数会增加此成本 . 对于任何给定点的每个可能的交换执行另一个递归调用（这将分支您的解决方案树）
每当您意识到当前正在探索的解决方案的成本超出了其他地方的成本时，就会中止（只返回） .
为了能够回答最后一个问题，您需要维护共享内存区域，您可以根据您在递归算法中的位置进行索引 . 如果有预先计算的成本，那么你只需返回该值并且不继续处理（这是修剪，这使得它很快） .
使用这种方法，您甚至可以将解决方案基于置换暴力算法，它可能会非常慢或内存密集，因为当您进行分支或修剪时它是愚蠢的，但您实际上并不需要特定的排序算法做这项工作，这样做会更有效率 .
祝好运！
如果进行高 - 低选择排序，则可以保证第N个最大元素的交换次数不超过N次 . 这是一个简单的算法，具有非常简单和诱人的保证......也许可以通过几个例子来看看它，看看它是如何调整的 . 注意：这可能不会导致最佳答案......
要找到绝对最低成本，您必须尝试所有方式进行交换，然后找到最快的方法 .
一种非常好的方法是递归地将最大值放在顶部 .