排序以最小的成本

Question

置換我給出元素的排列{1, 2, 3, ..., N}，我有使用交換操作來排序。交換元素x，y的操作的成本爲min（x，y）。

我需要找出排序置換的最低成本。我因子評分來自N貪婪要1，並把每個元素上使用交換操作它的位置，但這並不是一個好主意。

Answer 1

如果您有數字1，2，...的排列，ñ，那麼排序集合將精確爲1，2，...，ñ。所以你知道複雜度爲O（0）的答案（即你根本不需要算法）。

---

如果你真的想通過反覆交換排序的範圍內，可以反覆「提前和循環」：提前在已經排序範圍（其中a[i] == i），然後用a[a[i]]交換a[i]，直到你完成了一個循環。重複，直到你到達最後。需要至多Ñ   −   1互換，並且基本上執行與排列的週期分解。

Answer 2

嗯。一個有趣的問題。我想到的一個快速算法是使用元素作爲索引。我們首先找到具有1作爲值的元素的索引，並將其與該數字的元素交換。最終這將以1出現在第一位置，這意味着你必須交換1與一些尚未處於位置的元素，並繼續。這個上限爲2 * N-2，並且在置換（2,3，...，N，1）時具有下限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++ 
    } 
} 

Answer 3

使用桶排序與1
的成本是零桶的大小，因爲沒有互換髮生。 現在通過桶陣列進行傳遞，並將每個值交換回原始數組中的相應位置。
這就是N次掉期。
N的總和爲N（N + 1）/ 2給你一個確切的固定的成本。

不同的解釋是，你剛剛從桶陣列存儲，放回原陣列。這不是互換，因此成本爲零，這是一個合理的最小值。

Answer 4

這將是最佳的：

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 

Answer 5

如果尋求是微不足道的，然後互換的最小數目將被循環的數量來確定。它會遵循類似於Cuckoo Hashing的原則。您在排列中獲取第一個值，然後查看原始索引處的值索引處的值。如果這些匹配，然後交換一個單一的操作。

[ 2 1]：值3在索引1處，因此請查看索引3處的值。
[3 2 ]：值1在索引3處，所以存在兩個索引循環。交換這些值。

如果不是，則將第一個索引推入堆棧並查找第二個索引值的索引。最終會有一個循環。此時，通過彈出堆棧中的值開始交換。這將需要多次交換等於n-1，其中n是週期的長度。

[ 1 2]：值3是在索引1處，所以看的值在索引3
[3 1 ]：值2是在索引3，因此加入3到堆棧並尋找索引2.還存儲3作爲週期的開始值。
[3 2]：值1是在索引2處，所以加2到堆棧並尋求索引1
[ 1 2]：值3是週期的開始，所以交換從堆棧中彈出2並交換值1和2.
[1 3 2]：從堆棧中彈出3並交換2和3，從而產生具有2次交換的排序列表。
[1 2 3]

在此算法中，互換的最大數目將是N-1，其中N是值的總數。這發生在存在N長度週期時。

編輯：該算法給出了最小交換次數，但不一定是使用min（x，y）函數的最小值。我沒有完成數學計算，但我相信只有在交換（x，y）= {swap（1，x），swap（1，y），swap（1，x）}時不應該使用是當{2,3}中的x和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) 
}