折半插入排序(二分插入排序)

算法思想：折半插入排序是对直接插入排序的优化，具体的优化内容是优化比较的次数，通过每次对前面已有序的数进行折半查找，从而降低查找次数，实现优化；
但是数组的后移次数并没有减少，因而对时间复杂度的优化几乎没有；故时间复杂度 仍与直接插入排序相同。
(* 需要注意的是，折半插入排序是先找到插入位置再进行后移元素进行插入；
而原本的插入排序，是边比较边后移，最后插入。)

时间复杂度：O(n^2);
空间复杂度：O(1);

样例

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
int q[N];
int n;
void binary_search_inert_sort()
{
    for(int i=1; i<n; i++)  // 依旧是默认第一个元素有序，从第二个元素开始比较;
    {
       if(q[i-1] <= q[i]) continue; //特判，如果第i-1个元素就是小于i的，因为前面已有序，故直接跳过;
       int t = q[i]; 
       int l=0, r=i-1; // l为前i-1个元素的最左端点，r为最右端点;
       while(l < r) { //当 l<r 时说明 还没有找到带查找元素，循环结束条件为l=r;
           int mid = l + r >> 1; // ">>" 右移 符号对数值对应的二进制进行右移一位，会使得数值大小减半，从而找到中值(相当于÷2);
           if(q[mid] > t) r=mid; // 因为前i-1个数有序递增，如果中值大于待排序元素，说明待插入位置在前半部分，故使得右端为当前中值，继续循环；
           else l=mid + 1; // 如果中值小于等于待排序元素，说明待插入位置在右半部分，故使得左端为中值元素的后1位置，继续循环;<这保证了该排序的稳定性！因为当相等时最终会使得元素排在相等元素的后1位置>;
       }
       // 循环结束，找到待插入位置了 r
       for(int j=i-1; j>=r ; j--) // 从第i-1个元素开始，向前遍历到待插入位置，依次后移一位;
            q[j + 1]=q[j]; // 因为是从i-1开始遍历，故使得当前元素的后一位，等于当前元素实现后移;
        q[r] = t; // 找到待插入位置，直接插入即可;
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin >> q[i];

    binary_search_inert_sort();

    for(int i=0;i<n;i++) cout << q[i] << ' ';
    return 0;
}