CPP

#include <iostream>

using namespace std;

//直接插入排序（含哨兵）优点：不用判断j>=0，哨兵即为循环结束标志
void insertSort_1(int arr[], int n);
//直接插入排序（不含哨兵）
void insertSort_2(int arr[], int n);
//折半（二分）插入排序 对直接插入排序的优化
void insertSort_3(int arr[], int n);

int main()
{
    int arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, arr_2[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, arr_normal[] = {5, 7, 12, 6, 2, 0, 8, 15, 1, 11};
    int length = (int)(sizeof(arr) / sizeof(int));  //数组长度
    insertSort_1(arr, length);
    insertSort_2(arr_normal, length - 1);
    for (int i = 1; i < length; i++)
        cout << arr[i] << " ";
    cout << endl;
    for(auto item:arr_normal)
        cout << item << " ";
    cout << endl;
    insertSort_3(arr_2, length);
    for (int i = 1; i < length; i++)
        cout << arr_2[i] << " ";
    return 0;
}

void insertSort_1(int arr[],int n)
{
    int i, j;
    for (i = 2; i < n; i++)     //从第二个元素开始，arr[0]为哨兵
    {
        if(arr[i] < arr[i - 1])     //arr[i - 1]为上一个有序序列中的最大元素
        {
            arr[0] = arr[i];
            for (j = i - 1; arr[0] < arr[j]; --j)  //当前元素若小于或等于哨兵元素，则停止移动，哨兵插入该位置后
                arr[j + 1] = arr[j];    //往后移，为待插入元素腾出空位
            arr[j + 1] = arr[0];    //将哨兵插入
        }
    }
}

void insertSort_2(int arr[],int n)
{
    int i, j, temp;
    for (i = 1; i < n; i++)     //从第二个元素开始，arr[0]为哨兵
    {
        if(arr[i] < arr[i - 1])     //arr[i - 1]为上一个有序序列中的最大元素
        {
            temp = arr[i];  //临时存储待插入元素
            for (j = i - 1; j >= 0 && temp < arr[j]; --j)  //当前元素若小于或等于待插入元素，则停止移动，待插入元素插入该位置后
                arr[j + 1] = arr[j];    //往后移，为待插入元素腾出空位
            arr[j + 1] = temp;    //待插入元素插入
        }
    }
}

void insertSort_3(int arr[], int n)
{
    int i, j, low, high, mid;
    for (i = 2; i < n; i++)
    {
        arr[0] = arr[i];    //待插入元素存入哨兵节点
        low = 1, high = i - 1;  //折半查找的区域
        while(low <= high){
            mid = (low + high) / 2;
            if(arr[mid] > arr[0])
                high = mid - 1;     //查找左半部分
            else
                low = high + 1;     //查找右半部分，同时当arr[mid]==arr[0]时，继续在mid右方查找插入位置，保证算法稳定性
        }
        for (j = i - 1; j >= high + 1; j--)     //循环大于哨兵的所有元素，均往后移动一位
            arr[j + 1] = arr[j];    //往后移，为待插入元素腾出空位
        arr[high + 1] = arr[0];    //待插入元素插入
    }
}