algorithm - 按求和算法对数字进行排序

Question

我有一个与算法无关的问题。

这来 self 读到的一个(可能很简单的)编程挑战。问题是，我太笨了，无法弄清楚，而且好奇心让我很烦恼。

目标是通过交换列表中数字的位置来对整数列表进行升序排序。每次交换两个数字时，您都必须将它们的总和加到总计中。挑战在于生成具有尽可能小的运行总数的排序列表。 示例:

3 2 1 - 4
1 8 9 7 6 - 41
8 4 5 3 2 7 - 34

虽然您可以根据需要自由给出答案，但如果您更愿意提供正确方向的“提示”(如果可能的话)，我会更愿意这样做。

Answer 1

只读前两段是你只是想要一个提示。有一个有效的解决方案(当然除非我犯了一个错误)。首先对列表进行排序。现在我们可以将原始列表写成不相交循环的乘积列表。

例如 5,3,4,2,1 有两个循环，(5,1) 和 (3,4,2)。循环可以认为是从3开始，4在3的位置，2在4的位置，4在3的位置。点。最终目标是 1、2、3、4、5 或 (1)(2)(3)(4)(5)，五个不相交的循环。

如果我们切换来自不同循环的两个元素，比如 1 和 3，那么我们得到:5,1,4,2,3 和循环符号 (1,5,3,4,2)。两个循环合为一个循环，这与我们想做的相反。

如果我们从同一个循环中切换两个元素，比如 3 和 4，那么我们将得到:循环符号 (5,1)(2,4)(3) 中的 5,4,3,2,1。一个周期被分成两个较小的周期。这使我们更接近所有长度为 1 的循环的目标。请注意，同一循环中两个元素的任何切换都会将循环分成两个循环。

如果我们能找出切换一个循环的最佳算法，我们就可以将其应用于所有循环并获得整个排序的最佳算法。一种算法是取循环中的最小元素，并将它与它所在的位置进行切换。因此对于 (3,4,2)，我们将 2 与 4 切换。这给我们留下了一个长度为 1 的循环(元素刚刚切换到正确的位置)和一个比以前小一号的循环。然后我们可以再次应用该规则。该算法将最小元素循环长度切换 -1 次，每隔一个元素切换一次。

将长度为 n 的循环转换为长度为 1 的循环需要 n - 1 次操作。每个元素必须至少被操作一次(想想每个要排序的元素，它必须被移动到正确的位置)。我提出的算法对每个元素进行一次操作，这是所有算法都必须做的，然后所有其他操作都在最小元素上进行。没有比这更好的算法了。

这个算法需要 O(n log n) 来排序然后 O(n) 来打乱循环。求解一个循环需要 O(cycle length)，所有循环的总长度为 n，因此循环操作的成本为 O(n)。最终运行时间为 O(n log n)。