总阅读量次

像往常一样，每周几题。今天这道题(最少交换次数)让我做了一次发散性的思考，先把题面搬过来，有收获的小伙伴可以进原题链接练练手。

最少交换次数
序号：#8
难度：非常难
时间限制：1000ms
内存限制：10M
描述
给出一个无序数列，每次只能交换相邻两个元素，  
求将原数列变成递增数列的最少交换次数。   
如：数列：2,3,1，交换3和1后变成：2,1,3；交换1和2之后变成：1,2,3。总共交换2次。

输入
逗号隔开的正整数数列

输出
正整数

输入样例
2,3,1
输出样例
2

当时看到题面的第一个念头就是用归并排序求逆序对(多了解一些准没错)，但是仔细一看题面，只能交换相邻元素，归并排序，pass。转念一想，还有交换(冒泡)排序呀，每次只交换相邻元素，这是完全符合题意要求的。我的代码如下：

#include<bits/stdc++.h>
#define LARGE_IO
using namespace std;

vector<int> split(const string &t)
{
    vector<int> out;
    stringstream tstream(t);
    int temp;
    while(tstream>>temp)
    {
        out.push_back(temp);
        tstream.ignore(1);
    }
    return out;
}
int bubbleSort(vector<int> &p)
{
    int len = p.size(),cnt=0;

    for(int i = 0; i < len - 1; i++)              // 控制趟数
    {
        for(int j = 1; j < len - i; j++)          // 控制比较元素
        {
            if(p[j-1] > p[j])
            {
                swap(p[j-1],p[j]);                // <algorithm>算法库自带
                cnt++;
            }
        }
    }

    return cnt;
}
int main()
{
#ifdef    LARGE_IO
    ios::sync_with_stdio(0);
#endif
    string inputStr;
    vector<int> p;
    while(getline(cin,inputStr))
    {
        p = split(inputStr);
        cout<<bubbleSort(p)<<endl;
    }

    return 0;
}

关于冒泡排序，有一个优化：
设想一个场景，数组[1,0,2,3,4,5,6,7,8,9]，第一趟只进行了一次有用的比较，数组就有序了，后面的比较都是枉然的。所以考虑加一个flag，只要存在交换，冒泡排序就继续进行下一趟，反之，排序结束。请读者自行完成代码。

当然，，，，，不可能。

int bubbleSort(vector<int> &p)
{
    int len = p.size(),cnt=0;
    bool flag=1;                                // 交换标记
    for(int i = 0; i < len - 1&& flag; i++)      // 控制趟数
    {
        flag = 0;
        for(int j = 1; j < len - i; j++)          // 控制比较元素
        {
            if(p[j-1] > p[j])
            {
                swap(p[j-1],p[j]);
                cnt++;
                flag = 1;                        // 存在交换置 真
            }
        }
    }
    return cnt;
}

总结:

* 认真仔细看题面。失之毫厘，差之千里。
* 先不要急于思考代码的实现这种细节，而是思考算法与数据结构(深度思考)。
* 完成后考虑举一反三，一题多解，锻炼发散性思维(广度思考)。