數組排序問題

今天在龐果網做的一道題目，可是卻沒有挑戰成功，說多了都是淚，直接上題。

題目詳情:

給定一個包含1-n的數列，我們通過交換任意兩個元素給數列重新排序。求最少需要多少次交換，能把數組排成按1-n遞增的順序，其中，數組長度不超過100。

例如：

原數組是3,2,1， 我們只需要交換1和3就行了，交換次數為1，所以輸出1。

原數組是2,3,1，我們需要交換2和1，變成1,3,2，再交換3和2，變為1，2，3，總共需要的交換次數為2，所以輸出2。

起初，我以為這是一個用冒泡排序算法做的題目，可是卻不是。

數組排序完成後的每個元素都符合a[n]=n這個條件，所以可以利用這個條件來減少很多不必要的數組元素交換。

正確做法如下：

#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
int  run(const int *a,int n) {
    int* b=new int[n];
    int i,j,number=0;
    for(i=0;i<n;i++)b[i]=a[i];
    for(i=0;i<n;i++)
    {
          if(b[i]!=i+1)
        {
            for(j=i+1;j<n;j++)
          {
             if(b[j]==i+1)
             {
                 int temp=b[j];
                 b[j]=b[i];
                 b[i]=temp;
                 number++;
              }
           }
        }
    }
    return number;
}

本文出自 “淡定的dreamer” 博客，請務必保留此出處http://idiotxl1020.blog.51cto.com/6419277/1290281