描述

希尔排序，它是一种改进的插入排序。插入排序的思想是把一个数组分成两部分，一部分是已经排好序的，另一部分是未排序的。每次从未排序的部分取出一个元素，插入到已排序的部分的合适位置，使得已排序的部分仍然有序。这样重复进行，直到所有元素都排好序。

希尔排序的改进之处在于，它不是每次只取出一个元素进行插入，而是先把数组按照一定的间隔（称为跨度或增量）分成若干个子数组，然后对每个子数组进行插入排序。这样可以使得数组中较小的元素快速移动到前面，较大的元素快速移动到后面。然后再缩小间隔，重复上述过程，直到间隔为1，此时就相当于对整个数组进行了一次插入排序。

举个例子，假设我们有一个长度为8的数组：

[5, 3, 1, 7, 2, 9, 8, 4]

1. 我们可以先取一个间隔为4的跨度，把数组分成两个子数组（两行），也可以看作是4个子数组（4列），我们不妨都看作是列方向上的子数组：然后对每个子数组进行插入排序，然后再还原成原来的数组，想象一下就行，代码中不需要实现还原的。

2. 接下来我们再取一个间隔为2的跨度，把数组分成4个子数组（4行），或者说是2个子数组（2列），一样操作（插入排序），还原；

3. 最后我们再取一个间隔为1的跨度，把数组分成8个子数组（8行），或者说是1个子数组（1列），就是原数组了，插入排序，还原；

4. 结束

跨度为什么是4 2 1 呢？其实就是8/2， 8/2/2， 8/2/2/2

解释图呀，如下

结合其他大佬的写法写了出来，嘻嘻。

可以用acwing的785. 快速排序来练习验证。

附带上插入排序

代码部分

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 1e6+10;
int n,a[N];


void shell_sort(int arr[], int len) {
    int gap, i, j;
    int temp;
    // 枚举跨度gap,不断取半
    for (gap = len >> 1; gap > 0; gap >>= 1){

        // 和插入排序一样，每一次插入排序从下标（从一开始）的第二个开始往后枚举
        for (i = gap; i < len; i++) {
            temp = arr[i];


            // 和插入排序一样，就像上面的解释图，前后相差一个gap
            // 插入排序从小个数排到大个数,可以保证全部数字
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }

    }
}

void insert_sort(int arr[],int len){
    int j = 0;
    for(int i = 1;i < len;i++){
        int temp = arr[i];
        for(j = i - 1;j >= 0 && arr[j] > temp;j--)
            arr[j + 1] = arr[j];
        arr[j + 1] = temp;
    }

}

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i++){
        scanf("%d",&a[i]);
    }

    shell_sort(a,n);
    for(int i = 0;i < n;i++)printf("%d ",a[i]);


    return 0;
}