11

我得到了元素的排列，{1, 2, 3, ..., N}我必须使用交换操作对其进行排序。交换元素 x, y 的操作的成本为 min(x,y)。

我需要找出排序排列的最低成本。我坚持使用交换操作N将1每个元素放在它的位置上，但这不是一个好主意。

4

5 回答 5

2

这将是最佳的：

Find element 2
If it is not at correct place already

    Find element at position 2
    If swapping that with 2 puts both to right place

        Swap them
        Cost = Cost + min(2, other swapped element)

repeat

   Find element 1
   If element 1 is at position 1

      Find first element that is in wrong place
      If no element found

          set sorted true

      else

         Swap found element with element 1
         Cost = Cost + 1

   else

      Find element that should go to the position where 1 is
      Swap found element with element 1
      Cost = Cost + 1

until sorted is true
于 2012-10-26T17:30:56.293 回答
1

如果查找是微不足道的，那么最小交换次数将由周期数决定。它将遵循类似于Cuckoo Hashing的原则。您取排列中的第一个值，然后查看原始索引处的值的索引处的值。如果这些匹配，则交换单个操作。

[ 3 2 1] ：值 3 在索引 1 处，因此查看索引 3 处的值。
[3 2 1 ] ：值 1 在索引 3 处，因此存在两个索引循环。交换这些值。

如果不是，则将第一个索引压入堆栈并在该索引中查找第二个索引的值。最终会有一个循环。此时，通过从堆栈中弹出值开始交换。这将采用等于 n-1 的交换次数，其中 n 是循环的长度。

[ 3 1 2] ：值 3 在索引 1 处，因此查看索引 3 处的值。
[3 1 2 ] ：值 2 在索引 3 处，因此将 3 添加到堆栈并查找索引 2。同时存储 3作为循环的起始值。
[3 1 2] ：值 1 在索引 2 处，因此将 2 添加到堆栈并查找索引 1。
[ 3 1 2] ：值 3 是循环的开始，因此将弹出 2 交换出堆栈并交换值1 和 2。
[1 3 2] ：将 3 从堆栈中弹出并交换 2 和 3，从而得到一个包含 2 个交换的排序列表。
[1 2 3]

使用此算法，交换的最大数量将为 N-1，其中 N 是值的总数。当存在 N 个长度的循环时会发生这种情况。

编辑：这个算法给出了最小的交换次数，但不一定是使用 min(x, y) 函数的最小值。我没有计算过，但我相信只有一次不应该使用 swap(x, y) = {swap(1, x), swap(1, y), swap(1, x)}是当 x 在 {2,3} 和 n < 2 时；应该很容易把它写成一个特例。可能最好明确检查并放置 2 和 3，然后按照评论中提到的算法在两个操作中实现排序。

编辑2：很确定这将涵盖所有情况。

while ( unsorted ) {
    while ( 1 != index(1) )
        swap (1 , index (1) )

    if (index(2) == value@(2))
        swap (2, value@(2) )

    else
        swap (1 , highest value out of place)
}
于 2012-10-26T17:52:58.997 回答
0

如果您有数字 1, 2, ..., N的排列，那么排序后的集合将恰好是 1, 2, ..., N。所以你知道复杂度为 O(0) 的答案（即你根本不需要算法）。

如果你真的想通过重复交换对范围进行排序，你可以重复“前进和循环”：在已经排序的范围（where ）上前进a[i] == i，然后交换直到完成循环。重复直到你到达终点。这最多需要N  - 1 次交换，并且它基本上执行置换的循环分解。a[i]a[a[i]]

于 2012-10-26T16:50:26.983 回答
0

唔。一个有趣的问题。我想到的一个快速算法是使用元素作为索引。我们首先找到一个值为 1 的元素的索引，并将其与该数字的元素交换。最终这将导致 1 出现在第一个位置，这意味着您必须将 1 与一些尚未在该位置的元素交换，然后继续。最高为 2*N-2，下限为 N-1，用于排列 (2,3,...,N,1)，但具体成本会有所不同。

好的，鉴于上面的算法和示例，我认为最好的方法是用任何东西交换 1 直到它首先达到第一名，然后如果它还没有到位，则用第二名交换 2，然后继续用任何东西交换 1 还没有到位，直到排序。

set sorted=false
while (!sorted) {
    if (element 1 is in place) {
        if (element 2 is in place) {
            find any element NOT in place
            if (no element found) sorted=true 
            else {
                swap 1 with element found
                cost++
            }
        } else {
            swap 2 with element at second place
            cost+=2
        }
    } else {
        find element with number equals to position of element 1
        swap 1 with element found
        cost++
    }
}
于 2012-10-26T16:55:36.290 回答
-1

使用桶大小为 1
的桶排序。成本为零，因为没有交换发生。现在通过存储桶数组，并将每个值交换回原始数组中的相应位置。
那是N次交换。
N 的总和为 N(N+1)/2，为您提供准确的固定成本。

一种不同的解释是，您只需从存储桶数组中存储，回到原始数组中。那是没有掉期，因此成本为零，这是一个合理的最小值。

于 2012-10-26T16:57:33.590 回答