排序号被和算法 [英] Sort numbers by sum algorithm

问题描述

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

I have a language-agnostic question about an algorithm.

这来自于一个（可能是简单的）编程挑战，我读。问题是，我太愚蠢算起来，和好奇，以至于它被窃听我。

This comes from a (probably simple) programming challenge I read. The problem is, I'm too stupid to figure it out, and curious enough that it is bugging me.

的目标是整数列表进行排序，以通过交换在列表号码的位置按升序排列。每次交换两个数字，你要它们的和添加到正在运行的总和。面临的挑战是产生排序列表用尽可能小的运行总计。 例如：

The goal is to sort a list of integers to ascending order by swapping the positions of numbers in the list. Each time you swap two numbers, you have to add their sum to a running total. The challenge is to produce the sorted list with the smallest possible running total. Examples:

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

虽然你可以自由地只是给出了答案，如果你想，如果你宁愿提供正确的方向前进提示（如果这样的事情是可能的），我会preFER了。

Though you are free to just give the answer if you want, if you'd rather offer a "hint" in the right direction (if such a thing is possible), I would prefer that.

推荐答案

只能读取前两个段落，你只想要一个提示。有一个有效的解决方案，以本（除非我做当然是错误的）。首先对列表进行排序。现在，我们可以写原来的名单不相交周期的产品清单。

Only read the first two paragraph is you just want a hint. There is a an efficient solution to this (unless I made a mistake of course). First sort the list. Now we can write the original list as a list of products of disjoint cycles.

例如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），五不相交的周期。

For example 5,3,4,2,1 has two cycles, (5,1) and (3,4,2). The cycle can be thought of as starting at 3, 4 is in 3's spot, 2 is in 4's spot, and 4 is in 3's. spot. The end goal is 1,2,3,4,5 or (1)(2)(3)(4)(5), five disjoint cycles.

如果我们改用来自不同周期的两个元素，比如1和3，然后我们得到：5,1,4,2,3和循环符号（1,5,3,4,2）。两个循环连接成一个循环，这就是我们想要做的是相反的。

If we switch two elements from different cycles, say 1 and 3 then we get: 5,1,4,2,3 and in cycle notation (1,5,3,4,2). The two cycles are joined into one cycle, this is the opposite of what we want to do.

如果我们切换从同一周期两个元件，例如3和4，然后我们得到：5,4,3,2,1在周期符号（5,1）（2,4）（3）。的一个周期被分成两个较小的周期。这得到我们更接近的长度1.注意所有周期的目标，在同一周期两种元素的任何开关分裂周期分为两个周期。

If we switch two elements from the same cycle, say 3 and 4 then we get: 5,4,3,2,1 in cycle notation (5,1)(2,4)(3). The one cycle is split into two smaller cycles. This gets us closer to the goal of all cycles of length 1. Notice that any switch of two elements in the same cycle splits the cycle into two cycles.

如果我们能找出最佳的算法转换的一个周期，我们可以申请，对所有循环，并得到整个排序的优化算法。一种算法是采取最小元素在周期和切换它的其位置就在，所以为（3,4,2），我们将转向2 4。这给我们留下了长度为1的周期（元件刚切换到正确的位置），大小1比以前小的循环。然后，我们可以再次申请的规则。此算法切换的最小元素周期长度-1次和一次所有其他元素。

If we can figure out the optimal algorithm for switching one cycle we can apply that for all cycles and get an optimal algorithm for the entire sort. One algorithm is to take the minimum element in the cycle and switch it with the the whose position it is in. So for (3,4,2) we would switch 2 with 4. This leaves us with a cycle of length 1 (the element just switched into the correct position) and a cycle of size one smaller than before. We can then apply the rule again. This algorithm switches the smallest element cycle length -1 times and every other element once.

要变换的长度为n为长度为1个循环周期为N - 1的操作。每个元素必须被操作的至少一次（考虑每个元素进行排序，它必须被移动到它的正确位置）。我提出的算法操作的每个元素一次，这所有的算法必须这样做，那么所有其他操作的最小元素上进行的。没有算法可以做的更好。

To transform a cycle of length n into cycles of length 1 takes n - 1 operations. Each element must be operated on at least once (think about each element to be sorted, it has to be moved to its correct position). The algorithm I proposed operates on each element once, which all algorithms must do, then every other operation was done on the minimal element. No algorithm can do better.

此算法需要O（N日志N）来，然后为O（n）排序惹周期。解决一个周期需要O（周期），所有周期的总长度为n如此循环操作的成本为O（n）。最终的运行时间为O（n log n）的。

This algorithm takes O(n log n) to sort then O(n) to mess with cycles. Solving one cycle takes O(cycle length), the total length of all cycles is n so cost of the cycle operations is O(n). The final run time is O(n log n).

这篇关于排序号被和算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！