/*采用类似于间接排序的中间置换法思想
1.每次存储i处元素0，i为hole，然后找到i应该存储的元素p，将其移至i，然后p为hole，
然后找到p处应该存储的元素并放入p处。。。知道空洞出应该存储V[i]。
2.移动元素时需要将元素变为负值，防止已经移动的元素再次被移动。
3.接收后将每个元素改为正。
4.复杂度O(N),最多两个元素交换3次，总共最多交换3N/2
*/
//获取i处应该存放的元素下标
int getposition(int i, int n)
{
    if(i%2 == 0)
        return n - 1 - i / 2;
    else
        return (i + 1) / 2 - 1;
}
void fun(vector<int> &v)
{

    for (int i = 0; i < v.size(); ++i)
	{
	    if(v[i] < 0)
            continue;
        cout << i << endl;
		int p = getposition(i, v.size());
        int tmp = -v[i];
        int hole, nextHole = p;
        for (hole = i; p != i; hole = nextHole)
        {
            nextHole = p;
            v[hole] = -v[p];
            p = getposition(p, v.size());
        }
        v[nextHole] = tmp;		//遇见首次腾出位置的元素v[i]，将其放入空位
        cout << v[i] << endl;
	}
	for(auto &i : v)
        i = -i;
}