插入排序

废话不多说先上代码

void insertionSort(int arr[], int length) {
    int value;
    int x;

    for (int i = 1; i < length; ++i)
    {
        value = arr[i];
        x = i;

        for (; x > 0; --x)
        {
            if(arr[x - 1] > value) {
                arr[x] = arr[x - 1];
            } else {
                break;
            }
        }

        arr[x] = value;
    }

    return;
}

时间复杂度

O(n²)

空间复杂度

O(1) 原地排序

稳定排序

是稳定排序

算法核心思想

将待排序数组划分为两个区间，有序区间和无序区间。
有序区间在前，无序区间在后。
每次在无序区间的头部取出一个元素，插入到有序区间中某一个位置，使其依然有序。
最开始有序区间只有一个元素，随着轮次的增加，有序区间元素越来越多，无序区间元素越来越少，直至无序区间没有元素，共需进行 length - 1次。
随着有序区间的数越来越多，将元素插入到有序区间要进行的比较次数s就越来越多。
最初有序区间只有一个数据，需要比较一次，插入成功后有序区间有两个数据就要比较两次，有序区间有多少个元素就需要比较多少次。

一步一步实现插入排序

内层循环，将元素插入到有序区间中。

void insertionSort(int arr[], int length) {
    //要插入到有序区间的元素。
    int value;
    //arr[1]为无序区间中的第一个元素
    value = arr[1];
    //有序区间的最后一个元素
    //这里 i 不能在for里面定义，后面还要用
    int i = 0;
    //从有序区间的最后开始寻找value应该插入的位置
    for(; i >= 0; --i) {
        if(arr[i] > value) {
            //这里的 i + 1其实就是value原来的位置，value已经被保存了，直接覆盖就可以
            arr[i + 1] = arr[i];
        } else {
            //当前元素不大于value，当前元素的下一个元素就应该是value，注意 break 后 i 不会 --，break 后 --i 不执行。
            break;
        }
    }
    arr[i + 1] = value;
}

外层循环，不断从无序区间取出数据插入到有序区间

void insertionSort(int arr[], int length) {
    //要插入到有序区间的元素。
    int value;
    for(int x = 1; x < length; ++x) {
        //arr[x]为无序区间中的第一个元素
        value = arr[x];
        //有序区间的最后一个元素
        int i = x - 1;
        //从有序区间的最后开始寻找value应该插入的位置
        for(; i >= 0; --i) {
            if(arr[i] > value) {
                //这里的 i + 1其实就是value原来的位置，value已经被保存了，直接覆盖就可以
                arr[i + 1] = arr[i];
            } else {
                //当前元素不大于value，当前元素的下一个元素就应该是value，注意 break 后 i 不会 --，break 后 --i 不执行。
                break;
            }
        }
        arr[i + 1] = value;
    }
}
//加上外循环后就完成了

插入排序已经完成了

插入排序和冒泡排序进行比较的次数是一样的，但插入排序更受欢迎，因为插入排序赋值操作要少于冒泡排序。

//冒泡
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
//插入
arr[i + 1] = arr[i];

都看到这了，点个赞再走嘛~