原题链接：113. 特殊排序
解题思路
根据数学归纳法，假设前k-1哥元素之间的大小关系是已经按照要求排成一行，如果可以确定第k个元素应该放在哪一个前面，即可解决问题。
我们可以通过哟这样一种二分法确定第k个元素的位置：若第k个元素比第mid个元素小，令r=mid,否则令l=mid+1。二分的初始区间可设为[1,k],区间中的k这个值表示防止所有k-1个元素之后。
样例代码
方法1：不利用STL
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res;
res.push_back(1);
for(int i = 2;i <= N;i++){
int l = 0,r = res.size() - 1;
while(l <= r){
int mid = l + r >> 1;
if(compare(res[mid],i)) l = mid + 1;
else r = mid - 1;
}
res.push_back(i);
for(int j = res.size() - 2;j > r;j--) swap(res[j],res[j + 1]);
}
return res;
}
};
方法2：利用STL
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> a;
for(int i=(N+1)/2;i;i--){
a.push_back(i);
if(N-i+1!=i)a.push_back(N-i+1);
}
// for(auto i=a.begin();i!=a.end();i++)cout<<*i<<" "<<endl;
stable_sort(a.begin(),a.end(),compare);
return a;
}
};