upd on 2020/8/30:感谢@Randolph巨佬指出的错误，sort和stable_sort的实现就不是一个东西QAQ

题目描述

有N个元素，编号1.2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。
注意：不存在两个元素大小相等的情况。
也就是说，元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。
然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过10000次提问来获取信息，每次提问只能了解某两个元素之间的关系。
现在请你把这N个元素排成一行，使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。
例如，编号为a和b的两个元素，如果元素a小于元素b,则compare（a,b）返回true，否则返回false。
将N个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

简述题意：给你n个元素，只能比较，要求使用不超过10000次比较排序

数据范围 1≤N≤1000(1e3真凉心)

样例

[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

[3, 1, 2]

算法

(STL大法好！) $O(nlogn)$

我太弱了，连手写快排都不会……
于是我动起了STL排序的心思
丑陋代码：

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

然而IE了……
于是我灵机一动，将a的初始创建方式改成这样：（面向数据编程……）

for(int i=(N+1)/2;i;i--){//从中间开始往两边插入
    a.push_back(i);
    if(N-i+1!=i)a.push_back(N-i+1);
}

然而还是IE……
灰心丧气的我想起sort是个快排+乱搞
又想起stable_sort 是个归并排序
于是……

C++ 代码

// 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> 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;
    }
};

参考文献：
STLsort源码
STLstable_sort源码