使序列有序的最少交換次數

題目1：

給出一個序列，隻交換相鄰兩數，使得序列升序排列，求出最少交換次數。

思路：

如果說隻是交換相鄰兩個數字。那麼就是這個序列的逆序數。

1.假設序列個數為n，我們先把最大的數換到最後，因為是相鄰數字交換，是以把最大數交換到最後，需要交換的次數為最大數後的數字個數。

2.當完成最大數的交換後，可以将最大數從序列中劃去不管了，即此時序列個數為n-1了，我們再在該序列中找到一個最大數，進行相同操作。

3.是以使整個序列有序的交換次數為,這個序列的所有逆序總數。

比如4，3，2，1。 

(4,3) (4,2) (4,1)，有3個逆序，交換後 3，2，1，4 

(3,2) (3,1)，有2個逆序，交換後2,1,3,4 

(2,1)，有1個逆序，交換後1,2,3,4

用歸并的方法寫了個。

代碼：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
int cnt;
int arr[1005];
void Merge(int* arr,int* tmp,int left,int right,int rightEnd)
{
    int leftEnd = right - 1;
    int start = left;
    while (left <= leftEnd && right <= rightEnd)
    {
        if (arr[left] > arr[right])
        {
            tmp[start++] = arr[right++];
            cnt += (leftEnd - left+1); //如果目前left位置上的數大于right位置上的數，那麼從left到leftEnd所有的數都大于
        }
        else
        {
            tmp[start++] = arr[left++];
        }
    }
    while (left <= leftEnd)
    {
        tmp[start++] = arr[left++];
    }
    while (right <= rightEnd)
    {
        tmp[start++] = arr[right++];
    }
}
void MergeSort(int* arr,int* tmp,int n,int length)//length目前有序子列的長度
{
    int i;
    for (i = 0; i <= n - 2 * length; i += 2 * length)
    {
        Merge(arr,tmp,i,i+length,i+2*length-1);
    }
    //最後剩下兩個子列，進行歸并
    if (i + length < n)
    {
        Merge(arr,tmp,i,i+length,n-1);
    }
    else //隻剩最後一個子列，不能成對
    {
        for (int j = i; j < n; j++)
        {
            tmp[j] = arr[j];
        }
    }
}
void Merge_Sort(int* arr,int n)
{
    int lenght = 1;
    int* tmp = (int *)malloc(sizeof(int)*n);
    while (lenght < n)
    {
        MergeSort(arr,tmp,n,lenght);
        lenght *= 2;
        MergeSort(tmp,arr,n,lenght);
        lenght *= 2;
    }
    free(tmp);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(arr,0,sizeof(arr));
        for(int i=0; i<n; i++)
        {
            scanf("%d",&arr[i]);
        }
        cnt=0;
        Merge_Sort(arr,n);
        printf("%d\n",cnt);
    }
    return 0;
}
           

題目2：

給出一個序列，可交換任意兩個數，使序列升序排列，求最少交換次數。

思路：

與之前不同，之前是隻能交換相鄰兩數。 

比如4，3，2，1，如果隻交換相鄰兩數，最少交換次數為6。 

但如果是交換任意兩數，最少交換次數就為2。

有序列5，4，3，2，1。共5個數。

nums [0] [1] [2] [3] [4]
      5   4   3   2   1
           

按升序排列之後為

nums1 [0] [1] [2] [3] [4]
       1   2   3   4   5
           

我們可以發現5，1雖然不在自己應該在的位置，但是如果把它們兩個看成整體，對于整個序列來說它們占據了排好序後5，1應該在的位置，是以對于整個序列來說是有序的，它們隻是自身内部無序而已。5應該到1處，1應該到5處，形成了一個循環，是以可以将它們抽象成一個環，環内換序就可以了。(下面把這種環稱為循環節) 

對于一個含有n個元素的循環節來說，要使其有序，要交換n-1次(前面都排好了，最後一個數自然有序就不用排了)。 

上例中3在原本就在的位置，可以看成一個元素的循環節。 

我們可以推斷出有一個循環節，就可以少交換一次，因為n個元素的循環節，隻需交換n-1次即可有序。 

那麼對于整個序列來說，最少交換次數為 元素總數-循環節個數。

5，4，3，2，1序列中有3個循環節，是以最少交換次數為2。

代碼：

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
int getMinSwaps(vector<int> &nums){
    //排序
    vector<int> nums1(nums);
    sort(nums1.begin(),nums1.end());
    unordered_map<int,int> m;
    int len = nums.size();
    for (int i = 0; i < len; i++){
        m[nums1[i]] = i;//建立每個元素與其應放位置的映射關系
    }

    int loops = 0;//循環節個數
    vector<bool> flag(len,false);
    //找出循環節的個數
    for (int i = 0; i < len; i++){
        if (!flag[i]){//已經通路過的位置不再通路
            int j = i;
            while (!flag[j]){
                flag[j] = true;
                j = m[nums[j]];//原序列中j位置的元素在有序序列中的位置
            }
            loops++;
        }
    }
    return len - loops;
}
int main()
{
    vector<int> nums;
    //3, 7, 1, 6, 2, 4, 8, 5
    nums.push_back(3);
    nums.push_back(7);
    nums.push_back(1);
    nums.push_back(6);
    nums.push_back(2);
    nums.push_back(4);
    nums.push_back(8);
    nums.push_back(5);
    int res=getMinSwaps(nums);
    system("pause");
    return 0;
}