插入排序

最近在全面学习数据结构，常用算法记录：插入排序，基本思想是将待排序的记录按其关键字的大小逐个插入到一个有序序列（通常为左半部分），直到所有记录插入完成，是一种稳定排序。
空间复杂度：$O(1)$
平均时间复杂度：$O(n^2)$

#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];    //待插入元素插入
    }
}

版权属于：字节星球/肥柴之家 （转载请联系作者授权）
原文链接：https://www.bytecho.net/archives/2078.html
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。