http://blog.acmol.com/category/algorithm/

第一題：現在想通過交換相鄰元素的操作把一個給定序列交換成有序，最少需要交換的次數是多少？比如3 1 2 4 5需要最少交換2次。

答案：需要交換的最少次數為該序列的逆序數。

證明：可以先將最大數交換到最后，由于是相鄰兩個數交換，需要交換的次數為最大數后面的數的個數（可以看做是最大數的逆序數），然后，交換過后，去除最大數，再考慮當前最大數也需要其逆序數次交換。則每個數都需要交換其逆序數次操作，則總最少交換次數為序列總體的逆序數。

第二題：現在想通過交換任意兩個元素的操作把一個給定序列交換成有序，最少需要交換的次數是多少？

答案：我認為是數字的總個數減去循環節的個數。

循環節的求法是，先將數組排序，然后根據之前的坐標和排序之后的坐標，構建成一個有向圖，然后在這個圖上找到環

對于第二題有另一種方法：

http://blog.csdn.net/yysdsyl/article/details/4311031

e.g. { 2, 3, 1, 5, 6, 4}

231564 -> 6 mismatch?
two cycles -> 123 and 456?
swap 1,2 then 2,3, then 4,5 then 5,6 -> 4 swaps to sort?
?
Probably the easiest algorithm would be to use a bitarray. Initialize it to 0, then start at the first 0. Swap the number there to the right place and put a 1 there. Continue until the current place holds the right number. Then move on to the next 0?
?
Example:?
231564?
000000?
-> swap 2,3?
321564?
010000?
-> swap 3,1?
123564?
111000?
-> continue at next 0; swap 5,6?
123654?
111010?
-> swap 6,4?
123456?
111111?
-> bitarray is all 1's, so we're done.?

?

代碼：

#include <iostream>
#include <algorithm>

using namespace std;

template <typename T>
int GetMinimumSwapsForSorted(T seq[], int n)
{
??? bool* right_place_flag = new bool[n];
??? T* sorted_seq = new T[n];
??? int p ,q;
???
??? copy(seq, seq + n, sorted_seq);
??? sort(sorted_seq, sorted_seq + n);??? 可采用效率更高的排序算法
???
??? for(int i = 0; i < n; i++)
??? {
??????? if(seq[i] != sorted_seq[i])
??????????? right_place_flag[i] = false;
??????? else
??????????? right_place_flag[i] = true;
??? }
???
??? p = 0;
??? int minimumswap = 0;
??? while(1)
??? {
??????? while(right_place_flag[p])
??????????? p++;
??????? q = p + 1;
??????? 此種找法只對無重復序列能得出minimum swaps
??????? while(q < n)
??????? {
??????????? if(!right_place_flag[q] && sorted_seq[q] == seq[p])
??????????????? break;
??????????? q++;
??????? }

??????? if(q >= n || p >= n)
??????????? break;
??????? right_place_flag[q] = true;
??????? if(seq[q] == sorted_seq[p])
??????????? right_place_flag[p] = true;
??????? swap(seq[p], seq[q]);
??????? minimumswap++;
??? }

??? delete[] sorted_seq;
??? delete[] right_place_flag;

??? return minimumswap;
}

int _tmain(int argc, _TCHAR* argv[])
{
??? int seq[] = {3, 2, 1, 5, 6, 8, 4, 7 };//{2,3,1,5,6,4};//{2,3,2,4,7,6,3,5};
??? int n = sizeof(seq) / sizeof(int);
??? cout<<"minimum swaps : "<<GetMinimumSwapsForSorted(seq, n)<<endl;

??? system("pause");
?return 0;
}

也就是依次將元素放在其應該在的位置

總結

以上是生活随笔為你收集整理的最少交换次数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。