题目：

给定一个01串（仅由‘ 0’或‘1’组成的字符串），现在想把这个数字串排序成“非递减”有序序列，请问至少需要多少次交换（任意两个位置交换）？

输入描述:

输入数据第一行是一个正整数T(T<=100),表示有T组测试数据；
接下来的T行，每行给出01串。
数据保证——
50%的字符串长度在[1,100 ]
95%的字符串长度在[1,10000]
100%的字符串长度在[1,1000000]

输出描述:

对于每组测试数据，请输出排成“非递减有序序列”的最小交换次数。
每组输出占一行。

输入例子:

3
01
10
110

输出例子:

0
1
1

分析：

对于每一个01字符串都是一个非递减排序，最终的结果为0···01···1，所以，只需从右往左遍历，遇到0则从左边取一个1进行交换，直到头指针和尾指针相等。

算法代码：

int * sort(char **allString, int stringNumber)
{
    int changingTimes[stringNumber];
    
    for (int i = 0; i < stringNumber; ++i) {
        changingTimes[i] = sort01(allString[i], (int)strlen(allString[i]));
    }
    
    return changingTimes;
}

int sort01(char stringOf01[], int number)
{
    int minChangingTimes;
    
    int head = 0;
    int tale = number;

    while (head < tale) {
        if ('1' == stringOf01[head]) {
            while ('0' != stringOf01[tale]) {
                --tale;
            }
            if (head >= tale) {
                break;
            }
            
            //exchange
            ++minChangingTimes;
        }
        
        ++head;
        --tale;
    }
    
    return minChangingTimes;
}

测试代码：

//
//  main.cpp
//  sort01
//
//  Created by Jiajie Zhuo on 2017/4/10.
//  Copyright © 2017年 Jiajie Zhuo. All rights reserved.
//

#include <iostream>

#define MAXSTRLEN 1000000

using namespace std;

int * sort(char **allString, int stringNumber);
int sort01(char stringOf01[], int number);

int main(int argc, const char * argv[]) {
    cout << "Please enter the nubmer of 01: ";
    int number;
    cin >> number;
    
    char *stringOf01[number];
    
    cout << "Please enter the string of 01: ";
    char *tempString;// = new char[MAXSTRLEN];
    for (int i = 0; i < number; ++i) {
        cin >> tempString;
        stringOf01[i] = tempString;
    }
    
    int *changingTimes = sort(stringOf01, number);
    for (int i = 0; i < number; ++i) {
        cout << changingTimes[i] << endl;
    }
    
//    delete [] tempString;
    
    return 0;
}