/*采用类似于间接排序的中间置换法思想 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; }