特殊排序

这是交互式的题目，leetcode上很常见，只需要实现一个函数就好
 1 // Forward declaration of compare API.
 2 // bool compare(int a, int b);
 3 // return bool means whether a is less than b.
 4 
 5 class Solution {
 6 public:
 7     vector<int> specialSort(int n) {
 8         vector<int> res;
 9         res.push_back(1);
10         for (int i = 2; i <= n; i++) {
11             int l = 0, r = res.size() - 1;
12             while (l < r) {
13                 int mid = l + r + 1 >> 1;
14                 if (compare(res[mid], i)) {
15                     l = mid;
16                 } else {
17                     r = mid - 1;
18                 }
19             }
20             res.push_back(i);
21             for (int j = res.size() - 2; j > r; j--) {
22                 swap (res[j], res[j + 1]);
23             }
24             if (compare(i, res[r])) {
25                 swap(res[r], res[r + 1]);
26             }
27         }
28         return res;
29     }
30 };