【2023王道数据结构】【排序】通过C++实现折半插入排序二分查找优化（线性有序表STL容器）C、C++完整实现（可直接运行）

~~~笔锋至此又怎能平淡而终，故事开始便不承认普通✌✌✌

✌ 题目及题解持续更新中
【2023王道数据结构目录】课后算法设计题C、C++代码实现完整版大全

题目： 通过C++实现折半插入排序二分查找优化（线性有序表STL容器）

运行截图：

代码实现：

#include 
#include 
using namespace std;

void Binary_Insert_Sort(vector &v)
{
    

    // 因为有n-1个待插入元素，所以执行n-1轮
    for (int i = 1; i < v.size(); i++)
    {
        int temp = v[i]; // 保存当前待插入元素

        // 只有待插入小于前面已排好序最后一个元素才进行插入
        if (temp < v[i - 1])
        {
            int low = 0, high = i - 1, mid; // 定义折半查找变量，分别指向已经排好序的表头和表尾
            while (low <= high)
            {
                mid = (low + high) / 2;

                // 如果待插入小于中间值，查找左半子表
                if (temp < v[mid])
                {
                    high = mid - 1;
                }
                // 如果相等或者大于查找右半子表，相等也向右查找是为了稳定性
                else
                {
                    low = mid + 1;
                }
            }
            int j;

            // 将[low,i-1]之间的元素全部后移一位，low位置的元素是大于等于待插入元素的
            for (j = i - 1; j >= low; j--)
            {
                v[j + 1] = v[j];
            }

            // 将待插入元素进行插入
            v[j + 1] = temp;
        }
    }
}

void PrintArray(vector v)
{
    

    for (vector::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it << 't';
    }
    cout << endl;
}

int main()
{
    vector v = {1, 2, 9, 3, 3, 8, 5, 6, 7, 1, 2, 1};
    cout << "排序前:" << endl;
    PrintArray(v);
    Binary_Insert_Sort(v);
    cout << "排序后:" << endl;
    PrintArray(v);
}