使用选择法将数组中的整数按由小到大排序_数组可以直接赋值给数组吗

度度熊有一个N个数的数组，他想将数组从小到大 排好序，但是萌萌的度度熊只会下面这个操作：
任取数组中的一个数然后将它放置在数组的最后一个位置。
问最少操作多少次可以使得数组从小到大有序？

最开始的思路： 

19  7  8  25

使用set将输入数组排序，从头遍历，从最小值开始，将当前值之前所有比现在值大的数放到最后。

19 7 8 25 

— 7 8 25 19

— 7 8 — 19 25 

则共需要两次操作，由此可写得代码

#include<iostream>
#include<vector>
#include<set>
#include<deque>
using namespace std;
int main()
{
    int n;
    cin >> n;
    deque<int> num;
    set<int> s;
    for (int i = 0; i<n; i++)
    {
        int temp;
        cin >> temp;
        num.push_back(temp);
        s.insert(temp);
    }
    int res = 0;
    for (auto iter = s.begin(); iter != s.end(); iter++)
    {
        int val = *iter;
        set<int> ss;
        for (int i = 0; num[i] != val; i++)
        {
            if (num[i]>val)
            {
                ss.insert(num[i]);
                num.erase(num.begin() + i);
                i--;
            }
        }
        res += ss.size();
        if (ss.size()>0)
        {
            for (auto iter = ss.begin(); iter != ss.end(); iter++)
            {
                num.push_back(*iter);
            }
        }
    }
    cout << res << endl;
    return 0;
}

问题：ac通过率70%

测试用例：10 11 12 1 3 4 5 6 7 8 9 2

按上述思路进行分析供需13次操作，但是正确答案10次可以得到有序序列。

 1 3 4 5 6 7 8 9 2 10 11 12  //3次操作

1 2 10 11 12 3 4 5 6 7 8 //7次操作

 1 2 3 4 5 6 7 8 9 10 11 12 //3次操作

存在的问题：如果先把 3 4 5 7 8 9 放到最后，再把10 11 12 放到最后，则可以调节成有序。

这里正确的思路，选择第1小和第2小的数排成有序，选择第2小和第3小，。。。第n-1小第n小 排序

别人的代码：：）

#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int main()
  {
     int n,temp;
     cin>>n;
     vector<int> v;
     map<int,int> m;
     for(int i=0;i<n;i++)
       {  cin>>temp;
          v.push_back(temp);
          m[temp]=i;
       }
     sort(v.begin(),v.end());
     int t=n,count=0;
     for(int i=0;i<n-1;i++)
       {
           if (m[v[i]]>m[v[i+1]])
              {
                 m[v[i+1]]=t++;
                 count++;
              }
       }
     cout<<count<<endl;
  }

今天的文章使用选择法将数组中的整数按由小到大排序_数组可以直接赋值给数组吗分享到此就结束了，感谢您的阅读。