​

活动地址：CSDN21天学习挑战赛

📚“九层之台，起于垒土”。学习技术须脚踏实地。

☀️你要做冲出的黑马，而不是坠落的星星。
📖这里推荐一款刷题、模拟面试神器，可助你斩获心仪大厂offer：点我免费刷题、模拟面试

插入排序的概念

插入排序是一种较基础的排序算法，原理也简单易懂，只要会玩扑克就应该能很快学会。

1.直接插入排序

直接插入排序通过构建有序序列，依次扫描无序序列的每个元素，将其与有序序列比较，插入小于自身的元素后面，其余元素依次后移。

动图演示：

参考：菜鸟教程

​c++实现：

template<typename T>
void direct_insert_sort(T* arr, int len){
    for(int i = 1;i < len;i++){
        T temp = arr[i];
        int j = i - 1;
        while(j != -1 && temp < arr[j]){
            arr[j + 1] = arr[j];
            --j;
        }
        arr[++j] = temp;
    }
}

2.希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

由于插入排序具有以下两点性质：

• 插入排序在对几乎已经排好序的数据操作时，需要的元素访问与元素移位操作少。
• 直接插入排序每次只能插入一位。

所以可以先把元素分成几组，在每一组内直接插入排序。然后减少间距，形成新的分组，进行排序，直到间距为1时停止，这个过程中数列逐渐趋于有序，操作次数也比直接插入操作少。

动图演示：

参考：菜鸟教程

算法步骤：

• 选择一个序列 stride1、stride2、… 、1，其中后一个元素比前一个小。
• 序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的间距，将待排序列分割成若干子序列，分别对各子表进行直接插入排序。

c++实现：

template<typename T>
void shell_sort(T* array, int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}