时间复杂度分析

解法一:二分模板一 $\quad O(n \times logn)$

// 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;
        res.push_back(1);
        for(int i=2;i<=N;i++) 
        {
            //1.利用二分:找出第一个小于i的位置 r ,i要插入的位置为r+1 
            int l=0,r=res.size()-1;
            while(l<r)
            {
                int mid = l + r  +1>> 1;
                if(compare(res[mid],i)) l = mid;
                else r = mid -1;
            }
            //2.将i插入到结果数组res的 最后一个位置 
            res.push_back(i);
            //3.将i放到位置为r+1处,其他位置的元素依次移动 
            for(int j = res.size()-2;j>r;j--)  
                swap(res[j],res[j+1]);
            //4.边界条件 :如果i<res[r]说明i是最小的元素,i应该插入到结果数组res的第一个位置
            //为什么i是最小的元素? 因为res[r]是第一个小于i的元素,i还小于res[r],说明i是最小的元素 
            // 在第3步已经将i换到了r+1的位置处,所以只需要交换r和r+1的元素即可 
            if(compare(i,res[r])) swap(res[r],res[r+1]);
        }
        return res;
    }
};

解法二:二分模板二 $\quad O(n \times logn)$

写法一

// 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;
        res.push_back(1);
        for(int i=2;i<=N;i++)
        {
             //为什么在这里push_back? 
             /*
              在这里push_back可以充分考虑到2.1和2.2的边界情况
              在这里先push_back后,如果是2.2的情况,下面二分出来的r只会是res.size()-1
              如果是2.1的情况,则会正确找出一个r
              在步骤3时,就不需要分类讨论 
             */ 
            res.push_back(i); 
            //1.利用二分找出第一个>i的位置r,i插入到r处 ,其他元素向后移一位 
            int l=0,r=res.size()-1;
            while(l<r)
            {
                int mid = l + r >> 1;
                if(compare(i,res[mid])) r = mid;
                else l = mid + 1;
            }
            //2.边界情况分析
            /* 
            2.1 如果利用二分能顺利找出第一个>i的位置r,那么就将元素i插入到下标为r处,其他原先在r~res.size()-2
            的元素向后移一位
            2.2 如果利用二分无法找出第一个>i的位置r,那么i一定就是最大值,此时i应该放到res数组的最后一个位置 
            */
            //3.将元素i放到位置i 
            for(int j = res.size()-2;j >= r;j--)
                swap(res[j],res[j+1]);
        }
        return res;
    }
};

写法二

// 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;
        res.push_back(1);
        for(int i=2;i<=N;i++)
        {
            //1.利用二分找出第一个>i的位置r,i插入到r处 ,其他元素向后移一位  
            int l=0,r=res.size()-1;
            while(l<r)
            {
                int mid = l + r >> 1;
                if(compare(i,res[mid])) r = mid;
                else l = mid + 1;
            }
            /*
                2.边界条件
                    2.1如果利用二分正确找出第一个大于i的位置r,那么执行交换命令,将i放到r处
                    2.2如果利用二分没有正确找出第一个大于i的位置r,此时r必然等于res.size()-1,且这时i是最大的元素
                    应放到最后一个位置 
            */ 
            //在这再push_back ,先满足2.2的情况 
            res.push_back(i);  
            //如果满足2.1的情况,再交换,否则不需要交换 
            if(compare(i,res[r]))
                for(int j = res.size()-2;j >= r;j--)
                    swap(res[j],res[j+1]);
        }
        return res;
    }
};