算法1

依次将每个数插入ans中，插入前二分找到第一个比他大的位置
参考

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;

        for(int i=1;i<=N;i++)
        {
            int l = 0, r = res.size(); // 万一此时插入i为边界，多预留一个数
            while(l < r)
            {
                int mid = l + r >> 1;
                if(compare(i,res[mid])) r = mid; // 依次将每个数插入ans中，插入前二分找到第一个比他大的位置
                else l = mid + 1;
            }

            res.insert(res.begin() + r ,i);
        }

        return res;
    }
};

算法2（黑科技）

归并排序？(即元素大小关系不具有传递性)
参考

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int>v;
        for(int i=1;i<=N;++i)v.push_back(i);
        stable_sort(v.begin(),v.end(),compare);
        return v;
    }
};